# SCIP

Solving Constraint Integer Programs

heur_gins.c
Go to the documentation of this file.
1 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
2 /* */
3 /* This file is part of the program and library */
4 /* SCIP --- Solving Constraint Integer Programs */
5 /* */
6 /* Copyright (C) 2002-2017 Konrad-Zuse-Zentrum */
7 /* fuer Informationstechnik Berlin */
8 /* */
9 /* SCIP is distributed under the terms of the ZIB Academic License. */
10 /* */
11 /* You should have received a copy of the ZIB Academic License */
12 /* along with SCIP; see the file COPYING. If not email to scip@zib.de. */
13 /* */
14 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
15
16 /**@file heur_gins.c
17  * @brief LNS heuristic that tries to delimit the search region to a neighborhood in the constraint graph
18  * @author Gregor Hendel
19  *
20  * Graph Induced Neighborhood Search (GINS) is a Large Neighborhood Search Heuristic that attempts to improve
21  * an incumbent solution by fixing a suitable percentage of integer variables to the incumbent and
22  * solving the resulting, smaller and presumably easier sub-MIP.
23  *
24  * Its search neighborhoods are based on distances in a bipartite graph \f$G\f$ with the variables and constraints as nodes
25  * and an edge between a variable and a constraint, if the variable is part of the constraint.
26  * Given an integer \f$k\f$, the \f$k\f$-neighborhood of a variable \f$v\f$ in \f$G\f$ is the set of variables, whose nodes
27  * are connected to \f$v\f$ by a path not longer than \f$2 \cdot k\f$. Intuitively, a judiciously chosen neighborhood size
28  * allows to consider a local portion of the overall problem.
29  *
30  * An initial variable selection is made by randomly sampling different neighborhoods across the whole main problem.
31  * The neighborhood that offers the largest potential for improvement is selected to become the local search neighborhood,
32  * while all variables outside the neighborhood are fixed to their incumbent solution values.
33  *
34  * GINS also supports a rolling horizon approach, during which several local neighborhoods are considered
35  * with increasing distance to the variable selected for the initial sub-problem. The rolling horizon approach ends
36  * if no improvement could be found or a sufficient part of the problem component variables has been part of
37  * at least one neighborhood.
38  */
39
40 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
41
42 #include <assert.h>
43 #include <string.h>
44 #include "scip/scip.h"
45 #include "scip/scipdefplugins.h"
46 #include "scip/heur_gins.h"
47 #include "scip/pub_misc.h"
48
49 #define HEUR_NAME "gins"
50 #define HEUR_DESC "gins works on k-neighborhood in a variable-constraint graph"
51 #define HEUR_DISPCHAR 'K'
52 #define HEUR_PRIORITY -1103000
53 #define HEUR_FREQ 20
54 #define HEUR_FREQOFS 8
55 #define HEUR_MAXDEPTH -1
56 #define HEUR_TIMING SCIP_HEURTIMING_AFTERNODE
57 #define HEUR_USESSUBSCIP TRUE /**< does the heuristic use a secondary SCIP instance? */
58
59 #define DEFAULT_NODESOFS 500 /**< number of nodes added to the contingent of the total nodes */
60 #define DEFAULT_MAXNODES 5000 /**< maximum number of nodes to regard in the subproblem */
61 #define DEFAULT_MINIMPROVE 0.01 /**< factor by which Gins should at least improve the incumbent */
62 #define DEFAULT_MINNODES 50 /**< minimum number of nodes to regard in the subproblem */
63 #define DEFAULT_MINFIXINGRATE 0.66 /**< minimum percentage of integer variables that have to be fixed */
64 #define DEFAULT_NODESQUOT 0.15 /**< subproblem nodes in relation to nodes of the original problem */
65 #define DEFAULT_NWAITINGNODES 100 /**< number of nodes without incumbent change that heuristic should wait */
66 #define DEFAULT_USELPROWS FALSE /**< should subproblem be created out of the rows in the LP rows,
67  **< otherwise, the copy constructors of the constraints handlers are used */
68 #define DEFAULT_COPYCUTS TRUE /**< if DEFAULT_USELPROWS is FALSE, then should all active cuts from the
69  **< cutpool of the original scip be copied to constraints of the subscip */
70 #define DEFAULT_BESTSOLLIMIT 3 /**< limit on number of improving incumbent solutions in sub-CIP */
71 #define DEFAULT_FIXCONTVARS FALSE /**< should continuous variables outside the neighborhoods get fixed? */
72 #define DEFAULT_POTENTIAL 'r' /**< the reference point to compute the neighborhood potential: (r)oot or (p)seudo solution */
73 #define DEFAULT_MAXDISTANCE 3 /**< maximum distance to selected variable to enter the subproblem, or -1 to
74  * select the distance that best approximates the minimum fixing rate from below */
75 #define DEFAULT_RANDSEED 71
76 #define DEFAULT_RELAXDENSECONSS FALSE /**< should dense constraints (at least as dense as 1 - minfixingrate) be
77  * ignored by connectivity graph? */
78 #define DEFAULT_USEROLLINGHORIZON TRUE /**< should the heuristic solve a sequence of sub-MIP's around the first selected variable */
79 #define DEFAULT_ROLLHORIZONLIMFAC 0.4 /**< limiting percentage for variables already used in sub-SCIPs to terminate rolling
80  * horizon approach */
81 #ifdef SCIP_STATISTIC
82 #define NHISTOGRAMBINS 10 /* number of bins for histograms */
83 #endif
84 /*
85  * Data structures
86  */
87
88 /** variable graph data structure to determine breadth-first distances between variables
89  *
90  * the variable graph internally stores a mapping from the variables to the constraints in which they appear.
91  */
92 struct VariableGraph
93 {
94  SCIP_CONS*** varconss; /**< constraints of each variable */
95  SCIP_HASHTABLE* visitedconss; /**< hash table that keeps a record of visited constraints during breadth-first search */
96  int* nvarconss; /**< number of constraints for each variable */
97  int* varconssize; /**< size array for every varconss entry */
98 };
101 /** rolling horizon data structure to control multiple LNS heuristic runs away from an original source variable
102  *
103  */
105 {
106  VARIABLEGRAPH* variablegraph; /**< variable graph data structure for breadth-first-search neighborhoods */
107  int* distances; /**< distances of the heuristic rolling horizon from the original source
108  * variable indexed by probindex */
109  SCIP_Bool* used; /**< array that represents for every variable whether it has been used
110  * in a neighborhood indexed by probindex */
111  int lastmaxdistance; /**< the last distance k for a neighborhood, will be decreased
112  * during the rolling horizon if the selected neighborhood is too large */
113  int lastdistance; /**< last distance from originally selected variable in iteration zero */
114  int distancessize; /**< size of the distances and used arrays */
115  int niterations; /**< counter for the number of rolling horizon iterations */
116  int nused; /**< counts the number variables that have been part of any neighborhood
117  * during the rolling horizon approach */
118  int nnonreachable; /**< counter for the number of nonreachable variables (distance -1) from
119  * the initially selected variable */
120 };
122
123 /** primal heuristic data */
124 struct SCIP_HeurData
125 {
126  int nodesofs; /**< number of nodes added to the contingent of the total nodes */
127  int maxnodes; /**< maximum number of nodes to regard in the subproblem */
128  int minnodes; /**< minimum number of nodes to regard in the subproblem */
129  SCIP_Real minfixingrate; /**< minimum percentage of integer variables that have to be fixed */
130  int nwaitingnodes; /**< number of nodes without incumbent change that heuristic should wait */
131  SCIP_Real minimprove; /**< factor by which Gins should at least improve the incumbent */
132  SCIP_Longint usednodes; /**< nodes already used by Gins in earlier calls */
133  SCIP_Real nodesquot; /**< subproblem nodes in relation to nodes of the original problem */
134  SCIP_Real rollhorizonlimfac; /**< limiting percentage for variables already used in sub-SCIPs to terminate
135  * rolling horizon approach */
136  SCIP_RANDNUMGEN* randnumgen; /**< random number generator */
137  SCIP_Bool uselprows; /**< should subproblem be created out of the rows in the LP rows? */
138  SCIP_Bool copycuts; /**< if uselprows == FALSE, should all active cuts from cutpool be copied
139  * to constraints in subproblem? */
140  SCIP_Bool fixcontvars; /**< should continuous variables outside the neighborhoods get fixed? */
141  int bestsollimit; /**< limit on number of improving incumbent solutions in sub-CIP */
142  int maxdistance; /**< maximum distance to selected variable to enter the subproblem, or -1 to
143  * select the distance that best approximates the minimum fixing rate from below */
144  int sumneighborhoodvars;/**< neighborhood variables sum over all seen neighborhoods */
145  int sumdiscneighborhoodvars; /**< neighborhood discrete variables sum over all seen neighboorhoods */
146  int nneighborhoods; /**< number of calculated neighborhoods */
147  int nsubmips; /**< counter for the number of sub-MIP's that can be higher than the number of
148  * calls of this heuristic */
149  SCIP_Bool relaxdenseconss; /**< should dense constraints (at least as dense as 1 - minfixingrate) be
150  * ignored by connectivity graph? */
151  SCIP_Bool userollinghorizon; /**< should the heuristic solve a sequence of sub-MIP's around the first
152  * selected variable */
153  char potential; /**< the reference point to compute the neighborhood potential: (r)oot or
154  * (p)seudo solution */
155  int maxseendistance; /**< maximum of all distances between two variables */
156 #ifdef SCIP_STATISTIC
157  int consvarshist[NHISTOGRAMBINS]; /**< histogram that summarizes the densities of the constraints */
158  int consdiscvarshist[NHISTOGRAMBINS]; /**< histogram that summarizes the discrete variable densities of the constraints */
159  int conscontvarshist[NHISTOGRAMBINS]; /**< histogram that summarizes the continuous variable densities of the constraints */
160 #endif
161  int nrelaxedconstraints; /**< number of constraints that were relaxed */
162  int nfailures; /**< counter for the number of unsuccessful runs of this heuristic */
163  SCIP_Longint nextnodenumber; /**< the next node number at which the heuristic should be called again */
164 };
165
166 /** represents limits for the sub-SCIP solving process */
167 struct SolveLimits
168 {
169  SCIP_Longint nodelimit; /**< maximum number of solving nodes for the sub-SCIP */
170  SCIP_Real memorylimit; /**< memory limit for the sub-SCIP */
171  SCIP_Real timelimit; /**< time limit for the sub-SCIP */
172 };
173 typedef struct SolveLimits SOLVELIMITS;
175 /*
176  * Local methods
177  */
179 #ifdef SCIP_STATISTIC
180 /** resets a histogram */
181 static
182 void resetHistogram(
183  int* histogram /**< the histogram */
184  )
185 {
186  BMSclearMemoryArray(histogram, NHISTOGRAMBINS);
187 }
188
189 /** adds a ratio to the histogram at the right position */
190 static
192  int* histogram, /**< the histogram */
193  int value, /**< the value */
194  int basevalue /**< base value */
195  )
196 {
197  SCIP_Real ratio;
198  int index;
199  assert(value <= basevalue);
200  ratio = value/ MAX(1.0, (SCIP_Real)basevalue);
201
202  index = (int)(ratio * NHISTOGRAMBINS);
203  ++histogram[index];
204 }
205
206 #endif
207
208 /* fills variable graph data structure
209  *
210  * loops over global problem constraints and creates a mapping from the variables to their respective constraints
211  */
212 static
214  SCIP* scip, /**< SCIP data structure */
215  VARIABLEGRAPH* vargraph, /**< variable graph data structure for breadth-first-search neighborhoods */
216  SCIP_HEURDATA* heurdata /**< heuristic data */
217  )
218 {
219  SCIP_CONS** conss;
220  int nconss;
221  int nvars;
222  int c;
223  SCIP_VAR** varbuffer;
224
225  assert(scip != NULL);
226  assert(vargraph != NULL);
227
228  conss = SCIPgetConss(scip);
229  nconss = SCIPgetNConss(scip);
230
231  nvars = SCIPgetNVars(scip);
232  SCIP_CALL( SCIPallocBufferArray(scip, &varbuffer, nvars) );
233
234 #ifdef SCIP_STATISTIC
235  resetHistogram(heurdata->consvarshist);
236  resetHistogram(heurdata->consdiscvarshist);
237  resetHistogram(heurdata->conscontvarshist);
238 #endif
239
240  heurdata->nrelaxedconstraints = 0;
241
242  for( c = 0; c < nconss; ++c )
243  {
244  int nconsvars;
245  int v;
246  SCIP_Bool success;
247  SCIP_CONS* cons = conss[c];
248
249 #ifdef SCIP_STATISTIC
250  int nconsdiscvars;
251  int nconscontvars;
252 #endif
253
254  /* we only consider constraints that are checkable */
255  if( !SCIPconsIsChecked(cons) )
256  continue;
257
258  /* request number of variables */
259  SCIP_CALL( SCIPgetConsNVars(scip, cons, &nconsvars, &success) );
260
261  if( !success )
262  continue;
263
264  /* relax constraints with density above the allowed number of free variables */
265  if( heurdata->relaxdenseconss && nconsvars >= (1.0 - heurdata->minfixingrate) * nvars )
266  {
267  ++heurdata->nrelaxedconstraints;
268  continue;
269  }
270
271  /* collect constraint variables in buffer */
272  SCIP_CALL( SCIPgetConsVars(scip, cons, varbuffer, nvars, &success) );
273
274  if( !success )
275  continue;
276
277 #ifdef SCIP_STATISTIC
278  nconscontvars = 0;
279  nconsdiscvars = 0;
280 #endif
281
282  /* loop over constraint variables and add this constraint to them if they are active */
283  for( v = 0; v < nconsvars; ++v )
284  {
285  int varpos = SCIPvarGetProbindex(varbuffer[v]);
286
287  /* skip inactive variables */
288  if( varpos == -1 )
289  continue;
290
291 #ifdef SCIP_STATISTIC
292  /* count discrete and continuous problem variables */
293  if( SCIPvarIsIntegral(varbuffer[v]) )
294  ++nconsdiscvars;
295  else
296  ++nconscontvars;
297 #endif
298  /* ensure array size */
299  if( vargraph->varconssize[varpos] == vargraph->nvarconss[varpos] )
300  {
301  int newmem = SCIPcalcMemGrowSize(scip, vargraph->nvarconss[varpos] + 1);
302
303  assert(newmem > vargraph->varconssize[varpos]);
304
305  if( vargraph->varconss[varpos] == NULL )
306  {
307  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &vargraph->varconss[varpos], newmem) );
308  }
309  else
310  {
311  SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &vargraph->varconss[varpos], vargraph->varconssize[varpos], newmem) ); /*lint !e866*/
312  }
313  vargraph->varconssize[varpos] = newmem;
314  }
315
316  assert(vargraph->nvarconss[varpos] < vargraph->varconssize[varpos]);
317
318  /* add constraint to constraint array for this variable */
319  vargraph->varconss[varpos][vargraph->nvarconss[varpos]] = cons;
320  vargraph->nvarconss[varpos] += 1;
321  }
322
323  /* update the histograms */
324 #ifdef SCIP_STATISTIC
325  addHistogramEntry(heurdata->consvarshist, nconsvars, SCIPgetNVars(scip));
326  addHistogramEntry(heurdata->consdiscvarshist, nconsdiscvars, SCIPgetNVars(scip) - SCIPgetNContVars(scip));
327  addHistogramEntry(heurdata->conscontvarshist, nconscontvars, nconsvars);
328 #endif
329  }
330
331  /* free the buffer */
332  SCIPfreeBufferArray(scip, &varbuffer);
333
334  return SCIP_OKAY;
335 }
336
337 /** initialization method of variable graph data structure */
338 static
340  SCIP* scip, /**< SCIP data structure */
341  VARIABLEGRAPH** vargraph, /**< pointer to the variable graph */
342  SCIP_HEURDATA* heurdata /**< heuristic data */
343  )
344 {
345  int nvars;
346  int nconss;
347
348  assert(scip != NULL);
349  assert(vargraph != NULL);
350
351  nvars = SCIPgetNVars(scip);
352  nconss = SCIPgetNConss(scip);
353
354  if( nvars == 0 )
355  return SCIP_OKAY;
356
357  SCIP_CALL( SCIPallocBlockMemory(scip, vargraph) );
358
359  SCIP_CALL( SCIPhashtableCreate(&(*vargraph)->visitedconss, SCIPblkmem(scip), 2 * nconss, SCIPhashGetKeyStandard,
360  SCIPhashKeyEqPtr, SCIPhashKeyValPtr, NULL) );
361
362  /* allocate and clear memory */
363  SCIP_CALL( SCIPallocClearBlockMemoryArray(scip, &(*vargraph)->varconss, nvars) );
364  SCIP_CALL( SCIPallocClearBlockMemoryArray(scip, &(*vargraph)->nvarconss, nvars) );
365  SCIP_CALL( SCIPallocClearBlockMemoryArray(scip, &(*vargraph)->varconssize, nvars) );
366
367  /* fill the variable graph with variable-constraint mapping for breadth-first search*/
368  SCIP_CALL( fillVariableGraph(scip, *vargraph, heurdata) );
369
370  return SCIP_OKAY;
371 }
372
373 /** deinitialization method of variable graph data structure */
374 static
375 void variableGraphFree(
376  SCIP* scip, /**< SCIP data structure */
377  VARIABLEGRAPH** vargraph /**< pointer to the variable graph */
378  )
379 {
380  int nvars;
381  int v;
382  assert(scip != NULL);
383  assert(vargraph != NULL);
384
385  nvars = SCIPgetNVars(scip);
386
387  for( v = nvars - 1; v >= 0; --v )
388  {
389  SCIPfreeBlockMemoryArrayNull(scip, &(*vargraph)->varconss[v], (*vargraph)->varconssize[v]); /*lint !e866*/
390  }
391
392  /* allocate and clear memory */
393  SCIPfreeBlockMemoryArray(scip, &(*vargraph)->varconssize, nvars);
394  SCIPfreeBlockMemoryArray(scip, &(*vargraph)->nvarconss, nvars);
395  SCIPfreeBlockMemoryArray(scip, &(*vargraph)->varconss, nvars);
396
397  SCIPhashtableFree(&(*vargraph)->visitedconss);
398
399  SCIPfreeBlockMemory(scip, vargraph);
400 }
401
402 /* breadth-first (BFS) search on the variable constraint graph; uses a special kind of queue data structure that holds
403  * two queue levels at the same time: the variables at the current distance and the ones at the next distance
404  */
405 static
407  SCIP* scip, /**< SCIP data structure */
408  VARIABLEGRAPH* vargraph, /**< pointer to the variable graph */
409  SCIP_VAR* startvar, /**< variable to calculate distance from */
410  int* distances, /**< array to keep distance in vargraph from startvar for every variable */
411  int maxdistance /**< maximum distance >= 0 from start variable (INT_MAX for complete BFS)*/
412  )
413 {
414  SCIP_VAR** vars;
415
416  int* queue;
417  int nvars;
418  int i;
419  int currlvlidx;
420  int nextlvlidx;
421  int increment = 1;
422  int currentdistance;
423  SCIP_VAR** varbuffer;
424
425  assert(scip != NULL);
426  assert(vargraph != NULL);
427  assert(startvar != NULL);
428  assert(distances != NULL);
429  assert(maxdistance >= 0);
430
431  /* get variable data */
432  nvars = SCIPgetNVars(scip);
433  vars = SCIPgetVars(scip);
434  SCIP_CALL( SCIPallocBufferArray(scip, &queue, nvars) );
435  SCIP_CALL( SCIPallocClearBufferArray(scip, &varbuffer, nvars) );
436
438
439  /* initialize distances to -1 */
440  for( i = 0; i < nvars; ++i )
441  {
442  queue[i] = -1;
443  distances[i] = -1;
444  }
445
446  /* start variable has a distance of 0 */
447  distances[SCIPvarGetProbindex(startvar)] = 0;
448
449  queue[0] = SCIPvarGetProbindex(startvar);
450  currlvlidx = 0;
451  nextlvlidx = nvars - 1;
452
453  /* loop over the queue and pop the next variable, starting with start variable */
454  do
455  {
456  SCIP_VAR* currvar;
457  int c;
458  int varpos;
459
460  currvar = vars[queue[currlvlidx]];
461  varpos = SCIPvarGetProbindex(currvar);
462  currentdistance = distances[varpos];
463  assert(currentdistance >= 0);
464
465  /* distances must only be computed up to maxdistance */
466  assert(currentdistance <= maxdistance);
467
468  /* check for termination because maximum distance has been reached */
469  if( currentdistance == maxdistance )
470  break;
471
472  assert(varpos >= 0);
473
474  /* loop over variable constraints and enqueue variables that were not visited yet */
475  for( c = 0; c < vargraph->nvarconss[varpos]; ++c )
476  {
477  int nconsvars;
478  int v;
479  SCIP_Bool success;
480  SCIP_CONS* cons = vargraph->varconss[varpos][c];
481
482  /* check first if this constraint has already been visited */
483  if( SCIPhashtableExists(vargraph->visitedconss, (void *)cons) )
484  continue;
485
486  /* request number of constraint variables */
487  SCIP_CALL( SCIPgetConsNVars(scip, cons, &nconsvars, &success) );
488
489  if( !success )
490  continue;
491
492  /* collect constraint variables in buffer */
493  SCIP_CALL( SCIPgetConsVars(scip, cons, varbuffer, nvars, &success) );
494
495  if( !success )
496  continue;
497
498  /* collect previously unvisited variables of the constraint and enqueue them for breadth-first search */
499  for( v = 0; v < nconsvars; ++v )
500  {
501  SCIP_VAR* nextvar = varbuffer[v];
502  int nextvarpos;
503  assert(nextvar != NULL);
504  if( !SCIPvarIsActive(nextvar) )
505  continue;
506
507  nextvarpos = SCIPvarGetProbindex(nextvar);
508  assert(nextvarpos >= 0);
509
510  /* insert variables that were not considered yet into the next level queue */
511  if( distances[nextvarpos] == -1 )
512  {
513  distances[nextvarpos] = currentdistance + 1;
514  queue[nextlvlidx] = nextvarpos;
515  nextlvlidx -= increment;
516  }
517  } /* end constraint variables loop */
518
519  /* mark the constraint as visited */
520  SCIP_CALL( SCIPhashtableInsert(vargraph->visitedconss, (void *)cons) );
521
522  } /* end constraint loop */
523
524  queue[currlvlidx] = -1;
525  currlvlidx += increment;
526
527  /* check if we need to swap current and next level index and reverse the increment */
528  if( currlvlidx == nvars || currlvlidx == 0 || queue[currlvlidx] == -1 || currlvlidx == nextlvlidx )
529  {
530  /* increment knows whether we are currently looping upwards (all variables with odd distance) or downwards the
531  * queue
532  */
533  if( increment == +1 )
534  {
535  currlvlidx = nvars - 1;
536  nextlvlidx = 0;
537  increment = -1;
538  }
539  else
540  {
541  currlvlidx = 0;
542  nextlvlidx = nvars - 1;
543  increment = +1;
544  }
545  }
546  }
547  while( queue[currlvlidx] != -1 && distances[queue[currlvlidx]] >= currentdistance );
548
549  SCIPfreeBufferArray(scip, &varbuffer);
550  SCIPfreeBufferArray(scip, &queue);
551
552  return SCIP_OKAY;
553 }
554
555 /** create a rolling horizon data structure */
556 static
558  SCIP* scip, /**< SCIP data structure */
559  ROLLINGHORIZON** rollinghorizon /**< pointer to rolling horizon data structure */
560  )
561 {
562  int size;
563  assert(scip != NULL);
564  assert(rollinghorizon != NULL);
565
566  size = SCIPgetNBinVars(scip) + SCIPgetNIntVars(scip);
567  SCIP_CALL( SCIPallocBlockMemory(scip, rollinghorizon) );
568  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(*rollinghorizon)->distances, size) );
569  SCIP_CALL( SCIPallocClearBlockMemoryArray(scip, &(*rollinghorizon)->used, size) );
570  (*rollinghorizon)->distancessize = size;
571  (*rollinghorizon)->variablegraph = NULL;
572  (*rollinghorizon)->lastdistance = -1;
573  (*rollinghorizon)->niterations = 0;
574  (*rollinghorizon)->nused = 0;
575
576  return SCIP_OKAY;
577 }
578
579 /** free a rolling horizon data structure */
580 static
582  SCIP* scip, /**< SCIP data structure */
583  ROLLINGHORIZON** rollinghorizon /**< pointer to rolling horizon data structure */
584  )
585 {
587  assert(scip != NULL);
588  assert(rollinghorizon != NULL);
589  assert(*rollinghorizon != NULL);
590
591  if( (*rollinghorizon)->variablegraph != NULL )
592  {
593  variableGraphFree(scip, &(*rollinghorizon)->variablegraph);
594  }
595
596  SCIPfreeBlockMemoryArray(scip, &(*rollinghorizon)->distances, (*rollinghorizon)->distancessize);
597  SCIPfreeBlockMemoryArray(scip, &(*rollinghorizon)->used, (*rollinghorizon)->distancessize);
598  SCIPfreeBlockMemory(scip, rollinghorizon);
599  return SCIP_OKAY;
600 }
601
602 /** is there potential to run another iteration of the rolling horizon approach? */
603 static
605  SCIP* scip, /**< SCIP data structure */
606  ROLLINGHORIZON* rollinghorizon, /**< rolling horizon data structure */
607  SCIP_HEURDATA* heurdata /**< heuristic data */
608  )
609 {
610  int maxnused = (int)(heurdata->rollhorizonlimfac * (SCIPgetNBinVars(scip) + SCIPgetNIntVars(scip)
611  - rollinghorizon->nnonreachable));
612
613  /* run again if a certain percentage of the reachable variables (in the same connected component)
614  * was not used in a previous neighborhood
615  */
616  return (rollinghorizon->nused < maxnused);
617 }
618
619 /** store the distances from the selected variable permanently for the rolling horizon approach */
620 static
622  SCIP* scip, /**< SCIP data structure */
623  ROLLINGHORIZON* rollinghorizon, /**< rolling horizon data structure */
624  int* distances /**< breadth-first distances indexed by Probindex of variables */
625  )
626 {
627  int i;
628  BMScopyMemoryArray(rollinghorizon->distances, distances, rollinghorizon->distancessize);
629  rollinghorizon->lastdistance = 0;
630  rollinghorizon->nnonreachable = 0;
631
632  /* collect number of nonreachable variables */
633  for( i = 0; i < rollinghorizon->distancessize; ++i )
634  {
635  if( distances[i] == -1 )
636  ++rollinghorizon->nnonreachable;
637  }
638 }
639
640 /** get the potential of a subset of variables (distance to a reference point such as the pseudo-solution or root
641  * LP solution)
642  */
643 static
645  SCIP* scip, /**< SCIP data structure */
646  SCIP_HEURDATA* heurdata, /**< heuristic data */
647  SCIP_SOL* sol, /**< solution */
648  SCIP_VAR** vars, /**< variable array */
649  int nvars /**< length of variable array */
650  )
651 {
652  SCIP_Real potential;
653  int i;
654
655  assert(scip != NULL);
656  assert(vars != NULL);
657  assert(sol != NULL);
658
659  if( nvars == 0 )
660  return 0.0;
661
662  potential = 0.0;
663
664  for( i = 0; i < nvars; ++i )
665  {
666  SCIP_Real objdelta;
667  SCIP_VAR* var;
668  SCIP_Real referencepoint;
669  SCIP_Real varobj;
670
671  var = vars[i];
672  assert(var != NULL);
673  varobj = SCIPvarGetObj(var);
674
675  if( SCIPisZero(scip, varobj) )
676  continue;
677
678  /* determine the reference point for potential computation */
679  switch( heurdata->potential )
680  {
681  /* use difference to pseudo solution using the bound in the objective direction */
682  case 'p':
683  referencepoint = SCIPvarGetObj(var) > 0.0 ? SCIPvarGetLbGlobal(var) : SCIPvarGetUbGlobal(var);
684  break;
685
686  /* use root LP solution difference */
687  case 'r':
688  referencepoint = SCIPvarGetRootSol(var);
689  break;
690  default:
691  SCIPerrorMessage("Unknown potential computation %c specified\n", heurdata->potential);
692  referencepoint = 0.0;
693  break;
694  }
695
696  if( SCIPisInfinity(scip, REALABS(referencepoint)) )
697  continue;
698
699  /* calculate the delta to the variables best bound */
700  objdelta = (SCIPgetSolVal(scip, sol, var) - referencepoint) * SCIPvarGetObj(var);
701  potential += objdelta;
702  }
703
704  return potential;
705 }
706
707 /** is the variable in the current neighborhood which is given by the breadth-first distances from a central variable? */
708 static
710  SCIP_VAR* var, /**< problem variable */
711  int* distances, /**< breadth-first distances indexed by Probindex of variables */
712  int maxdistance /**< maximum distance (inclusive) to be considered for neighborhoods */
713  )
714 {
715  assert(var != NULL);
716  assert(distances != NULL);
717  assert(maxdistance >= 0);
718  assert(SCIPvarGetProbindex(var) >= 0);
719
720  return (distances[SCIPvarGetProbindex(var)] != -1 && distances[SCIPvarGetProbindex(var)] <= maxdistance);
721 }
722
723 /** fixes variables in subproblem based on long breadth-first distances in variable graph */
724 static
726  SCIP* scip, /**< SCIP data structure */
727  SCIP_HEURDATA* heurdata, /**< heuristic data */
728  ROLLINGHORIZON* rollinghorizon, /**< rolling horizon data structure to save relevant information, or NULL if not needed */
729  SCIP_SOL* sol, /**< solution in main SCIP for fixing values */
730  SCIP_VAR** vars, /**< variables in the main SCIP */
731  SCIP_VAR** fixedvars, /**< buffer to store variables that should be fixed */
732  SCIP_Real* fixedvals, /**< buffer to store fixing values for fixed variables */
733  int* distances, /**< breadth-first distances indexed by Probindex of variables */
734  int maxdistance, /**< maximum distance (inclusive) to be considered for neighborhoods */
735  int* nfixings /**< pointer to store number of fixed variables */
736  )
737 {
738  int i;
739  int nbinvars;
740  int nintvars;
741  int nvars;
742  int nvarstofix;
743
744  SCIP_CALL( SCIPgetVarsData(scip, NULL, &nvars, &nbinvars, &nintvars, NULL, NULL) );
745
746  nvarstofix = heurdata->fixcontvars ? nvars : nbinvars + nintvars;
747  *nfixings = 0;
748
749  /* change bounds of variables of the subproblem */
750  for( i = 0; i < nvarstofix; i++ )
751  {
752  /* fix all variables that are too far away from this variable according to maxdistance */
753  if( distances[i] == -1 || distances[i] > maxdistance )
754  {
755  SCIP_Real solval;
756  SCIP_Real lb;
757  SCIP_Real ub;
758
759  solval = SCIPgetSolVal(scip, sol, vars[i]);
760  lb = SCIPvarGetLbGlobal(vars[i]);
761  ub = SCIPvarGetUbGlobal(vars[i]);
762  assert(SCIPisLE(scip, lb, ub));
763
764  /* due to dual reductions, it may happen that the solution value is not in the variable's domain anymore */
765  if( SCIPisLT(scip, solval, lb) )
766  solval = lb;
767  else if( SCIPisGT(scip, solval, ub) )
768  solval = ub;
769
770  /* perform the bound change */
771  if( !SCIPisInfinity(scip, solval) && !SCIPisInfinity(scip, -solval) )
772  {
773  fixedvars[*nfixings] = vars[i];
774  fixedvals[*nfixings] = solval;
775  ++(*nfixings);
776  }
777  }
778  else if( rollinghorizon != NULL && i < nbinvars + nintvars && ! rollinghorizon->used[i] )
779  {
780  ++rollinghorizon->nused;
781  rollinghorizon->used[i] = TRUE;
782  }
783  }
784
785  if( rollinghorizon != NULL )
786  {
787  rollinghorizon->lastmaxdistance = maxdistance;
788  rollinghorizon->niterations++;
789  }
790
791  return SCIP_OKAY;
792 }
793
794 /** determine the maximum allowed distance to stay within the restriction to fix at least minfixingrate many non
795  * neighborhood variables
796  */
797 static
799  SCIP* scip, /**< SCIP data structure */
800  SCIP_HEURDATA* heurdata, /**< heuristic data */
801  int* distances, /**< breadth-first distances indexed by Probindex of variables */
802  int* choosevardistance /**< pointer to store the computed maximum distance */
803  )
804 {
805  int* distancescopy;
806  int nrelevantdistances;
807  int criticalidx;
808  int zeropos;
809  int nvars;
810  int nbinvars;
811  int nintvars;
812
813  SCIP_CALL( SCIPgetVarsData(scip, NULL, &nvars, &nbinvars, &nintvars, NULL, NULL) );
814
815  nrelevantdistances = (heurdata->fixcontvars ? nvars : (nbinvars + nintvars));
816
817  /* copy the relevant distances of either the discrete or all problem variables and sort them */
818  SCIP_CALL( SCIPduplicateBufferArray(scip, &distancescopy, distances, nrelevantdistances) );
819  SCIPsortInt(distancescopy, nrelevantdistances);
820
821  /* distances can be infinite in the case of multiple connected components; therefore, search for the index of the
822  * zero entry, which is the unique representative of the chosen variable in the sorted distances
823  */
824  zeropos = -1;
825
826  /* TODO: use selection method instead */
827  (void)SCIPsortedvecFindInt(distancescopy, 0, nrelevantdistances, &zeropos);
828  assert(zeropos >= 0);
829
830  /* determine the critical index to look for an appropriate neighborhood distance, starting from the zero position */
831  criticalidx = zeropos + (int)((1.0 - heurdata->minfixingrate) * nrelevantdistances);
832  criticalidx = MIN(criticalidx, nrelevantdistances - 1);
833
834  /* determine the maximum breadth-first distance such that the neighborhood size stays small enough (below 1-minfixingrate)*/
835  *choosevardistance = distancescopy[criticalidx];
836
837  /* we set the distance to exactly the distance at the critical index. If the distance at critical index is not the
838  * last one before the distance increases, we decrease the choosevardistance such that the entire neighborhood
839  * fits into the minfixingrate restriction
840  */
841  if( criticalidx != nrelevantdistances - 1 && distancescopy[criticalidx + 1] == *choosevardistance )
842  (*choosevardistance)--;
843
844  /* update the maximum distance */
845  heurdata->maxseendistance = MAX(heurdata->maxseendistance, distancescopy[nrelevantdistances - 1]);
846
847  SCIPfreeBufferArray(scip, &distancescopy);
848
849  return SCIP_OKAY;
850 }
851
852 /** gets the average size of a discrete neighborhood over all variables tested */
853 static
855  SCIP_HEURDATA* heurdata /**< heuristic data */
856  )
857 {
858  return heurdata->sumdiscneighborhoodvars / (MAX(1.0, (SCIP_Real)heurdata->nneighborhoods));
859 }
860
861 /** select a good starting variable at the first iteration of a rolling horizon approach */
862 static
864  SCIP* scip, /**< SCIP data structure */
865  SCIP_HEURDATA* heurdata, /**< heuristic data */
866  VARIABLEGRAPH* vargraph, /**< variable graph data structure to work on */
867  int* distances, /**< breadth-first distances indexed by Probindex of variables */
868  SCIP_VAR** selvar, /**< pointer to store the selected variable */
869  int* selvarmaxdistance /**< maximal distance k to consider for selected variable neighborhood */
870  )
871 {
872  SCIP_SOL* sol;
873  SCIP_VAR** vars; /* original scip variables */
874  int nbinvars;
875  int nintvars;
876  int nvars;
877  int nsearched;
878  int searchlimit;
879  int nintegralvarsleft;
880  int nintegralvarsbound;
881  int v;
882  SCIP_VAR** varscopy;
883  int maxdistance;
884  SCIP_Real maxpotential;
885
886  assert(vargraph != NULL);
887  assert(scip != NULL);
888  assert(heurdata != NULL);
889  assert(selvar != NULL);
890  sol = SCIPgetBestSol(scip);
891  assert(sol != NULL);
892
893  /* get required data of the original problem */
894  SCIP_CALL( SCIPgetVarsData(scip, &vars, &nvars, &nbinvars, &nintvars, NULL, NULL) );
895
896  /* copy SCIP variables */
897  SCIP_CALL( SCIPduplicateBufferArray(scip, &varscopy, vars, nbinvars + nintvars) );
898  nsearched = 0;
899  maxpotential = SCIP_REAL_MIN;
900
901  /* determine upper bound on neighborhood size */
902  nintegralvarsbound = (int)((1.0 - heurdata->minfixingrate) * (nbinvars + nintvars));
903
904  /* maximum distance from selected variable for breadth-first search (if set to -1, we compute an exhaustive breadth-first
905  * search and sort the variables by their distance)
906  */
907  maxdistance = (heurdata->maxdistance == - 1 ? INT_MAX : heurdata->maxdistance);
908
909  nintegralvarsleft = nbinvars + nintvars;
910  *selvar = NULL;
911
912  /* sort inactive variables to the end of the array */
913  for( v = nintegralvarsleft - 1; v >= 0; --v )
914  {
915  if( ! SCIPvarIsActive(varscopy[v]) )
916  {
917  varscopy[v] = varscopy[nintegralvarsleft - 1];
918  --nintegralvarsleft;
919  }
920  }
921
922  /* adjust the search limit */
923  searchlimit = heurdata->nneighborhoods < 10 ? 5 : (int)(nintegralvarsleft / heurdataAvgDiscreteNeighborhoodSize(heurdata));
924  searchlimit = MIN(searchlimit, 10);
925
926  /* multi variable potential: choose different disjoint neighborhoods, compare their potential */
927  while( nsearched < searchlimit && nintegralvarsleft > 0 )
928  {
929  SCIP_VAR** neighborhood;
930  SCIP_VAR* choosevar;
931  int neighborhoodsize;
932  int ndiscvarsneighborhood;
933  int choosevardistance;
934
935  ++nsearched;
936
937  /* select a variable to start with randomly, but make sure it is active */
938  do
939  {
940  int idx = SCIPrandomGetInt(heurdata->randnumgen, 0, nintegralvarsleft - 1);
941  choosevar = varscopy[idx];
942  assert(choosevar != NULL);
943  /* sort inactive variables to the end */
944  if( SCIPvarGetProbindex(choosevar) < 0 )
945  {
946  varscopy[idx] = varscopy[nintegralvarsleft - 1];
947  --nintegralvarsleft;
948  }
949  }
950  while( SCIPvarGetProbindex(choosevar) < 0 && nintegralvarsleft > 0);
951
952  /* if there was no variable chosen, there are no active variables left */
953  if( SCIPvarGetProbindex(choosevar) < 0 )
954  {
955  SCIPdebugMsg(scip, "No active variable left to perform breadth-first search\n");
956  break;
957  }
958
959  assert(SCIPvarIsIntegral(choosevar));
960
961  /* get neighborhood storage */
962  SCIP_CALL( SCIPallocBufferArray(scip, &neighborhood, nvars) );
963
964  /* determine breadth-first distances from the chosen variable */
965  SCIP_CALL( variablegraphBreadthFirst(scip, vargraph, choosevar, distances, maxdistance) );
966
967  /* use either automatic or user-defined max-distance for neighborhood in variable constraint graph */
968  if( heurdata->maxdistance != -1 )
969  {
970  choosevardistance = heurdata->maxdistance;
971  }
972  else
973  {
974  SCIP_CALL( determineMaxDistance(scip, heurdata, distances, &choosevardistance) );
975  }
976
977  ndiscvarsneighborhood = 0;
978  neighborhoodsize = 0;
979
980  /* loop over variables and determine neighborhood */
981  for( v = nvars - 1; v >= 0; --v )
982  {
983  SCIP_VAR* currvar;
984  currvar = vars[v];
985
986  /* put variable in the neighborhood */
987  if( isVariableInNeighborhood(currvar, distances, choosevardistance) )
988  {
989  neighborhood[neighborhoodsize++] = currvar;
990
991  /* increase discrete variables counter */
992  if( SCIPvarIsIntegral(currvar) )
993  ++ndiscvarsneighborhood;
994  }
995  }
996
997  /* check if neighborhood contains too many integer variables in order to satisfy the minimum fixing rate */
998  if( ndiscvarsneighborhood >= nintegralvarsbound || ndiscvarsneighborhood <= 1 )
999  {
1000  SCIPdebugMsg(scip, "Too many or too few discrete variables in neighboorhood: %d (%d)\n",
1001  ndiscvarsneighborhood, nbinvars + nintvars);
1002  }
1003  else
1004  {
1005  /* compare the neighborhood potential to the best potential found so far */
1006  SCIP_Real potential = getPotential(scip, heurdata, sol, neighborhood, neighborhoodsize);
1007
1008  /* big potential, take this variable */
1009  if( potential > maxpotential )
1010  {
1011  maxpotential = potential;
1012  *selvar = choosevar;
1013  *selvarmaxdistance = choosevardistance;
1014  }
1015  }
1016
1017  /* sort neighborhood variables to the end so that this neighborhood is not considered in further samples */
1018  for( v = nintegralvarsleft - 1; v >= 0; --v )
1019  {
1020  SCIP_VAR* currvar;
1021  currvar = vars[v];
1022
1023  if( isVariableInNeighborhood(currvar, distances, choosevardistance) )
1024  {
1025  varscopy[v] = varscopy[nintegralvarsleft - 1];
1026  --nintegralvarsleft;
1027  }
1028  }
1029
1030  heurdata->sumdiscneighborhoodvars += ndiscvarsneighborhood;
1031  heurdata->sumneighborhoodvars += neighborhoodsize;
1032  ++heurdata->nneighborhoods;
1033
1034  /* free current neighborhood */
1035  SCIPfreeBufferArray(scip, &neighborhood);
1036  }
1037
1038  SCIPfreeBufferArray(scip, &varscopy);
1039
1040  /* maybe no variable has a positive delta */
1041  if( !SCIPisPositive(scip, maxpotential) || *selvar == NULL )
1042  {
1043  SCIPdebugMsg(scip, "Stopping with maxpotential %15.9f and selected variable %s\n",
1044  maxpotential, *selvar != NULL ? SCIPvarGetName(*selvar) : "none");
1045  *selvar = NULL;
1046  }
1047
1048  return SCIP_OKAY;
1049 }
1050
1051 /** select the next variable using the rolling horizon */
1052 static
1054  SCIP* scip, /**< SCIP data structure */
1055  SCIP_HEURDATA* heurdata, /**< heuristic data */
1056  ROLLINGHORIZON* rollinghorizon, /**< rolling horizon data structure to save relevant information, or NULL if not needed */
1057  int* distances, /**< breadth-first distances indexed by Probindex of variables */
1058  SCIP_VAR** selvar, /**< pointer to store the selected variable */
1059  int* selvarmaxdistance /**< maximal distance k to consider for selected variable neighborhood */
1060  )
1061 {
1062  SCIP_VAR** vars; /* original scip variables */
1063  int i;
1064  int nbinvars;
1065  int nintvars;
1066  int minunuseddistance;
1067
1068  assert(scip != NULL);
1069  assert(rollinghorizon != NULL);
1070  assert(distances != NULL);
1071  assert(selvar != NULL);
1072  assert(selvarmaxdistance != NULL);
1073
1074  SCIP_CALL( SCIPgetVarsData(scip, &vars, NULL, &nbinvars, &nintvars, NULL, NULL) );
1075
1076  /* loop over the variables that are left and pick the variable with
1077  * - the smallest, always nondecreasing distance
1078  * - that was not used before in a neighborhood
1079  */
1080  do
1081  {
1082  minunuseddistance = INT_MAX;
1083  *selvarmaxdistance = rollinghorizon->lastmaxdistance;
1084  *selvar = NULL;
1085  for( i = 0; i < nbinvars + nintvars && minunuseddistance > rollinghorizon->lastdistance; ++i )
1086  {
1087  if( rollinghorizon->distances[i] >= rollinghorizon->lastdistance
1088  && rollinghorizon->distances[i] < minunuseddistance && ! rollinghorizon->used[i] )
1089  {
1090  minunuseddistance = rollinghorizon->distances[i];
1091  *selvar = vars[i];
1092  }
1093  }
1094
1095  /* if no variable could be selected, we can stop */
1096  if( *selvar == NULL )
1097  {
1098  *selvarmaxdistance = 0;
1099  return SCIP_OKAY;
1100  }
1101
1102  /* determine the distances to other variables from this variable */
1103  SCIP_CALL( variablegraphBreadthFirst(scip, rollinghorizon->variablegraph, *selvar, distances, *selvarmaxdistance) );
1104
1105  SCIP_CALL( determineMaxDistance(scip, heurdata, distances, selvarmaxdistance) );
1106
1107  /* mark this variable as used in order to not find it again */
1108  if( *selvarmaxdistance == 0 )
1109  {
1110  rollinghorizon->used[SCIPvarGetProbindex(*selvar)] = TRUE;
1111  rollinghorizon->nused++;
1112  *selvar = NULL;
1113  }
1114
1115  } while( rollingHorizonRunAgain(scip, rollinghorizon, heurdata) && (*selvar == NULL || *selvarmaxdistance == 0) );
1116
1117  /* breadth-first search determines the distances of all variables
1118  * that are no more than maxdistance away from the start variable
1119  */
1120  assert(*selvarmaxdistance <= rollinghorizon->lastmaxdistance);
1121  *selvarmaxdistance = MIN(*selvarmaxdistance, rollinghorizon->lastmaxdistance);
1122  rollinghorizon->lastdistance = minunuseddistance;
1123  rollinghorizon->lastmaxdistance = *selvarmaxdistance;
1124
1125  return SCIP_OKAY;
1126 }
1127
1128 /** determines the graph-induced variable fixings */
1129 static
1131  SCIP* scip, /**< original SCIP data structure */
1132  SCIP_VAR** fixedvars, /**< buffer to store variables that should be fixed */
1133  SCIP_Real* fixedvals, /**< buffer to store fixing values for fixed variables */
1134  int* nfixings, /**< pointer to store the number of fixed variables */
1135  SCIP_HEURDATA* heurdata, /**< heuristic data */
1136  ROLLINGHORIZON* rollinghorizon, /**< rolling horizon data structure to save relevant information, or NULL if not needed */
1137  SCIP_Bool* success /**< used to store whether the creation of the subproblem worked */
1138  )
1139 {
1140  SCIP_VAR** vars;
1141  SCIP_SOL* sol; /* pool of solutions */
1142  int* distances;
1143  VARIABLEGRAPH* vargraph;
1144  SCIP_VAR* selvar;
1145  int nvars;
1146  int nbinvars;
1147  int nintvars;
1148  int fixthreshold;
1149
1150  int selvarmaxdistance;
1151
1152  assert(fixedvars != NULL);
1153  assert(fixedvals != NULL);
1154  assert(nfixings != NULL);
1155
1156  *success = TRUE;
1157  *nfixings = 0;
1158  selvarmaxdistance = 0;
1159  sol = SCIPgetBestSol(scip);
1160  assert(sol != NULL);
1161
1162  /* get required data of the original problem */
1163  SCIP_CALL( SCIPgetVarsData(scip, &vars, &nvars, &nbinvars, &nintvars, NULL, NULL) );
1164
1165  /* create variable graph */
1166  SCIPdebugMsg(scip, "Creating variable constraint graph\n");
1167
1168  /* get the saved variable graph, or create a new one */
1169  if( rollinghorizon != NULL )
1170  {
1171  if( rollinghorizon->niterations == 0 )
1172  {
1173  SCIP_CALL( variableGraphCreate(scip, &rollinghorizon->variablegraph, heurdata) );
1174  }
1175  else
1176  assert(rollinghorizon->variablegraph != NULL);
1177
1178  vargraph = rollinghorizon->variablegraph;
1179  }
1180  else
1181  {
1182  SCIP_CALL( variableGraphCreate(scip, &vargraph, heurdata) );
1183  }
1184
1185  /* allocate buffer memory to hold distances */
1186  SCIP_CALL( SCIPallocBufferArray(scip, &distances, nvars) );
1187
1188  selvar = NULL;
1189
1190  /* in the first iteration of the rolling horizon approach, we select an initial variable */
1191  if( rollinghorizon == NULL || rollinghorizon->niterations == 0 )
1192  {
1193  SCIP_CALL( selectInitialVariable(scip, heurdata, vargraph, distances, &selvar, &selvarmaxdistance) );
1194
1195  /* collect and save the distances in the rolling horizon data structure */
1196  if( selvar != NULL && rollinghorizon != NULL )
1197  {
1198  /* collect distances in the variable graph of all variables to the selected variable */
1199  SCIP_CALL( variablegraphBreadthFirst(scip, vargraph, selvar, distances, INT_MAX) );
1200  rollingHorizonStoreDistances(scip, rollinghorizon, distances);
1201  rollinghorizon->lastmaxdistance = selvarmaxdistance;
1202  }
1203  }
1204  else
1205  {
1206  /* select the next variable, if variables are left */
1207  SCIP_CALL( selectNextVariable(scip, heurdata, rollinghorizon, distances, &selvar, &selvarmaxdistance) );
1208  }
1209
1210  assert(selvar == NULL || selvarmaxdistance > 0);
1211  if( selvar == NULL )
1212  {
1213  *success = FALSE;
1214  }
1215  else
1216  {
1217  SCIPdebugMsg(scip, "Selected variable <%s> as central variable for a <%d>-neighborhood\n",
1218  SCIPvarGetName(selvar), selvarmaxdistance);
1219
1220  /* fix variables that are not in the neighborhood around the selected variable */
1221  SCIP_CALL( fixNonNeighborhoodVariables(scip, heurdata, rollinghorizon, sol, vars, fixedvars, fixedvals, distances,
1222  selvarmaxdistance, nfixings) );
1223
1224  fixthreshold = (int)(heurdata->minfixingrate * (heurdata->fixcontvars ? nvars : (nbinvars + nintvars)));
1225
1226  /* compare actual number of fixings to limit; if we fixed not enough variables we terminate here;
1227  * we also terminate if no discrete variables are left
1228  */
1229  if( *nfixings < fixthreshold )
1230  {
1231  SCIPdebugMsg(scip, "Fixed %d < %d variables in gins heuristic, stopping", *nfixings, fixthreshold);
1232  *success = FALSE;
1233  }
1234  }
1235
1236  SCIPfreeBufferArray(scip, &distances);
1237  if( rollinghorizon == NULL )
1238  variableGraphFree(scip, &vargraph);
1239
1240  return SCIP_OKAY;
1241 }
1242
1243 /** creates a new solution for the original problem by copying the solution of the subproblem */
1244 static
1246  SCIP* scip, /**< original SCIP data structure */
1247  SCIP* subscip, /**< SCIP structure of the subproblem */
1248  SCIP_VAR** subvars, /**< the variables of the subproblem */
1249  SCIP_HEUR* heur, /**< gins heuristic structure */
1250  SCIP_SOL* subsol, /**< solution of the subproblem */
1251  SCIP_Bool* success /**< used to store whether new solution was found or not */
1252  )
1253 {
1254  SCIP_VAR** vars; /* the original problem's variables */
1255  int nvars;
1256  SCIP_Real* subsolvals; /* solution values of the subproblem */
1257  SCIP_SOL* newsol; /* solution to be created for the original problem */
1258
1259  assert(scip != NULL);
1260  assert(subscip != NULL);
1261  assert(subvars != NULL);
1262  assert(subsol != NULL);
1263
1264  /* get variables' data */
1265  SCIP_CALL( SCIPgetVarsData(scip, &vars, &nvars, NULL, NULL, NULL, NULL) );
1266
1267  /* sub-SCIP may have more variables than the number of active (transformed) variables in the main SCIP
1268  * since constraint copying may have required the copy of variables that are fixed in the main SCIP
1269  */
1270  assert(nvars <= SCIPgetNOrigVars(subscip));
1271
1272  SCIP_CALL( SCIPallocBufferArray(scip, &subsolvals, nvars) );
1273
1274  /* copy the solution */
1275  SCIP_CALL( SCIPgetSolVals(subscip, subsol, nvars, subvars, subsolvals) );
1276
1277  /* create new solution for the original problem */
1278  SCIP_CALL( SCIPcreateSol(scip, &newsol, heur) );
1279  SCIP_CALL( SCIPsetSolVals(scip, newsol, nvars, vars, subsolvals) );
1280
1281  /* try to add new solution to scip and free it immediately */
1282  SCIP_CALL( SCIPtrySolFree(scip, &newsol, FALSE, FALSE, TRUE, TRUE, TRUE, success) );
1283
1284  SCIPfreeBufferArray(scip, &subsolvals);
1285
1286  return SCIP_OKAY;
1287 }
1288
1289 /** set sub-SCIP solving limits */
1290 static
1292  SCIP* subscip, /**< SCIP data structure */
1293  SOLVELIMITS* solvelimits /**< pointer to solving limits data structure */
1294  )
1295 {
1296  assert(subscip != NULL);
1297  assert(solvelimits != NULL);
1298
1299  SCIP_CALL( SCIPsetLongintParam(subscip, "limits/nodes", solvelimits->nodelimit) );
1300  SCIP_CALL( SCIPsetRealParam(subscip, "limits/time", solvelimits->timelimit) );
1301  SCIP_CALL( SCIPsetRealParam(subscip, "limits/memory", solvelimits->memorylimit) );
1302
1303  return SCIP_OKAY;
1304 }
1305
1306 /** set up the sub-SCIP */
1307 static
1309  SCIP* scip, /**< SCIP data structure */
1310  SCIP* subscip, /**< sub-SCIP data structure */
1311  SOLVELIMITS* solvelimits, /**< pointer to solving limits data structure */
1312  SCIP_HEUR* heur /**< this heuristic */
1313  )
1314 {
1315  SCIP_HEURDATA* heurdata;
1316  SCIP_Real cutoff;
1317  SCIP_Real upperbound;
1318
1319  heurdata = SCIPheurGetData(heur);
1320
1321  /* do not abort subproblem on CTRL-C */
1322  SCIP_CALL( SCIPsetBoolParam(subscip, "misc/catchctrlc", FALSE) );
1323
1324  /* disable output to console */
1325  SCIP_CALL( SCIPsetIntParam(subscip, "display/verblevel", 0) );
1326
1327  /* disable statistic timing inside sub SCIP */
1328  SCIP_CALL( SCIPsetBoolParam(subscip, "timing/statistictiming", FALSE) );
1329
1330  SCIP_CALL( SCIPsetIntParam(subscip, "limits/bestsol", heurdata->bestsollimit) );
1331
1332  /* forbid recursive call of heuristics and separators solving subMIPs */
1333  SCIP_CALL( SCIPsetSubscipsOff(subscip, TRUE) );
1334
1335  /* disable cutting plane separation */
1337
1338  /* disable expensive presolving */
1340
1341  /* use best estimate node selection */
1342  if( SCIPfindNodesel(subscip, "estimate") != NULL && !SCIPisParamFixed(subscip, "nodeselection/estimate/stdpriority") )
1343  {
1344  SCIP_CALL( SCIPsetIntParam(subscip, "nodeselection/estimate/stdpriority", INT_MAX/4) );
1345  }
1346
1347  /* use inference branching */
1348  if( SCIPfindBranchrule(subscip, "inference") != NULL && !SCIPisParamFixed(subscip, "branching/inference/priority") )
1349  {
1350  SCIP_CALL( SCIPsetIntParam(subscip, "branching/inference/priority", INT_MAX/4) );
1351  }
1352
1353  /* enable conflict analysis and restrict conflict pool */
1354  if( !SCIPisParamFixed(subscip, "conflict/enable") )
1355  {
1356  SCIP_CALL( SCIPsetBoolParam(subscip, "conflict/enable", TRUE) );
1357  }
1358  if( !SCIPisParamFixed(subscip, "conflict/maxstoresize") )
1359  {
1360  SCIP_CALL( SCIPsetIntParam(subscip, "conflict/maxstoresize", 100) );
1361  }
1362
1363  /* speed up sub-SCIP by not checking dual LP feasibility */
1364  SCIP_CALL( SCIPsetBoolParam(subscip, "lp/checkdualfeas", FALSE) );
1365
1366  /* employ a limit on the number of enforcement rounds in the quadratic constraint handlers; this fixes the issue that
1367  * sometimes the quadratic constraint handler needs hundreds or thousands of enforcement rounds to determine the
1368  * feasibility status of a single node without fractional branching candidates by separation (namely for uflquad
1369  * instances); however, the solution status of the sub-SCIP might get corrupted by this; hence no decutions shall be
1370  * made for the original SCIP
1371  */
1372  if( SCIPfindConshdlr(subscip, "quadratic") != NULL && !SCIPisParamFixed(subscip, "constraints/quadratic/enfolplimit") )
1373  {
1374  SCIP_CALL( SCIPsetIntParam(subscip, "constraints/quadratic/enfolplimit", 10) );
1375  }
1376
1377  /* add an objective cutoff */
1378  assert( !SCIPisInfinity(scip, SCIPgetUpperbound(scip)) );
1379
1380  upperbound = SCIPgetUpperbound(scip) - SCIPsumepsilon(scip);
1381  if( !SCIPisInfinity(scip, -1.0 * SCIPgetLowerbound(scip)) )
1382  {
1383  cutoff = (1 - heurdata->minimprove) * SCIPgetUpperbound(scip)
1384  + heurdata->minimprove * SCIPgetLowerbound(scip);
1385  }
1386  else
1387  {
1388  if( SCIPgetUpperbound(scip) >= 0 )
1389  cutoff = (1 - heurdata->minimprove) * SCIPgetUpperbound(scip);
1390  else
1391  cutoff = (1 + heurdata->minimprove) * SCIPgetUpperbound(scip);
1392  }
1393  cutoff = MIN(upperbound, cutoff);
1394  SCIP_CALL(SCIPsetObjlimit(subscip, cutoff));
1395
1396  /* set solve limits for sub-SCIP */
1397  SCIP_CALL( setLimits(subscip, solvelimits) );
1398
1399  return SCIP_OKAY;
1400 }
1401
1402 /** determine limits for a sub-SCIP */
1403 static
1405  SCIP* scip, /**< SCIP data structure */
1406  SCIP_HEUR* heur, /**< this heuristic */
1407  SOLVELIMITS* solvelimits, /**< pointer to solving limits data structure */
1408  SCIP_Bool* runagain /**< can we solve another sub-SCIP with these limits */
1409  )
1410 {
1411  SCIP_HEURDATA* heurdata;
1412  SCIP_Real maxnnodesr;
1413  SCIP_Longint maxnnodes;
1414  assert(scip != NULL);
1415  assert(heur != NULL);
1416  assert(solvelimits != NULL);
1417  assert(runagain != NULL);
1418
1419  heurdata = SCIPheurGetData(heur);
1420
1421  /* check whether there is enough time and memory left */
1422  SCIP_CALL( SCIPgetRealParam(scip, "limits/time", &solvelimits->timelimit) );
1423  if( !SCIPisInfinity(scip, solvelimits->timelimit) )
1424  solvelimits->timelimit -= SCIPgetSolvingTime(scip);
1425  SCIP_CALL( SCIPgetRealParam(scip, "limits/memory", &solvelimits->memorylimit) );
1426
1427  /* substract the memory already used by the main SCIP and the estimated memory usage of external software */
1428  if( !SCIPisInfinity(scip, solvelimits->memorylimit) )
1429  {
1430  solvelimits->memorylimit -= SCIPgetMemUsed(scip)/1048576.0;
1431  solvelimits->memorylimit -= SCIPgetMemExternEstim(scip)/1048576.0;
1432  }
1433
1434  /* abort if no time is left or not enough memory to create a copy of SCIP, including external memory usage */
1435  if( solvelimits->timelimit <= 0.0 || solvelimits->memorylimit <= 2.0*SCIPgetMemExternEstim(scip)/1048576.0 )
1436  *runagain = FALSE;
1437
1438  /* calculate the maximal number of branching nodes until heuristic is aborted */
1439  maxnnodesr = heurdata->nodesquot * SCIPgetNNodes(scip);
1440
1441  /* reward gins if it succeeded often, count the setup costs for the sub-MIP as 100 nodes */
1442  maxnnodesr *= 1.0 + 2.0 * (SCIPheurGetNBestSolsFound(heur)+1.0)/(heurdata->nsubmips + 1.0);
1443  maxnnodes = (SCIP_Longint)(maxnnodesr - 100.0 * heurdata->nsubmips);
1444  maxnnodes += heurdata->nodesofs;
1445
1446  /* determine the node limit for the current process */
1447  solvelimits->nodelimit = maxnnodes - heurdata->usednodes;
1448  solvelimits->nodelimit = MIN(solvelimits->nodelimit, heurdata->maxnodes);
1449
1450  /* check whether we have enough nodes left to call subproblem solving */
1451  if( solvelimits->nodelimit < heurdata->minnodes )
1452  *runagain = FALSE;
1453
1454  return SCIP_OKAY;
1455 }
1456
1457 /** updates heurdata after a run of GINS */
1458 static
1460  SCIP* scip, /**< original SCIP data structure */
1461  SCIP_HEURDATA* heurdata /**< primal heuristic data */
1462  )
1463 {
1464  /* increase number of failures, calculate next node at which GINS should be called and update actual solutions */
1465  heurdata->nfailures++;
1466  heurdata->nextnodenumber = (heurdata->nfailures <= 25
1467  ? SCIPgetNNodes(scip) + 100*(2LL << heurdata->nfailures) /*lint !e703*/
1468  : SCIP_LONGINT_MAX);
1469 }
1470
1471 #ifdef SCIP_STATISTIC
1472 /** gets the average neighborhood size of all selected variables */
1473 static
1474 SCIP_Real heurdataAvgNeighborhoodSize(
1475  SCIP_HEURDATA* heurdata /**< heuristic data */
1476  )
1477 {
1478  return heurdata->sumneighborhoodvars / (MAX(1.0, (SCIP_Real)heurdata->nneighborhoods));
1479 }
1480
1481 /** prints a histogram */
1482 static
1483 void printHistogram(
1484  SCIP* scip, /**< SCIP data structure */
1485  int* histogram, /**< histogram values */
1486  const char* name /**< display name of this histogram */
1487  )
1488 {
1489  int i;
1490
1491  SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL, "Gins: %s", name);
1492
1493  /* write out entries of this histogram */
1494  for( i = 0; i < NHISTOGRAMBINS; ++i )
1495  SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL, " %d", histogram[i]);
1497 }
1498 #endif
1499
1500 /*
1501  * Callback methods of primal heuristic
1502  */
1503
1504 /** copy method for primal heuristic plugins (called when SCIP copies plugins) */
1505 static
1506 SCIP_DECL_HEURCOPY(heurCopyGins)
1507 { /*lint --e{715}*/
1508  assert(scip != NULL);
1509  assert(heur != NULL);
1510  assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0);
1512  /* call inclusion method of primal heuristic */
1513  SCIP_CALL( SCIPincludeHeurGins(scip) );
1514
1515  return SCIP_OKAY;
1516 }
1517
1518 /** destructor of primal heuristic to free user data (called when SCIP is exiting) */
1519 static
1520 SCIP_DECL_HEURFREE(heurFreeGins)
1521 { /*lint --e{715}*/
1522  SCIP_HEURDATA* heurdata;
1523
1524  assert(heur != NULL);
1525  assert(scip != NULL);
1526
1527  /* get heuristic data */
1528  heurdata = SCIPheurGetData(heur);
1529  assert(heurdata != NULL);
1530
1531  /* free heuristic data */
1532  SCIPfreeBlockMemory(scip, &heurdata);
1533  SCIPheurSetData(heur, NULL);
1534
1535  return SCIP_OKAY;
1536 }
1537
1538 /** initialization method of primal heuristic (called after problem was transformed) */
1539 static
1540 SCIP_DECL_HEURINIT(heurInitGins)
1541 { /*lint --e{715}*/
1542  SCIP_HEURDATA* heurdata;
1543
1544  assert(heur != NULL);
1545  assert(scip != NULL);
1546
1547  /* get heuristic's data */
1548  heurdata = SCIPheurGetData(heur);
1549  assert(heurdata != NULL);
1550  assert(heurdata->randnumgen == NULL);
1551
1552  /* initialize data */
1553  heurdata->usednodes = 0;
1554  SCIP_CALL( SCIPrandomCreate(&heurdata->randnumgen, SCIPblkmem(scip), SCIPinitializeRandomSeed(scip, DEFAULT_RANDSEED)) );
1555  heurdata->sumdiscneighborhoodvars = heurdata->sumneighborhoodvars = 0;
1556  heurdata->nneighborhoods = 0;
1557  heurdata->maxseendistance = 0;
1558  heurdata->nsubmips = 0;
1559  heurdata->nfailures = 0;
1560  heurdata->nextnodenumber = 0;
1561
1562 #ifdef SCIP_STATISTIC
1563  resetHistogram(heurdata->conscontvarshist);
1564  resetHistogram(heurdata->consdiscvarshist);
1565  resetHistogram(heurdata->conscontvarshist);
1566 #endif
1567
1568  return SCIP_OKAY;
1569 }
1570
1571 /** initialization method of primal heuristic (called after problem was transformed) */
1572 static
1573 SCIP_DECL_HEUREXIT(heurExitGins)
1574 { /*lint --e{715}*/
1575  SCIP_HEURDATA* heurdata;
1576
1577  assert(heur != NULL);
1578  assert(scip != NULL);
1579
1580  /* get heuristic's data */
1581  heurdata = SCIPheurGetData(heur);
1582  assert(heurdata != NULL);
1583
1584  SCIPstatistic(
1585  SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL, "Gins: Avg Neighborhood size: %.1f Avg. discrete neighboorhood vars: %.1f\n",
1586  heurdataAvgNeighborhoodSize(heurdata), heurdataAvgDiscreteNeighborhoodSize(heurdata));
1587  SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL, "Gins: Max seen distance %d\n", heurdata->maxseendistance);
1588  printHistogram(scip, heurdata->consvarshist, "Constraint density histogram");
1589  printHistogram(scip, heurdata->conscontvarshist, "Constraint continuous density histogram");
1590  printHistogram(scip, heurdata->consdiscvarshist, "Constraint discrete density histogram");
1591  )
1592
1593  SCIPrandomFree(&heurdata->randnumgen);
1594  heurdata->randnumgen = NULL;
1595
1596  return SCIP_OKAY;
1597 }
1598
1599 /** execution method of primal heuristic */
1600 static
1601 SCIP_DECL_HEUREXEC(heurExecGins)
1602 { /*lint --e{715}*/
1603
1604  SCIP_HEURDATA* heurdata; /* heuristic's data */
1605  SCIP* subscip; /* the subproblem created by gins */
1606  SCIP_VAR** vars; /* original problem's variables */
1607  SCIP_VAR** subvars; /* subproblem's variables */
1608  SCIP_VAR** fixedvars;
1609  SCIP_Real* fixedvals;
1610  ROLLINGHORIZON* rollinghorizon; /* data structure for rolling horizon approach */
1611  SCIP_HASHMAP* varmapfw; /* mapping of SCIP variables to sub-SCIP variables */
1612
1613  int nvars; /* number of original problem's variables */
1614  int i;
1615  int nfixedvars;
1616  SOLVELIMITS solvelimits;
1617  SCIP_Bool runagain;
1618
1619  SCIP_Bool success;
1620
1621  assert(heur != NULL);
1622  assert(scip != NULL);
1623  assert(result != NULL);
1624
1625  /* get heuristic's data */
1626  heurdata = SCIPheurGetData(heur);
1627  assert(heurdata != NULL);
1628
1629  *result = SCIP_DELAYED;
1630
1631  /* only call heuristic, if feasible solution is available */
1632  if( SCIPgetNSols(scip) <= 0 )
1633  return SCIP_OKAY;
1634
1635  /* in case of many unsuccessful calls, the nextnodenumber is increased to prevent us from running too often */
1636  if( SCIPgetNNodes(scip) < heurdata->nextnodenumber )
1637  return SCIP_OKAY;
1638
1639  /* only call heuristic, if the best solution comes from transformed problem */
1640  assert(SCIPgetBestSol(scip) != NULL);
1641  if( SCIPsolIsOriginal(SCIPgetBestSol(scip)) )
1642  return SCIP_OKAY;
1643
1644  /* only call heuristic, if enough nodes were processed since last incumbent */
1645  if( SCIPgetNNodes(scip) - SCIPgetSolNodenum(scip,SCIPgetBestSol(scip)) < heurdata->nwaitingnodes )
1646  return SCIP_OKAY;
1647
1648  *result = SCIP_DIDNOTRUN;
1649
1650  /* only call heuristic, if discrete variables are present */
1651  if( SCIPgetNBinVars(scip) == 0 && SCIPgetNIntVars(scip) == 0 )
1652  return SCIP_OKAY;
1653
1654  if( SCIPisStopped(scip) )
1655  return SCIP_OKAY;
1656
1657  runagain = TRUE;
1658
1659  /* determine solving limits for the sub-SCIP for the first time */
1660  SCIP_CALL( determineLimits(scip, heur, &solvelimits, &runagain) );
1661
1662  if( ! runagain )
1663  return SCIP_OKAY;
1664
1665  *result = SCIP_DIDNOTFIND;
1666
1667  SCIP_CALL( SCIPgetVarsData(scip, &vars, &nvars, NULL, NULL, NULL, NULL) );
1668  SCIP_CALL( SCIPallocBufferArray(scip, &fixedvars, nvars) );
1669  SCIP_CALL( SCIPallocBufferArray(scip, &fixedvals, nvars) );
1670
1671  /* only create a rolling horizon data structure if we need to keep it */
1672  if( heurdata->userollinghorizon )
1673  SCIP_CALL( rollingHorizonCreate(scip, &rollinghorizon) );
1674  else
1675  rollinghorizon = NULL;
1676
1677  do
1678  {
1679  /* create a new problem, by fixing all variables except for a small neighborhood */
1680  SCIP_CALL( determineVariableFixings(scip, fixedvars, fixedvals, &nfixedvars, heurdata, rollinghorizon, &success) );
1681
1682  /* terminate if it was not possible to create the subproblem */
1683  if( !success )
1684  {
1685  SCIPdebugMsg(scip, "Could not create the subproblem -> skip call\n");
1686
1687  /* do not count this as a call to the heuristic */
1688  *result = SCIP_DIDNOTRUN;
1689
1690  /* count this as a failure and increase the number of waiting nodes until the next call */
1691  updateFailureStatistic(scip, heurdata);
1692  goto TERMINATE;
1693  }
1694
1695  /* initializing the subproblem */
1696  SCIP_CALL( SCIPallocBufferArray(scip, &subvars, nvars) );
1697  SCIP_CALL( SCIPcreate(&subscip) );
1698  ++heurdata->nsubmips;
1699
1700  /* create the variable mapping hash map */
1701  SCIP_CALL( SCIPhashmapCreate(&varmapfw, SCIPblkmem(subscip), nvars) );
1702
1703  /* create a problem copy as sub SCIP */
1704  SCIP_CALL( SCIPcopyLargeNeighborhoodSearch(scip, subscip, varmapfw, "gins", fixedvars, fixedvals, nfixedvars,
1705  heurdata->uselprows, heurdata->copycuts, &success, NULL) );
1706
1707  for( i = 0; i < nvars; i++ )
1708  subvars[i] = (SCIP_VAR*) SCIPhashmapGetImage(varmapfw, vars[i]);
1709
1710  /* free hash map */
1711  SCIPhashmapFree(&varmapfw);
1712
1713  /* set up limits for the subproblem */
1714  SCIP_CALL( setupSubScip(scip, subscip, &solvelimits, heur) );
1715
1716  /* solve the subproblem */
1717  SCIPdebugMsg(scip, "Solve Gins subMIP\n");
1718
1719  /* Errors in solving the subproblem should not kill the overall solving process
1720  * Hence, the return code is caught and a warning is printed, only in debug mode, SCIP will stop.
1721  */
1722  SCIP_CALL_ABORT( SCIPsolve(subscip) );
1723
1724  /* transfer variable statistics from sub-SCIP */
1725  SCIP_CALL( SCIPmergeVariableStatistics(subscip, scip, subvars, vars, nvars) );
1726
1727  heurdata->usednodes += SCIPgetNNodes(subscip);
1728
1729  /* check, whether a solution was found */
1730  if( SCIPgetNSols(subscip) > 0 )
1731  {
1732  SCIP_SOL** subsols;
1733  int nsubsols;
1734
1735  /* check, whether a solution was found;
1736  * due to numerics, it might happen that not all solutions are feasible -> try all solutions until one was accepted
1737  */
1738  nsubsols = SCIPgetNSols(subscip);
1739  subsols = SCIPgetSols(subscip);
1740  success = FALSE;
1741  for( i = 0; i < nsubsols && !success; ++i )
1742  {
1743  SCIP_CALL( createNewSol(scip, subscip, subvars, heur, subsols[i], &success) );
1744  }
1745  if( success )
1746  *result = SCIP_FOUNDSOL;
1747  }
1748
1749  /* free subproblem */
1750  SCIPfreeBufferArray(scip, &subvars);
1751  SCIP_CALL( SCIPfree(&subscip) );
1752
1753  /* check if we want to run another rolling horizon iteration */
1754  runagain = (*result == SCIP_FOUNDSOL) && heurdata->userollinghorizon;
1755  if( runagain )
1756  {
1757  assert(rollinghorizon != NULL);
1758  SCIP_CALL( determineLimits(scip, heur, &solvelimits, &runagain ) );
1759  runagain = runagain && rollingHorizonRunAgain(scip, rollinghorizon, heurdata);
1760  }
1761
1762  } while( runagain );
1763
1764  /* delay the heuristic in case it was not successful */
1765  if( *result != SCIP_FOUNDSOL )
1766  updateFailureStatistic(scip, heurdata);
1767
1768 TERMINATE:
1769
1770  /* only free the rolling horizon data structure if we need to keep it */
1771  if( heurdata->userollinghorizon )
1772  {
1773  SCIP_CALL( rollingHorizonFree(scip, &rollinghorizon) );
1774  }
1775
1776  SCIPfreeBufferArray(scip, &fixedvals);
1777  SCIPfreeBufferArray(scip, &fixedvars);
1778
1779  return SCIP_OKAY;
1780 }
1781
1782 /*
1783  * primal heuristic specific interface methods
1784  */
1785
1786 /** creates the gins primal heuristic and includes it in SCIP */
1788  SCIP* scip /**< SCIP data structure */
1789  )
1790 {
1791  SCIP_HEURDATA* heurdata;
1792  SCIP_HEUR* heur;
1793
1794  /* create Gins primal heuristic data */
1795  SCIP_CALL( SCIPallocBlockMemory(scip, &heurdata) );
1796  heurdata->randnumgen = NULL;
1797
1798  /* include primal heuristic */
1799  SCIP_CALL( SCIPincludeHeurBasic(scip, &heur,
1801  HEUR_MAXDEPTH, HEUR_TIMING, HEUR_USESSUBSCIP, heurExecGins, heurdata) );
1802
1803  assert(heur != NULL);
1804
1805  /* set non-NULL pointers to callback methods */
1806  SCIP_CALL( SCIPsetHeurCopy(scip, heur, heurCopyGins) );
1807  SCIP_CALL( SCIPsetHeurFree(scip, heur, heurFreeGins) );
1808  SCIP_CALL( SCIPsetHeurInit(scip, heur, heurInitGins) );
1809  SCIP_CALL( SCIPsetHeurExit(scip, heur, heurExitGins) );
1810
1811  /* add gins primal heuristic parameters */
1812  SCIP_CALL( SCIPaddIntParam(scip, "heuristics/" HEUR_NAME "/nodesofs",
1813  "number of nodes added to the contingent of the total nodes",
1814  &heurdata->nodesofs, FALSE, DEFAULT_NODESOFS, 0, INT_MAX, NULL, NULL) );
1815
1816  SCIP_CALL( SCIPaddIntParam(scip, "heuristics/" HEUR_NAME "/maxnodes",
1817  "maximum number of nodes to regard in the subproblem",
1818  &heurdata->maxnodes, TRUE, DEFAULT_MAXNODES, 0, INT_MAX, NULL, NULL) );
1819
1820  SCIP_CALL( SCIPaddIntParam(scip, "heuristics/" HEUR_NAME "/minnodes",
1821  "minimum number of nodes required to start the subproblem",
1822  &heurdata->minnodes, TRUE, DEFAULT_MINNODES, 0, INT_MAX, NULL, NULL) );
1823
1824  SCIP_CALL( SCIPaddIntParam(scip, "heuristics/" HEUR_NAME "/nwaitingnodes",
1825  "number of nodes without incumbent change that heuristic should wait",
1826  &heurdata->nwaitingnodes, TRUE, DEFAULT_NWAITINGNODES, 0, INT_MAX, NULL, NULL) );
1827
1828  SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/nodesquot",
1829  "contingent of sub problem nodes in relation to the number of nodes of the original problem",
1830  &heurdata->nodesquot, FALSE, DEFAULT_NODESQUOT, 0.0, 1.0, NULL, NULL) );
1831
1832  SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/minfixingrate",
1833  "percentage of integer variables that have to be fixed",
1834  &heurdata->minfixingrate, FALSE, DEFAULT_MINFIXINGRATE, SCIPsumepsilon(scip), 1.0-SCIPsumepsilon(scip), NULL, NULL) );
1835
1836  SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/minimprove",
1837  "factor by which " HEUR_NAME " should at least improve the incumbent",
1838  &heurdata->minimprove, TRUE, DEFAULT_MINIMPROVE, 0.0, 1.0, NULL, NULL) );
1839
1840  SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/uselprows",
1841  "should subproblem be created out of the rows in the LP rows?",
1842  &heurdata->uselprows, TRUE, DEFAULT_USELPROWS, NULL, NULL) );
1843
1844  SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/copycuts",
1845  "if uselprows == FALSE, should all active cuts from cutpool be copied to constraints in subproblem?",
1846  &heurdata->copycuts, TRUE, DEFAULT_COPYCUTS, NULL, NULL) );
1847
1848  SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/fixcontvars",
1849  "should continuous variables outside the neighborhoods be fixed?",
1850  &heurdata->fixcontvars, TRUE, DEFAULT_FIXCONTVARS, NULL, NULL) );
1851
1852  SCIP_CALL( SCIPaddIntParam(scip, "heuristics/" HEUR_NAME "/bestsollimit",
1853  "limit on number of improving incumbent solutions in sub-CIP",
1854  &heurdata->bestsollimit, FALSE, DEFAULT_BESTSOLLIMIT, -1, INT_MAX, NULL, NULL) );
1855
1856  SCIP_CALL( SCIPaddIntParam(scip, "heuristics/" HEUR_NAME "/maxdistance",
1857  "maximum distance to selected variable to enter the subproblem, or -1 to select the distance "
1858  "that best approximates the minimum fixing rate from below",
1859  &heurdata->maxdistance, FALSE, DEFAULT_MAXDISTANCE, -1, INT_MAX, NULL, NULL) );
1860
1861  SCIP_CALL( SCIPaddCharParam(scip, "heuristics/" HEUR_NAME "/potential",
1862  "the reference point to compute the neighborhood potential: (r)oot or (p)seudo solution",
1863  &heurdata->potential, TRUE, DEFAULT_POTENTIAL, "pr", NULL, NULL) );
1864
1865  SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/userollinghorizon",
1866  "should the heuristic solve a sequence of sub-MIP's around the first selected variable",
1867  &heurdata->userollinghorizon, TRUE, DEFAULT_USEROLLINGHORIZON, NULL, NULL) );
1868
1869  SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/relaxdenseconss",
1870  "should dense constraints (at least as dense as 1 - minfixingrate) be ignored by connectivity graph?",
1871  &heurdata->relaxdenseconss, TRUE, DEFAULT_RELAXDENSECONSS, NULL, NULL) );
1872
1873  SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/rollhorizonlimfac",
1874  "limiting percentage for variables already used in sub-SCIPs to terminate rolling horizon approach",
1875  &heurdata->rollhorizonlimfac, TRUE, DEFAULT_ROLLHORIZONLIMFAC, 0.0, 1.0, NULL, NULL) );
1876
1877  return SCIP_OKAY;
1878 }
SCIP_Bool SCIPsolIsOriginal(SCIP_SOL *sol)
Definition: sol.c:2299
static SCIP_Real heurdataAvgDiscreteNeighborhoodSize(SCIP_HEURDATA *heurdata)
Definition: heur_gins.c:859
#define SCIPfreeBlockMemoryArray(scip, ptr, num)
Definition: scip.h:21909
int SCIPgetNIntVars(SCIP *scip)
Definition: scip.c:11721
static SCIP_RETCODE rollingHorizonCreate(SCIP *scip, ROLLINGHORIZON **rollinghorizon)
Definition: heur_gins.c:562
#define SCIPreallocBlockMemoryArray(scip, ptr, oldnum, newnum)
Definition: scip.h:21898
SCIP_RETCODE SCIPrandomCreate(SCIP_RANDNUMGEN **randnumgen, BMS_BLKMEM *blkmem, unsigned int initialseed)
Definition: misc.c:8693
SCIP_Real SCIPgetSolvingTime(SCIP *scip)
Definition: scip.c:45137
SCIP_RETCODE SCIPsetSeparating(SCIP *scip, SCIP_PARAMSETTING paramsetting, SCIP_Bool quiet)
Definition: scip.c:5095
#define SCIPallocBlockMemoryArray(scip, ptr, num)
Definition: scip.h:21892
SCIP_RETCODE SCIPincludeHeurGins(SCIP *scip)
Definition: heur_gins.c:1792
static void rollingHorizonStoreDistances(SCIP *scip, ROLLINGHORIZON *rollinghorizon, int *distances)
Definition: heur_gins.c:626
static SCIP_DECL_HEURCOPY(heurCopyGins)
Definition: heur_gins.c:1511
SCIP_RETCODE SCIPhashtableInsert(SCIP_HASHTABLE *hashtable, void *element)
Definition: misc.c:2254
#define DEFAULT_MAXDISTANCE
Definition: heur_gins.c:75
SCIP_CONSHDLR * SCIPfindConshdlr(SCIP *scip, const char *name)
Definition: scip.c:6541
#define SCIPallocClearBufferArray(scip, ptr, num)
Definition: scip.h:21927
#define HEUR_FREQ
Definition: heur_gins.c:53
#define DEFAULT_NODESOFS
Definition: heur_gins.c:59
SCIP_Real SCIPvarGetLbGlobal(SCIP_VAR *var)
Definition: var.c:17166
SCIP_RETCODE SCIPgetRealParam(SCIP *scip, const char *name, SCIP_Real *value)
Definition: scip.c:4426
SCIP_HASHTABLE * visitedconss
Definition: heur_gins.c:100
SCIP_Longint SCIPheurGetNBestSolsFound(SCIP_HEUR *heur)
Definition: heur.c:1327
#define SCIPallocClearBlockMemoryArray(scip, ptr, num)
Definition: scip.h:21896
static SCIP_RETCODE fillVariableGraph(SCIP *scip, VARIABLEGRAPH *vargraph, SCIP_HEURDATA *heurdata)
Definition: heur_gins.c:218
SCIP_RETCODE SCIPsetHeurExit(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEUREXIT((*heurexit)))
Definition: scip.c:8092
int SCIPcalcMemGrowSize(SCIP *scip, int num)
Definition: scip.c:45601
SCIP_Bool SCIPisPositive(SCIP *scip, SCIP_Real val)
Definition: scip.c:45876
int SCIPgetNOrigVars(SCIP *scip)
Definition: scip.c:12071
static SCIP_RETCODE selectNextVariable(SCIP *scip, SCIP_HEURDATA *heurdata, ROLLINGHORIZON *rollinghorizon, int *distances, SCIP_VAR **selvar, int *selvarmaxdistance)
Definition: heur_gins.c:1058
SCIP_Real SCIPvarGetRootSol(SCIP_VAR *var)
Definition: var.c:12654
SCIP_RETCODE SCIPgetVarsData(SCIP *scip, SCIP_VAR ***vars, int *nvars, int *nbinvars, int *nintvars, int *nimplvars, int *ncontvars)
Definition: scip.c:11505
SCIP_SOL ** SCIPgetSols(SCIP *scip)
Definition: scip.c:38881
#define FALSE
Definition: def.h:64
SCIP_RETCODE SCIPhashmapCreate(SCIP_HASHMAP **hashmap, BMS_BLKMEM *blkmem, int mapsize)
Definition: misc.c:2765
static SCIP_RETCODE determineVariableFixings(SCIP *scip, SCIP_VAR **fixedvars, SCIP_Real *fixedvals, int *nfixings, SCIP_HEURDATA *heurdata, ROLLINGHORIZON *rollinghorizon, SCIP_Bool *success)
Definition: heur_gins.c:1135
static SCIP_RETCODE setLimits(SCIP *subscip, SOLVELIMITS *solvelimits)
Definition: heur_gins.c:1296
#define TRUE
Definition: def.h:63
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:53
SCIP_RETCODE SCIPsetPresolving(SCIP *scip, SCIP_PARAMSETTING paramsetting, SCIP_Bool quiet)
Definition: scip.c:5069
SCIP_BRANCHRULE * SCIPfindBranchrule(SCIP *scip, const char *name)
Definition: scip.c:9184
#define DEFAULT_MAXNODES
Definition: heur_gins.c:60
int SCIPvarGetProbindex(SCIP_VAR *var)
Definition: var.c:16859
#define DEFAULT_MINFIXINGRATE
Definition: heur_gins.c:63
struct SCIP_HeurData SCIP_HEURDATA
Definition: type_heur.h:51
#define HEUR_DISPCHAR
Definition: heur_gins.c:51
#define SCIPfreeBlockMemory(scip, ptr)
Definition: scip.h:21907
SCIP_RETCODE SCIPincludeHeurBasic(SCIP *scip, SCIP_HEUR **heur, const char *name, const char *desc, char dispchar, int priority, int freq, int freqofs, int maxdepth, SCIP_HEURTIMING timingmask, SCIP_Bool usessubscip, SCIP_DECL_HEUREXEC((*heurexec)), SCIP_HEURDATA *heurdata)
Definition: scip.c:7999
SCIP_Real timelimit
Definition: heur_gins.c:176
int SCIPrandomGetInt(SCIP_RANDNUMGEN *randnumgen, int minrandval, int maxrandval)
Definition: misc.c:8723
#define SCIPduplicateBufferArray(scip, ptr, source, num)
Definition: scip.h:21933
SCIP_CONS ** SCIPgetConss(SCIP *scip)
Definition: scip.c:12725
void * SCIPhashmapGetImage(SCIP_HASHMAP *hashmap, void *origin)
Definition: misc.c:2903
#define SCIP_LONGINT_MAX
Definition: def.h:121
#define SCIPfreeBufferArray(scip, ptr)
Definition: scip.h:21937
SCIP_RETCODE SCIPcreate(SCIP **scip)
Definition: scip.c:696
void SCIPheurSetData(SCIP_HEUR *heur, SCIP_HEURDATA *heurdata)
Definition: heur.c:1102
#define SCIPallocBlockMemory(scip, ptr)
Definition: scip.h:21890
static SCIP_RETCODE determineMaxDistance(SCIP *scip, SCIP_HEURDATA *heurdata, int *distances, int *choosevardistance)
Definition: heur_gins.c:803
SCIP_RETCODE SCIPsetRealParam(SCIP *scip, const char *name, SCIP_Real value)
Definition: scip.c:4741
#define SCIPdebugMsg
Definition: scip.h:451
SCIP_RETCODE SCIPaddIntParam(SCIP *scip, const char *name, const char *desc, int *valueptr, SCIP_Bool isadvanced, int defaultvalue, int minvalue, int maxvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition: scip.c:4202
#define DEFAULT_ROLLHORIZONLIMFAC
Definition: heur_gins.c:83
int SCIPgetNContVars(SCIP *scip)
Definition: scip.c:11811
int lastmaxdistance
Definition: heur_gins.c:116
SCIP_RETCODE SCIPhashtableCreate(SCIP_HASHTABLE **hashtable, BMS_BLKMEM *blkmem, int tablesize, SCIP_DECL_HASHGETKEY((*hashgetkey)), SCIP_DECL_HASHKEYEQ((*hashkeyeq)), SCIP_DECL_HASHKEYVAL((*hashkeyval)), void *userptr)
Definition: misc.c:2015
SCIP_Real SCIPvarGetUbGlobal(SCIP_VAR *var)
Definition: var.c:17176
void SCIPrandomFree(SCIP_RANDNUMGEN **randnumgen)
Definition: misc.c:8710
SCIP_Real memorylimit
Definition: heur_gins.c:175
SCIP_RETCODE SCIPsolve(SCIP *scip)
Definition: scip.c:15777
#define HEUR_NAME
Definition: heur_gins.c:49
const char * SCIPheurGetName(SCIP_HEUR *heur)
Definition: heur.c:1181
#define DEFAULT_FIXCONTVARS
Definition: heur_gins.c:73
#define DEFAULT_USEROLLINGHORIZON
Definition: heur_gins.c:82
#define SCIPerrorMessage
Definition: pub_message.h:45
SCIP_Bool SCIPisParamFixed(SCIP *scip, const char *name)
Definition: scip.c:4338
SCIP_RETCODE SCIPgetConsNVars(SCIP *scip, SCIP_CONS *cons, int *nvars, SCIP_Bool *success)
Definition: scip.c:28737
SCIP_RETCODE SCIPsetHeurFree(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURFREE((*heurfree)))
Definition: scip.c:8060
SCIP_Bool SCIPisLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip.c:45764
SCIP_RETCODE SCIPgetSolVals(SCIP *scip, SCIP_SOL *sol, int nvars, SCIP_VAR **vars, SCIP_Real *vals)
Definition: scip.c:38044
static void updateFailureStatistic(SCIP *scip, SCIP_HEURDATA *heurdata)
Definition: heur_gins.c:1464
static void variableGraphFree(SCIP *scip, VARIABLEGRAPH **vargraph)
Definition: heur_gins.c:380
static SCIP_RETCODE variableGraphCreate(SCIP *scip, VARIABLEGRAPH **vargraph, SCIP_HEURDATA *heurdata)
Definition: heur_gins.c:344
SCIP_RETCODE SCIPsetBoolParam(SCIP *scip, const char *name, SCIP_Bool value)
Definition: scip.c:4567
BMS_BLKMEM * SCIPblkmem(SCIP *scip)
Definition: scip.c:45519
const char * SCIPvarGetName(SCIP_VAR *var)
Definition: var.c:16552
void SCIPhashmapFree(SCIP_HASHMAP **hashmap)
Definition: misc.c:2798
SCIP_RETCODE SCIPmergeVariableStatistics(SCIP *sourcescip, SCIP *targetscip, SCIP_VAR **sourcevars, SCIP_VAR **targetvars, int nvars)
Definition: scip.c:2419
LNS heuristic that tries to delimit the search region to a neighborhood in the constraint graph...
#define NULL
Definition: lpi_spx1.cpp:137
static SCIP_RETCODE setupSubScip(SCIP *scip, SCIP *subscip, SOLVELIMITS *solvelimits, SCIP_HEUR *heur)
Definition: heur_gins.c:1313
#define DEFAULT_RELAXDENSECONSS
Definition: heur_gins.c:79
#define REALABS(x)
Definition: def.h:159
#define SCIP_CALL(x)
Definition: def.h:306
SCIP_Real SCIPgetLowerbound(SCIP *scip)
Definition: scip.c:42323
#define HEUR_FREQOFS
Definition: heur_gins.c:54
#define DEFAULT_POTENTIAL
Definition: heur_gins.c:74
static SCIP_DECL_HEURFREE(heurFreeGins)
Definition: heur_gins.c:1525
#define DEFAULT_NODESQUOT
Definition: heur_gins.c:64
void SCIPhashtableRemoveAll(SCIP_HASHTABLE *hashtable)
Definition: misc.c:2462
SCIP_Longint nodelimit
Definition: heur_gins.c:174
void SCIPverbMessage(SCIP *scip, SCIP_VERBLEVEL msgverblevel, FILE *file, const char *formatstr,...)
Definition: scip.c:1353
static SCIP_DECL_HEUREXEC(heurExecGins)
Definition: heur_gins.c:1606
SCIP_Bool SCIPsortedvecFindInt(int *intarray, int val, int len, int *pos)
SCIP_RETCODE SCIPgetConsVars(SCIP *scip, SCIP_CONS *cons, SCIP_VAR **vars, int varssize, SCIP_Bool *success)
Definition: scip.c:28693
#define DEFAULT_BESTSOLLIMIT
Definition: heur_gins.c:72
#define DEFAULT_MINNODES
Definition: heur_gins.c:62
#define SCIPallocBufferArray(scip, ptr, num)
Definition: scip.h:21925
#define DEFAULT_USELPROWS
Definition: heur_gins.c:66
public data structures and miscellaneous methods
#define SCIP_Bool
Definition: def.h:61
VARIABLEGRAPH * variablegraph
Definition: heur_gins.c:111
SCIP_RETCODE SCIPsetObjlimit(SCIP *scip, SCIP_Real objlimit)
Definition: scip.c:11078
#define DEFAULT_COPYCUTS
Definition: heur_gins.c:69
#define MAX(x, y)
Definition: tclique_def.h:75
SCIP_RETCODE SCIPtrySolFree(SCIP *scip, SCIP_SOL **sol, SCIP_Bool printreason, SCIP_Bool completely, SCIP_Bool checkbounds, SCIP_Bool checkintegrality, SCIP_Bool checklprows, SCIP_Bool *stored)
Definition: scip.c:39843
static SCIP_Bool rollingHorizonRunAgain(SCIP *scip, ROLLINGHORIZON *rollinghorizon, SCIP_HEURDATA *heurdata)
Definition: heur_gins.c:609
SCIP_RETCODE SCIPsetIntParam(SCIP *scip, const char *name, int value)
Definition: scip.c:4625
unsigned int SCIPinitializeRandomSeed(SCIP *scip, int initialseedvalue)
Definition: scip.c:25467
SCIP_Bool SCIPconsIsChecked(SCIP_CONS *cons)
Definition: cons.c:8080
SCIP_Real SCIPvarGetObj(SCIP_VAR *var)
Definition: var.c:17014
int SCIPgetNSols(SCIP *scip)
Definition: scip.c:38832
#define BMScopyMemoryArray(ptr, source, num)
Definition: memory.h:89
#define HEUR_PRIORITY
Definition: heur_gins.c:52
static SCIP_RETCODE variablegraphBreadthFirst(SCIP *scip, VARIABLEGRAPH *vargraph, SCIP_VAR *startvar, int *distances, int maxdistance)
Definition: heur_gins.c:411
SCIP_Bool SCIPisInfinity(SCIP *scip, SCIP_Real val)
Definition: scip.c:45827
int SCIPgetNBinVars(SCIP *scip)
Definition: scip.c:11676
void SCIPhashtableFree(SCIP_HASHTABLE **hashtable)
Definition: misc.c:2065
int SCIPgetNVars(SCIP *scip)
Definition: scip.c:11631
#define HEUR_TIMING
Definition: heur_gins.c:56
#define SCIP_REAL_MIN
Definition: def.h:137
static SCIP_DECL_HEURINIT(heurInitGins)
Definition: heur_gins.c:1545
static SCIP_RETCODE determineLimits(SCIP *scip, SCIP_HEUR *heur, SOLVELIMITS *solvelimits, SCIP_Bool *runagain)
Definition: heur_gins.c:1409
SCIP_SOL * SCIPgetBestSol(SCIP *scip)
Definition: scip.c:38931
SCIP_Bool SCIPisGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip.c:45790
SCIP_RETCODE SCIPaddCharParam(SCIP *scip, const char *name, const char *desc, char *valueptr, SCIP_Bool isadvanced, char defaultvalue, const char *allowedvalues, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition: scip.c:4286
SCIP_Longint SCIPgetMemUsed(SCIP *scip)
Definition: scip.c:45562
static SCIP_RETCODE createNewSol(SCIP *scip, SCIP *subscip, SCIP_VAR **subvars, SCIP_HEUR *heur, SCIP_SOL *subsol, SCIP_Bool *success)
Definition: heur_gins.c:1250
#define DEFAULT_MINIMPROVE
Definition: heur_gins.c:61
int SCIPgetNConss(SCIP *scip)
Definition: scip.c:12679
static SCIP_RETCODE fixNonNeighborhoodVariables(SCIP *scip, SCIP_HEURDATA *heurdata, ROLLINGHORIZON *rollinghorizon, SCIP_SOL *sol, SCIP_VAR **vars, SCIP_VAR **fixedvars, SCIP_Real *fixedvals, int *distances, int maxdistance, int *nfixings)
Definition: heur_gins.c:730
int * nvarconss
Definition: heur_gins.c:101
int * distances
Definition: heur_gins.c:112
SCIP_RETCODE SCIPsetHeurInit(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURINIT((*heurinit)))
Definition: scip.c:8076
SCIP_Longint SCIPgetMemExternEstim(SCIP *scip)
Definition: scip.c:45588
SCIP_NODESEL * SCIPfindNodesel(SCIP *scip, const char *name)
Definition: scip.c:8872
SCIP_RETCODE SCIPcopyLargeNeighborhoodSearch(SCIP *sourcescip, SCIP *subscip, SCIP_HASHMAP *varmap, const char *suffix, SCIP_VAR **fixedvars, SCIP_Real *fixedvals, int nfixedvars, SCIP_Bool uselprows, SCIP_Bool copycuts, SCIP_Bool *success, SCIP_Bool *valid)
Definition: heuristics.c:899
SCIP_VAR ** SCIPgetVars(SCIP *scip)
Definition: scip.c:11586
#define SCIPstatistic(x)
Definition: pub_message.h:101
#define SCIP_Real
Definition: def.h:135
SCIP_Bool SCIPisStopped(SCIP *scip)
Definition: scip.c:1138
#define MIN(x, y)
Definition: memory.c:75
void SCIPsortInt(int *intarray, int len)
static SCIP_DECL_HEUREXIT(heurExitGins)
Definition: heur_gins.c:1578
#define SCIP_Longint
Definition: def.h:120
static SCIP_Real getPotential(SCIP *scip, SCIP_HEURDATA *heurdata, SCIP_SOL *sol, SCIP_VAR **vars, int nvars)
Definition: heur_gins.c:649
SCIP_CONS *** varconss
Definition: heur_gins.c:99
SCIP_Bool SCIPhashtableExists(SCIP_HASHTABLE *hashtable, void *element)
Definition: misc.c:2366
SCIP_RETCODE SCIPsetSolVals(SCIP *scip, SCIP_SOL *sol, int nvars, SCIP_VAR **vars, SCIP_Real *vals)
Definition: scip.c:37909
SCIP_Bool SCIPisZero(SCIP *scip, SCIP_Real val)
Definition: scip.c:45864
SCIP_Bool SCIPisLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip.c:45777
static SCIP_RETCODE rollingHorizonFree(SCIP *scip, ROLLINGHORIZON **rollinghorizon)
Definition: heur_gins.c:586
#define HEUR_MAXDEPTH
Definition: heur_gins.c:55
static SCIP_RETCODE selectInitialVariable(SCIP *scip, SCIP_HEURDATA *heurdata, VARIABLEGRAPH *vargraph, int *distances, SCIP_VAR **selvar, int *selvarmaxdistance)
Definition: heur_gins.c:868
SCIP_RETCODE SCIPsetHeurCopy(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURCOPY((*heurcopy)))
Definition: scip.c:8044
#define SCIPfreeBlockMemoryArrayNull(scip, ptr, num)
Definition: scip.h:21910
SCIP_Real SCIPsumepsilon(SCIP *scip)
Definition: scip.c:45260
SCIP_Real SCIPgetUpperbound(SCIP *scip)
Definition: scip.c:42472
#define BMSclearMemoryArray(ptr, num)
Definition: memory.h:85
int * varconssize
Definition: heur_gins.c:102
#define DEFAULT_NWAITINGNODES
Definition: heur_gins.c:65
#define SCIP_CALL_ABORT(x)
Definition: def.h:285
SCIP_HEURDATA * SCIPheurGetData(SCIP_HEUR *heur)
Definition: heur.c:1092
SCIP_Bool * used
Definition: heur_gins.c:114
SCIP_Longint SCIPgetNNodes(SCIP *scip)
Definition: scip.c:41182
#define HEUR_DESC
Definition: heur_gins.c:50
SCIP_Bool SCIPvarIsIntegral(SCIP_VAR *var)
Definition: var.c:16743
static SCIP_Bool isVariableInNeighborhood(SCIP_VAR *var, int *distances, int maxdistance)
Definition: heur_gins.c:714
#define HEUR_USESSUBSCIP
Definition: heur_gins.c:57
SCIP_Real SCIPgetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var)
Definition: scip.c:38007
default SCIP plugins
SCIP_RETCODE SCIPaddRealParam(SCIP *scip, const char *name, const char *desc, SCIP_Real *valueptr, SCIP_Bool isadvanced, SCIP_Real defaultvalue, SCIP_Real minvalue, SCIP_Real maxvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition: scip.c:4258
SCIP_RETCODE SCIPsetSubscipsOff(SCIP *scip, SCIP_Bool quiet)
Definition: scip.c:5020
SCIP_RETCODE SCIPsetLongintParam(SCIP *scip, const char *name, SCIP_Longint value)
Definition: scip.c:4683
SCIP callable library.
SCIP_RETCODE SCIPaddBoolParam(SCIP *scip, const char *name, const char *desc, SCIP_Bool *valueptr, SCIP_Bool isadvanced, SCIP_Bool defaultvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition: scip.c:4176
SCIP_Bool SCIPvarIsActive(SCIP_VAR *var)
Definition: var.c:16839
SCIP_RETCODE SCIPfree(SCIP **scip)
Definition: scip.c:774
#define DEFAULT_RANDSEED
Definition: heur_gins.c:78
SCIP_RETCODE SCIPcreateSol(SCIP *scip, SCIP_SOL **sol, SCIP_HEUR *heur)
Definition: scip.c:37005
SCIP_Longint SCIPgetSolNodenum(SCIP *scip, SCIP_SOL *sol)
Definition: scip.c:38303