# 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 /* */
7 /* fuer Informationstechnik Berlin */
8 /* */
10 /* */
12 /* along with SCIP; see the file COPYING. If not visit 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 "blockmemshell/memory.h"
43 #include "scip/heur_gins.h"
44 #include "scip/heuristics.h"
45 #include "scip/pub_heur.h"
46 #include "scip/pub_message.h"
47 #include "scip/pub_misc.h"
48 #include "scip/pub_misc_sort.h"
49 #include "scip/pub_sol.h"
50 #include "scip/pub_var.h"
51 #include "scip/scip_branch.h"
52 #include "scip/scip_cons.h"
53 #include "scip/scip_copy.h"
54 #include "scip/scip_general.h"
55 #include "scip/scip_heur.h"
56 #include "scip/scip_mem.h"
57 #include "scip/scip_message.h"
58 #include "scip/scip_nodesel.h"
59 #include "scip/scip_numerics.h"
60 #include "scip/scip_param.h"
61 #include "scip/scip_prob.h"
62 #include "scip/scip_randnumgen.h"
63 #include "scip/scip_sol.h"
64 #include "scip/scip_solve.h"
65 #include "scip/scip_solvingstats.h"
66 #include "scip/scip_timing.h"
67 #include <string.h>
68
69 #define HEUR_NAME "gins"
70 #define HEUR_DESC "gins works on k-neighborhood in a variable-constraint graph"
71 #define HEUR_DISPCHAR 'K'
72 #define HEUR_PRIORITY -1103000
73 #define HEUR_FREQ 20
74 #define HEUR_FREQOFS 8
75 #define HEUR_MAXDEPTH -1
76 #define HEUR_TIMING SCIP_HEURTIMING_AFTERNODE
77 #define HEUR_USESSUBSCIP TRUE /**< does the heuristic use a secondary SCIP instance? */
78
79 #define DEFAULT_NODESOFS 500 /**< number of nodes added to the contingent of the total nodes */
80 #define DEFAULT_MAXNODES 5000 /**< maximum number of nodes to regard in the subproblem */
81 #define DEFAULT_MINIMPROVE 0.01 /**< factor by which Gins should at least improve the incumbent */
82 #define DEFAULT_MINNODES 50 /**< minimum number of nodes to regard in the subproblem */
83 #define DEFAULT_MINFIXINGRATE 0.66 /**< minimum percentage of integer variables that have to be fixed */
84 #define DEFAULT_NODESQUOT 0.15 /**< subproblem nodes in relation to nodes of the original problem */
85 #define DEFAULT_NWAITINGNODES 100 /**< number of nodes without incumbent change that heuristic should wait */
86 #define DEFAULT_USELPROWS FALSE /**< should subproblem be created out of the rows in the LP rows,
87  **< otherwise, the copy constructors of the constraints handlers are used */
88 #define DEFAULT_COPYCUTS TRUE /**< if DEFAULT_USELPROWS is FALSE, then should all active cuts from the
89  **< cutpool of the original scip be copied to constraints of the subscip */
90 #define DEFAULT_BESTSOLLIMIT 3 /**< limit on number of improving incumbent solutions in sub-CIP */
91 #define DEFAULT_FIXCONTVARS FALSE /**< should continuous variables outside the neighborhoods get fixed? */
92 #define DEFAULT_POTENTIAL 'r' /**< the reference point to compute the neighborhood potential: (r)oot or (p)seudo solution */
93 #define DEFAULT_MAXDISTANCE 3 /**< maximum distance to selected variable to enter the subproblem, or -1 to
94  * select the distance that best approximates the minimum fixing rate from below */
95 #define DEFAULT_RANDSEED 71
96 #define DEFAULT_RELAXDENSECONSS FALSE /**< should dense constraints (at least as dense as 1 - minfixingrate) be
97  * ignored by connectivity graph? */
98 #define DEFAULT_USEROLLINGHORIZON TRUE /**< should the heuristic solve a sequence of sub-MIP's around the first selected variable */
99 #define DEFAULT_ROLLHORIZONLIMFAC 0.4 /**< limiting percentage for variables already used in sub-SCIPs to terminate rolling
100  * horizon approach */
101 #ifdef SCIP_STATISTIC
102 #define NHISTOGRAMBINS 10 /* number of bins for histograms */
103 #endif
104 /*
105  * Data structures
106  */
107
108 /** rolling horizon data structure to control multiple LNS heuristic runs away from an original source variable
109  *
110  */
111 struct RollingHorizon
112 {
113  SCIP_VGRAPH* variablegraph; /**< variable graph data structure for breadth-first-search neighborhoods */
114  int* distances; /**< distances of the heuristic rolling horizon from the original source
115  * variable indexed by probindex */
116  SCIP_Bool* used; /**< array that represents for every variable whether it has been used
117  * in a neighborhood indexed by probindex */
118  int lastmaxdistance; /**< the last distance k for a neighborhood, will be decreased
119  * during the rolling horizon if the selected neighborhood is too large */
120  int lastdistance; /**< last distance from originally selected variable in iteration zero */
121  int distancessize; /**< size of the distances and used arrays */
122  int niterations; /**< counter for the number of rolling horizon iterations */
123  int nused; /**< counts the number variables that have been part of any neighborhood
124  * during the rolling horizon approach */
125  int nnonreachable; /**< counter for the number of nonreachable variables (distance -1) from
126  * the initially selected variable */
127 };
129
130 /** primal heuristic data */
131 struct SCIP_HeurData
132 {
133  int nodesofs; /**< number of nodes added to the contingent of the total nodes */
134  int maxnodes; /**< maximum number of nodes to regard in the subproblem */
135  int minnodes; /**< minimum number of nodes to regard in the subproblem */
136  SCIP_Real minfixingrate; /**< minimum percentage of integer variables that have to be fixed */
137  int nwaitingnodes; /**< number of nodes without incumbent change that heuristic should wait */
138  SCIP_Real minimprove; /**< factor by which Gins should at least improve the incumbent */
139  SCIP_Longint usednodes; /**< nodes already used by Gins in earlier calls */
140  SCIP_Real nodesquot; /**< subproblem nodes in relation to nodes of the original problem */
141  SCIP_Real rollhorizonlimfac; /**< limiting percentage for variables already used in sub-SCIPs to terminate
142  * rolling horizon approach */
143  SCIP_RANDNUMGEN* randnumgen; /**< random number generator */
144  SCIP_Bool uselprows; /**< should subproblem be created out of the rows in the LP rows? */
145  SCIP_Bool copycuts; /**< if uselprows == FALSE, should all active cuts from cutpool be copied
146  * to constraints in subproblem? */
147  SCIP_Bool fixcontvars; /**< should continuous variables outside the neighborhoods get fixed? */
148  int bestsollimit; /**< limit on number of improving incumbent solutions in sub-CIP */
149  int maxdistance; /**< maximum distance to selected variable to enter the subproblem, or -1 to
150  * select the distance that best approximates the minimum fixing rate from below */
151  int sumneighborhoodvars;/**< neighborhood variables sum over all seen neighborhoods */
152  int sumdiscneighborhoodvars; /**< neighborhood discrete variables sum over all seen neighboorhoods */
153  int nneighborhoods; /**< number of calculated neighborhoods */
154  int nsubmips; /**< counter for the number of sub-MIP's that can be higher than the number of
155  * calls of this heuristic */
156  SCIP_Bool relaxdenseconss; /**< should dense constraints (at least as dense as 1 - minfixingrate) be
157  * ignored by connectivity graph? */
158  SCIP_Bool userollinghorizon; /**< should the heuristic solve a sequence of sub-MIP's around the first
159  * selected variable */
160  char potential; /**< the reference point to compute the neighborhood potential: (r)oot or
161  * (p)seudo solution */
162  int maxseendistance; /**< maximum of all distances between two variables */
163 #ifdef SCIP_STATISTIC
164  int consvarshist[NHISTOGRAMBINS]; /**< histogram that summarizes the densities of the constraints */
165  int consdiscvarshist[NHISTOGRAMBINS]; /**< histogram that summarizes the discrete variable densities of the constraints */
166  int conscontvarshist[NHISTOGRAMBINS]; /**< histogram that summarizes the continuous variable densities of the constraints */
167 #endif
168  int nrelaxedconstraints; /**< number of constraints that were relaxed */
169  int nfailures; /**< counter for the number of unsuccessful runs of this heuristic */
170  SCIP_Longint nextnodenumber; /**< the next node number at which the heuristic should be called again */
171 };
172
173 /** represents limits for the sub-SCIP solving process */
174 struct SolveLimits
175 {
176  SCIP_Longint nodelimit; /**< maximum number of solving nodes for the sub-SCIP */
177  SCIP_Real memorylimit; /**< memory limit for the sub-SCIP */
178  SCIP_Real timelimit; /**< time limit for the sub-SCIP */
179 };
180 typedef struct SolveLimits SOLVELIMITS;
181
182 /*
183  * Local methods
184  */
186 #ifdef SCIP_STATISTIC
187 /** resets a histogram */
188 static
189 void resetHistogram(
190  int* histogram /**< the histogram */
191  )
192 {
193  BMSclearMemoryArray(histogram, NHISTOGRAMBINS);
194 }
195
196 /** adds a ratio to the histogram at the right position */
197 static
199  int* histogram, /**< the histogram */
200  int value, /**< the value */
201  int basevalue /**< base value */
202  )
203 {
204  SCIP_Real ratio;
205  int index;
206  assert(value <= basevalue);
207  ratio = value/ MAX(1.0, (SCIP_Real)basevalue);
208
209  index = (int)(ratio * NHISTOGRAMBINS);
210  ++histogram[index];
211 }
212
213 #endif
214
215 /** create a rolling horizon data structure */
216 static
218  SCIP* scip, /**< SCIP data structure */
219  ROLLINGHORIZON** rollinghorizon /**< pointer to rolling horizon data structure */
220  )
221 {
222  int size;
223  assert(scip != NULL);
224  assert(rollinghorizon != NULL);
225
226  size = SCIPgetNBinVars(scip) + SCIPgetNIntVars(scip);
227  SCIP_CALL( SCIPallocBlockMemory(scip, rollinghorizon) );
228  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(*rollinghorizon)->distances, size) );
229  SCIP_CALL( SCIPallocClearBlockMemoryArray(scip, &(*rollinghorizon)->used, size) );
230  (*rollinghorizon)->distancessize = size;
231  (*rollinghorizon)->variablegraph = NULL;
232  (*rollinghorizon)->lastdistance = -1;
233  (*rollinghorizon)->niterations = 0;
234  (*rollinghorizon)->nused = 0;
235
236  return SCIP_OKAY;
237 }
238
239 /** free a rolling horizon data structure */
240 static
242  SCIP* scip, /**< SCIP data structure */
243  ROLLINGHORIZON** rollinghorizon /**< pointer to rolling horizon data structure */
244  )
245 {
246  assert(scip != NULL);
247  assert(rollinghorizon != NULL);
248  assert(*rollinghorizon != NULL);
249
250  if( (*rollinghorizon)->variablegraph != NULL )
251  {
252  SCIPvariableGraphFree(scip, &(*rollinghorizon)->variablegraph);
253  }
254
255  SCIPfreeBlockMemoryArray(scip, &(*rollinghorizon)->distances, (*rollinghorizon)->distancessize);
256  SCIPfreeBlockMemoryArray(scip, &(*rollinghorizon)->used, (*rollinghorizon)->distancessize);
257  SCIPfreeBlockMemory(scip, rollinghorizon);
258  return SCIP_OKAY;
259 }
260
261 /** is there potential to run another iteration of the rolling horizon approach? */
262 static
264  SCIP* scip, /**< SCIP data structure */
265  ROLLINGHORIZON* rollinghorizon, /**< rolling horizon data structure */
266  SCIP_HEURDATA* heurdata /**< heuristic data */
267  )
268 {
269  int maxnused = (int)(heurdata->rollhorizonlimfac * (SCIPgetNBinVars(scip) + SCIPgetNIntVars(scip)
270  - rollinghorizon->nnonreachable));
271
272  /* run again if a certain percentage of the reachable variables (in the same connected component)
273  * was not used in a previous neighborhood
274  */
275  return (rollinghorizon->nused < maxnused);
276 }
277
278 /** store the distances from the selected variable permanently for the rolling horizon approach */
279 static
281  SCIP* scip, /**< SCIP data structure */
282  ROLLINGHORIZON* rollinghorizon, /**< rolling horizon data structure */
283  int* distances /**< breadth-first distances indexed by Probindex of variables */
284  )
285 {
286  int i;
287  BMScopyMemoryArray(rollinghorizon->distances, distances, rollinghorizon->distancessize);
288  rollinghorizon->lastdistance = 0;
289  rollinghorizon->nnonreachable = 0;
290
291  /* collect number of nonreachable variables */
292  for( i = 0; i < rollinghorizon->distancessize; ++i )
293  {
294  if( distances[i] == -1 )
295  ++rollinghorizon->nnonreachable;
296  }
297 }
298
299 /** get the potential of a subset of variables (distance to a reference point such as the pseudo-solution or root
300  * LP solution)
301  */
302 static
304  SCIP* scip, /**< SCIP data structure */
305  SCIP_HEURDATA* heurdata, /**< heuristic data */
306  SCIP_SOL* sol, /**< solution */
307  SCIP_VAR** vars, /**< variable array */
308  int nvars /**< length of variable array */
309  )
310 {
311  SCIP_Real potential;
312  int i;
313
314  assert(scip != NULL);
315  assert(vars != NULL);
316  assert(sol != NULL);
317
318  if( nvars == 0 )
319  return 0.0;
320
321  potential = 0.0;
322
323  for( i = 0; i < nvars; ++i )
324  {
325  SCIP_Real objdelta;
326  SCIP_VAR* var;
327  SCIP_Real referencepoint;
328  SCIP_Real varobj;
329
330  var = vars[i];
331  assert(var != NULL);
332  varobj = SCIPvarGetObj(var);
333
334  if( SCIPisZero(scip, varobj) )
335  continue;
336
337  /* determine the reference point for potential computation */
338  switch( heurdata->potential )
339  {
340  /* use difference to pseudo solution using the bound in the objective direction */
341  case 'p':
342  referencepoint = SCIPvarGetObj(var) > 0.0 ? SCIPvarGetLbGlobal(var) : SCIPvarGetUbGlobal(var);
343  break;
344
345  /* use root LP solution difference */
346  case 'r':
347  referencepoint = SCIPvarGetRootSol(var);
348  break;
349  default:
350  SCIPerrorMessage("Unknown potential computation %c specified\n", heurdata->potential);
351  referencepoint = 0.0;
352  break;
353  }
354
355  if( SCIPisInfinity(scip, REALABS(referencepoint)) )
356  continue;
357
358  /* calculate the delta to the variables best bound */
359  objdelta = (SCIPgetSolVal(scip, sol, var) - referencepoint) * SCIPvarGetObj(var);
360  potential += objdelta;
361  }
362
363  return potential;
364 }
365
366 /** is the variable in the current neighborhood which is given by the breadth-first distances from a central variable? */
367 static
369  SCIP_VAR* var, /**< problem variable */
370  int* distances, /**< breadth-first distances indexed by Probindex of variables */
371  int maxdistance /**< maximum distance (inclusive) to be considered for neighborhoods */
372  )
373 {
374  assert(var != NULL);
375  assert(distances != NULL);
376  assert(maxdistance >= 0);
377  assert(SCIPvarGetProbindex(var) >= 0);
378
379  return (distances[SCIPvarGetProbindex(var)] != -1 && distances[SCIPvarGetProbindex(var)] <= maxdistance);
380 }
381
382 /** fixes variables in subproblem based on long breadth-first distances in variable graph */
383 static
385  SCIP* scip, /**< SCIP data structure */
386  SCIP_HEURDATA* heurdata, /**< heuristic data */
387  ROLLINGHORIZON* rollinghorizon, /**< rolling horizon data structure to save relevant information, or NULL if not needed */
388  SCIP_SOL* sol, /**< solution in main SCIP for fixing values */
389  SCIP_VAR** vars, /**< variables in the main SCIP */
390  SCIP_VAR** fixedvars, /**< buffer to store variables that should be fixed */
391  SCIP_Real* fixedvals, /**< buffer to store fixing values for fixed variables */
392  int* distances, /**< breadth-first distances indexed by Probindex of variables */
393  int maxdistance, /**< maximum distance (inclusive) to be considered for neighborhoods */
394  int* nfixings /**< pointer to store number of fixed variables */
395  )
396 {
397  int i;
398  int nbinvars;
399  int nintvars;
400  int nvars;
401  int nvarstofix;
402
403  SCIP_CALL( SCIPgetVarsData(scip, NULL, &nvars, &nbinvars, &nintvars, NULL, NULL) );
404
405  nvarstofix = heurdata->fixcontvars ? nvars : nbinvars + nintvars;
406  *nfixings = 0;
407
408  /* change bounds of variables of the subproblem */
409  for( i = 0; i < nvarstofix; i++ )
410  {
411  /* fix all variables that are too far away from this variable according to maxdistance */
412  if( distances[i] == -1 || distances[i] > maxdistance )
413  {
414  SCIP_Real solval;
415  SCIP_Real lb;
416  SCIP_Real ub;
417
418  solval = SCIPgetSolVal(scip, sol, vars[i]);
419  lb = SCIPvarGetLbGlobal(vars[i]);
420  ub = SCIPvarGetUbGlobal(vars[i]);
421  assert(SCIPisLE(scip, lb, ub));
422
423  /* due to dual reductions, it may happen that the solution value is not in the variable's domain anymore */
424  if( SCIPisLT(scip, solval, lb) )
425  solval = lb;
426  else if( SCIPisGT(scip, solval, ub) )
427  solval = ub;
428
429  /* perform the bound change */
430  if( !SCIPisInfinity(scip, solval) && !SCIPisInfinity(scip, -solval) )
431  {
432  fixedvars[*nfixings] = vars[i];
433  fixedvals[*nfixings] = solval;
434  ++(*nfixings);
435  }
436  }
437  else if( rollinghorizon != NULL && i < nbinvars + nintvars && ! rollinghorizon->used[i] )
438  {
439  ++rollinghorizon->nused;
440  rollinghorizon->used[i] = TRUE;
441  }
442  }
443
444  if( rollinghorizon != NULL )
445  {
446  rollinghorizon->lastmaxdistance = maxdistance;
447  rollinghorizon->niterations++;
448  }
449
450  return SCIP_OKAY;
451 }
452
453 /** determine the maximum allowed distance to stay within the restriction to fix at least minfixingrate many non
454  * neighborhood variables
455  */
456 static
458  SCIP* scip, /**< SCIP data structure */
459  SCIP_HEURDATA* heurdata, /**< heuristic data */
460  int* distances, /**< breadth-first distances indexed by Probindex of variables */
461  int* choosevardistance /**< pointer to store the computed maximum distance */
462  )
463 {
464  int* distancescopy;
465  int nrelevantdistances;
466  int criticalidx;
467  int zeropos;
468  int nvars;
469  int nbinvars;
470  int nintvars;
471
472  SCIP_CALL( SCIPgetVarsData(scip, NULL, &nvars, &nbinvars, &nintvars, NULL, NULL) );
473
474  nrelevantdistances = (heurdata->fixcontvars ? nvars : (nbinvars + nintvars));
475
476  /* copy the relevant distances of either the discrete or all problem variables and sort them */
477  SCIP_CALL( SCIPduplicateBufferArray(scip, &distancescopy, distances, nrelevantdistances) );
478  SCIPsortInt(distancescopy, nrelevantdistances);
479
480  /* distances can be infinite in the case of multiple connected components; therefore, search for the index of the
481  * zero entry, which is the unique representative of the chosen variable in the sorted distances
482  */
483  zeropos = -1;
484
485  /* TODO: use selection method instead */
486  (void)SCIPsortedvecFindInt(distancescopy, 0, nrelevantdistances, &zeropos);
487  assert(zeropos >= 0);
488
489  /* determine the critical index to look for an appropriate neighborhood distance, starting from the zero position */
490  criticalidx = zeropos + (int)((1.0 - heurdata->minfixingrate) * nrelevantdistances);
491  criticalidx = MIN(criticalidx, nrelevantdistances - 1);
492
493  /* determine the maximum breadth-first distance such that the neighborhood size stays small enough (below 1-minfixingrate)*/
494  *choosevardistance = distancescopy[criticalidx];
495
496  /* we set the distance to exactly the distance at the critical index. If the distance at critical index is not the
497  * last one before the distance increases, we decrease the choosevardistance such that the entire neighborhood
498  * fits into the minfixingrate restriction
499  */
500  if( criticalidx != nrelevantdistances - 1 && distancescopy[criticalidx + 1] == *choosevardistance )
501  (*choosevardistance)--;
502
503  /* update the maximum distance */
504  heurdata->maxseendistance = MAX(heurdata->maxseendistance, distancescopy[nrelevantdistances - 1]);
505
506  SCIPfreeBufferArray(scip, &distancescopy);
507
508  return SCIP_OKAY;
509 }
510
511 /** gets the average size of a discrete neighborhood over all variables tested */
512 static
514  SCIP_HEURDATA* heurdata /**< heuristic data */
515  )
516 {
517  return heurdata->sumdiscneighborhoodvars / (MAX(1.0, (SCIP_Real)heurdata->nneighborhoods));
518 }
519
520 /** select a good starting variable at the first iteration of a rolling horizon approach */
521 static
523  SCIP* scip, /**< SCIP data structure */
524  SCIP_HEURDATA* heurdata, /**< heuristic data */
525  SCIP_VGRAPH* vargraph, /**< variable graph data structure to work on */
526  int* distances, /**< breadth-first distances indexed by Probindex of variables */
527  SCIP_VAR** selvar, /**< pointer to store the selected variable */
528  int* selvarmaxdistance /**< maximal distance k to consider for selected variable neighborhood */
529  )
530 {
531  SCIP_SOL* sol;
532  SCIP_VAR** vars; /* original scip variables */
533  int nbinvars;
534  int nintvars;
535  int nvars;
536  int nsearched;
537  int searchlimit;
538  int nintegralvarsleft;
539  int nintegralvarsbound;
540  int v;
541  SCIP_VAR** varscopy;
542  int maxdistance;
543  SCIP_Real maxpotential;
544
545  assert(vargraph != NULL);
546  assert(scip != NULL);
547  assert(heurdata != NULL);
548  assert(selvar != NULL);
549  sol = SCIPgetBestSol(scip);
550  assert(sol != NULL);
551
552  /* get required data of the original problem */
553  SCIP_CALL( SCIPgetVarsData(scip, &vars, &nvars, &nbinvars, &nintvars, NULL, NULL) );
554
555  /* copy SCIP variables */
556  SCIP_CALL( SCIPduplicateBufferArray(scip, &varscopy, vars, nbinvars + nintvars) );
557  nsearched = 0;
558  maxpotential = SCIP_REAL_MIN;
559
560  /* determine upper bound on neighborhood size */
561  nintegralvarsbound = (int)((1.0 - heurdata->minfixingrate) * (nbinvars + nintvars));
562
563  /* maximum distance from selected variable for breadth-first search (if set to -1, we compute an exhaustive breadth-first
564  * search and sort the variables by their distance)
565  */
566  maxdistance = (heurdata->maxdistance == - 1 ? INT_MAX : heurdata->maxdistance);
567
568  nintegralvarsleft = nbinvars + nintvars;
569  *selvar = NULL;
570
571  /* sort inactive variables to the end of the array */
572  for( v = nintegralvarsleft - 1; v >= 0; --v )
573  {
574  if( ! SCIPvarIsActive(varscopy[v]) )
575  {
576  varscopy[v] = varscopy[nintegralvarsleft - 1];
577  --nintegralvarsleft;
578  }
579  }
580
581  /* adjust the search limit */
582  searchlimit = heurdata->nneighborhoods < 10 ? 5 : (int)(nintegralvarsleft / heurdataAvgDiscreteNeighborhoodSize(heurdata));
583  searchlimit = MIN(searchlimit, 10);
584
585  /* multi variable potential: choose different disjoint neighborhoods, compare their potential */
586  while( nsearched < searchlimit && nintegralvarsleft > 0 )
587  {
588  SCIP_VAR** neighborhood;
589  SCIP_VAR* choosevar;
590  int neighborhoodsize;
591  int ndiscvarsneighborhood;
592  int choosevardistance;
593
594  ++nsearched;
595
596  /* select a variable to start with randomly, but make sure it is active */
597  do
598  {
599  int idx = SCIPrandomGetInt(heurdata->randnumgen, 0, nintegralvarsleft - 1);
600  choosevar = varscopy[idx];
601  assert(choosevar != NULL);
602  /* sort inactive variables to the end */
603  if( SCIPvarGetProbindex(choosevar) < 0 )
604  {
605  varscopy[idx] = varscopy[nintegralvarsleft - 1];
606  --nintegralvarsleft;
607  }
608  }
609  while( SCIPvarGetProbindex(choosevar) < 0 && nintegralvarsleft > 0);
610
611  /* if there was no variable chosen, there are no active variables left */
612  if( SCIPvarGetProbindex(choosevar) < 0 )
613  {
614  SCIPdebugMsg(scip, "No active variable left to perform breadth-first search\n");
615  break;
616  }
617
618  assert(SCIPvarIsIntegral(choosevar));
619
620  /* get neighborhood storage */
621  SCIP_CALL( SCIPallocBufferArray(scip, &neighborhood, nvars) );
622
623  /* determine breadth-first distances from the chosen variable */
624  SCIP_CALL( SCIPvariablegraphBreadthFirst(scip, vargraph, &choosevar, 1, distances, maxdistance, INT_MAX, INT_MAX) );
625
626  /* use either automatic or user-defined max-distance for neighborhood in variable constraint graph */
627  if( heurdata->maxdistance != -1 )
628  {
629  choosevardistance = heurdata->maxdistance;
630  }
631  else
632  {
633  SCIP_CALL( determineMaxDistance(scip, heurdata, distances, &choosevardistance) );
634  }
635
636  ndiscvarsneighborhood = 0;
637  neighborhoodsize = 0;
638
639  /* loop over variables and determine neighborhood */
640  for( v = nvars - 1; v >= 0; --v )
641  {
642  SCIP_VAR* currvar;
643  currvar = vars[v];
644
645  /* put variable in the neighborhood */
646  if( isVariableInNeighborhood(currvar, distances, choosevardistance) )
647  {
648  neighborhood[neighborhoodsize++] = currvar;
649
650  /* increase discrete variables counter */
651  if( SCIPvarIsIntegral(currvar) )
652  ++ndiscvarsneighborhood;
653  }
654  }
655
656  /* check if neighborhood contains too many integer variables in order to satisfy the minimum fixing rate */
657  if( ndiscvarsneighborhood >= nintegralvarsbound || ndiscvarsneighborhood <= 1 )
658  {
659  SCIPdebugMsg(scip, "Too many or too few discrete variables in neighboorhood: %d (%d)\n",
660  ndiscvarsneighborhood, nbinvars + nintvars);
661  }
662  else
663  {
664  /* compare the neighborhood potential to the best potential found so far */
665  SCIP_Real potential = getPotential(scip, heurdata, sol, neighborhood, neighborhoodsize);
666
667  /* big potential, take this variable */
668  if( potential > maxpotential )
669  {
670  maxpotential = potential;
671  *selvar = choosevar;
672  *selvarmaxdistance = choosevardistance;
673  }
674  }
675
676  /* sort neighborhood variables to the end so that this neighborhood is not considered in further samples */
677  for( v = nintegralvarsleft - 1; v >= 0; --v )
678  {
679  SCIP_VAR* currvar;
680  currvar = vars[v];
681
682  if( isVariableInNeighborhood(currvar, distances, choosevardistance) )
683  {
684  varscopy[v] = varscopy[nintegralvarsleft - 1];
685  --nintegralvarsleft;
686  }
687  }
688
689  heurdata->sumdiscneighborhoodvars += ndiscvarsneighborhood;
690  heurdata->sumneighborhoodvars += neighborhoodsize;
691  ++heurdata->nneighborhoods;
692
693  /* free current neighborhood */
694  SCIPfreeBufferArray(scip, &neighborhood);
695  }
696
697  SCIPfreeBufferArray(scip, &varscopy);
698
699  /* maybe no variable has a positive delta */
700  if( !SCIPisPositive(scip, maxpotential) || *selvar == NULL )
701  {
702  SCIPdebugMsg(scip, "Stopping with maxpotential %15.9f and selected variable %s\n",
703  maxpotential, *selvar != NULL ? SCIPvarGetName(*selvar) : "none");
704  *selvar = NULL;
705  }
706
707  return SCIP_OKAY;
708 }
709
710 /** select the next variable using the rolling horizon */
711 static
713  SCIP* scip, /**< SCIP data structure */
714  SCIP_HEURDATA* heurdata, /**< heuristic data */
715  ROLLINGHORIZON* rollinghorizon, /**< rolling horizon data structure to save relevant information, or NULL if not needed */
716  int* distances, /**< breadth-first distances indexed by Probindex of variables */
717  SCIP_VAR** selvar, /**< pointer to store the selected variable */
718  int* selvarmaxdistance /**< maximal distance k to consider for selected variable neighborhood */
719  )
720 {
721  SCIP_VAR** vars; /* original scip variables */
722  int i;
723  int nbinvars;
724  int nintvars;
725  int minunuseddistance;
726
727  assert(scip != NULL);
728  assert(rollinghorizon != NULL);
729  assert(distances != NULL);
730  assert(selvar != NULL);
731  assert(selvarmaxdistance != NULL);
732
733  SCIP_CALL( SCIPgetVarsData(scip, &vars, NULL, &nbinvars, &nintvars, NULL, NULL) );
734
735  /* loop over the variables that are left and pick the variable with
736  * - the smallest, always nondecreasing distance
737  * - that was not used before in a neighborhood
738  */
739  do
740  {
741  minunuseddistance = INT_MAX;
742  *selvarmaxdistance = rollinghorizon->lastmaxdistance;
743  *selvar = NULL;
744  for( i = 0; i < nbinvars + nintvars && minunuseddistance > rollinghorizon->lastdistance; ++i )
745  {
746  if( rollinghorizon->distances[i] >= rollinghorizon->lastdistance
747  && rollinghorizon->distances[i] < minunuseddistance && ! rollinghorizon->used[i] )
748  {
749  minunuseddistance = rollinghorizon->distances[i];
750  *selvar = vars[i];
751  }
752  }
753
754  /* if no variable could be selected, we can stop */
755  if( *selvar == NULL )
756  {
757  *selvarmaxdistance = 0;
758  return SCIP_OKAY;
759  }
760
761  /* determine the distances to other variables from this variable */
762  SCIP_CALL( SCIPvariablegraphBreadthFirst(scip, rollinghorizon->variablegraph, selvar, 1, distances, *selvarmaxdistance, INT_MAX, INT_MAX) );
763
764  SCIP_CALL( determineMaxDistance(scip, heurdata, distances, selvarmaxdistance) );
765
766  /* mark this variable as used in order to not find it again */
767  if( *selvarmaxdistance == 0 )
768  {
769  rollinghorizon->used[SCIPvarGetProbindex(*selvar)] = TRUE;
770  rollinghorizon->nused++;
771  *selvar = NULL;
772  }
773  }
774  while( rollingHorizonRunAgain(scip, rollinghorizon, heurdata) && (*selvar == NULL || *selvarmaxdistance == 0) );
775
776  /* breadth-first search determines the distances of all variables
777  * that are no more than maxdistance away from the start variable
778  */
779  assert(*selvarmaxdistance <= rollinghorizon->lastmaxdistance);
780  *selvarmaxdistance = MIN(*selvarmaxdistance, rollinghorizon->lastmaxdistance);
781  rollinghorizon->lastdistance = minunuseddistance;
782  rollinghorizon->lastmaxdistance = *selvarmaxdistance;
783
784  return SCIP_OKAY;
785 }
786
787 /** determines the graph-induced variable fixings */
788 static
790  SCIP* scip, /**< original SCIP data structure */
791  SCIP_VAR** fixedvars, /**< buffer to store variables that should be fixed */
792  SCIP_Real* fixedvals, /**< buffer to store fixing values for fixed variables */
793  int* nfixings, /**< pointer to store the number of fixed variables */
794  SCIP_HEURDATA* heurdata, /**< heuristic data */
795  ROLLINGHORIZON* rollinghorizon, /**< rolling horizon data structure to save relevant information, or NULL if not needed */
796  SCIP_Bool* success /**< used to store whether the creation of the subproblem worked */
797  )
798 {
799  SCIP_VAR** vars;
800  SCIP_SOL* sol; /* pool of solutions */
801  int* distances;
802  SCIP_VGRAPH* vargraph;
803  SCIP_VAR* selvar;
804  int nvars;
805  int nbinvars;
806  int nintvars;
807  int fixthreshold;
808
809  int selvarmaxdistance;
810
811  assert(fixedvars != NULL);
812  assert(fixedvals != NULL);
813  assert(nfixings != NULL);
814
815  *success = TRUE;
816  *nfixings = 0;
817  selvarmaxdistance = 0;
818  sol = SCIPgetBestSol(scip);
819  assert(sol != NULL);
820
821  /* get required data of the original problem */
822  SCIP_CALL( SCIPgetVarsData(scip, &vars, &nvars, &nbinvars, &nintvars, NULL, NULL) );
823
824  /* create variable graph */
825  SCIPdebugMsg(scip, "Creating variable constraint graph\n");
826
827  /* get the saved variable graph, or create a new one */
828  if( rollinghorizon != NULL )
829  {
830  if( rollinghorizon->niterations == 0 )
831  {
832  SCIP_CALL( SCIPvariableGraphCreate(scip, &rollinghorizon->variablegraph, heurdata->relaxdenseconss, 1.0 - heurdata->minfixingrate, &heurdata->nrelaxedconstraints) );
833  }
834  else
835  assert(rollinghorizon->variablegraph != NULL);
836
837  vargraph = rollinghorizon->variablegraph;
838  }
839  else
840  {
841  SCIP_CALL( SCIPvariableGraphCreate(scip, &vargraph, heurdata->relaxdenseconss, 1.0 - heurdata->minfixingrate, &heurdata->nrelaxedconstraints) );
842  }
843
844  /* allocate buffer memory to hold distances */
845  SCIP_CALL( SCIPallocBufferArray(scip, &distances, nvars) );
846
847  selvar = NULL;
848
849  /* in the first iteration of the rolling horizon approach, we select an initial variable */
850  if( rollinghorizon == NULL || rollinghorizon->niterations == 0 )
851  {
852  SCIP_CALL( selectInitialVariable(scip, heurdata, vargraph, distances, &selvar, &selvarmaxdistance) );
853
854  /* collect and save the distances in the rolling horizon data structure */
855  if( selvar != NULL && rollinghorizon != NULL )
856  {
857  /* collect distances in the variable graph of all variables to the selected variable */
858  SCIP_CALL( SCIPvariablegraphBreadthFirst(scip, vargraph, &selvar, 1, distances, INT_MAX, INT_MAX, INT_MAX) );
859  rollingHorizonStoreDistances(scip, rollinghorizon, distances);
860  rollinghorizon->lastmaxdistance = selvarmaxdistance;
861  }
862  }
863  else
864  {
865  /* select the next variable, if variables are left */
866  SCIP_CALL( selectNextVariable(scip, heurdata, rollinghorizon, distances, &selvar, &selvarmaxdistance) );
867  }
868
869  assert(selvar == NULL || selvarmaxdistance > 0);
870  if( selvar == NULL )
871  {
872  *success = FALSE;
873  }
874  else
875  {
876  SCIPdebugMsg(scip, "Selected variable <%s> as central variable for a <%d>-neighborhood\n",
877  SCIPvarGetName(selvar), selvarmaxdistance);
878
879  /* fix variables that are not in the neighborhood around the selected variable */
880  SCIP_CALL( fixNonNeighborhoodVariables(scip, heurdata, rollinghorizon, sol, vars, fixedvars, fixedvals, distances,
881  selvarmaxdistance, nfixings) );
882
883  fixthreshold = (int)(heurdata->minfixingrate * (heurdata->fixcontvars ? nvars : (nbinvars + nintvars)));
884
885  /* compare actual number of fixings to limit; if we fixed not enough variables we terminate here;
886  * we also terminate if no discrete variables are left
887  */
888  if( *nfixings < fixthreshold )
889  {
890  SCIPdebugMsg(scip, "Fixed %d < %d variables in gins heuristic, stopping", *nfixings, fixthreshold);
891  *success = FALSE;
892  }
893  }
894
896  if( rollinghorizon == NULL )
897  SCIPvariableGraphFree(scip, &vargraph);
898
899  return SCIP_OKAY;
900 }
901
902 /** creates a new solution for the original problem by copying the solution of the subproblem */
903 static
905  SCIP* scip, /**< original SCIP data structure */
906  SCIP* subscip, /**< SCIP structure of the subproblem */
907  SCIP_VAR** subvars, /**< the variables of the subproblem */
908  SCIP_HEUR* heur, /**< gins heuristic structure */
909  SCIP_SOL* subsol, /**< solution of the subproblem */
910  SCIP_Bool* success /**< used to store whether new solution was found or not */
911  )
912 {
913  SCIP_VAR** vars; /* the original problem's variables */
914  int nvars;
915  SCIP_Real* subsolvals; /* solution values of the subproblem */
916  SCIP_SOL* newsol; /* solution to be created for the original problem */
917
918  assert(scip != NULL);
919  assert(subscip != NULL);
920  assert(subvars != NULL);
921  assert(subsol != NULL);
922
923  /* get variables' data */
924  SCIP_CALL( SCIPgetVarsData(scip, &vars, &nvars, NULL, NULL, NULL, NULL) );
925
926  /* sub-SCIP may have more variables than the number of active (transformed) variables in the main SCIP
927  * since constraint copying may have required the copy of variables that are fixed in the main SCIP
928  */
929  assert(nvars <= SCIPgetNOrigVars(subscip));
930
931  SCIP_CALL( SCIPallocBufferArray(scip, &subsolvals, nvars) );
932
933  /* copy the solution */
934  SCIP_CALL( SCIPgetSolVals(subscip, subsol, nvars, subvars, subsolvals) );
935
936  /* create new solution for the original problem */
937  SCIP_CALL( SCIPcreateSol(scip, &newsol, heur) );
938  SCIP_CALL( SCIPsetSolVals(scip, newsol, nvars, vars, subsolvals) );
939
940  /* try to add new solution to scip and free it immediately */
941  SCIP_CALL( SCIPtrySolFree(scip, &newsol, FALSE, FALSE, TRUE, TRUE, TRUE, success) );
942
943  SCIPfreeBufferArray(scip, &subsolvals);
944
945  return SCIP_OKAY;
946 }
947
948 /** set sub-SCIP solving limits */
949 static
951  SCIP* subscip, /**< SCIP data structure */
952  SOLVELIMITS* solvelimits /**< pointer to solving limits data structure */
953  )
954 {
955  assert(subscip != NULL);
956  assert(solvelimits != NULL);
957
958  SCIP_CALL( SCIPsetLongintParam(subscip, "limits/nodes", solvelimits->nodelimit) );
959  SCIP_CALL( SCIPsetRealParam(subscip, "limits/time", solvelimits->timelimit) );
960  SCIP_CALL( SCIPsetRealParam(subscip, "limits/memory", solvelimits->memorylimit) );
961
962  return SCIP_OKAY;
963 }
964
965 /** set up the sub-SCIP */
966 static
968  SCIP* scip, /**< SCIP data structure */
969  SCIP* subscip, /**< sub-SCIP data structure */
970  SOLVELIMITS* solvelimits, /**< pointer to solving limits data structure */
971  SCIP_HEUR* heur /**< this heuristic */
972  )
973 {
974  SCIP_HEURDATA* heurdata;
975  SCIP_Real cutoff;
976  SCIP_Real upperbound;
977
978  heurdata = SCIPheurGetData(heur);
979
980  /* do not abort subproblem on CTRL-C */
981  SCIP_CALL( SCIPsetBoolParam(subscip, "misc/catchctrlc", FALSE) );
982
983  /* disable output to console */
984  SCIP_CALL( SCIPsetIntParam(subscip, "display/verblevel", 0) );
985
986  /* disable statistic timing inside sub SCIP */
987  SCIP_CALL( SCIPsetBoolParam(subscip, "timing/statistictiming", FALSE) );
988
989  SCIP_CALL( SCIPsetIntParam(subscip, "limits/bestsol", heurdata->bestsollimit) );
990
991  /* forbid recursive call of heuristics and separators solving subMIPs */
992  SCIP_CALL( SCIPsetSubscipsOff(subscip, TRUE) );
993
994  /* disable cutting plane separation */
996
997  /* disable expensive presolving */
999
1000  /* use best estimate node selection */
1001  if( SCIPfindNodesel(subscip, "estimate") != NULL && !SCIPisParamFixed(subscip, "nodeselection/estimate/stdpriority") )
1002  {
1003  SCIP_CALL( SCIPsetIntParam(subscip, "nodeselection/estimate/stdpriority", INT_MAX/4) );
1004  }
1005
1006  /* use inference branching */
1007  if( SCIPfindBranchrule(subscip, "inference") != NULL && !SCIPisParamFixed(subscip, "branching/inference/priority") )
1008  {
1009  SCIP_CALL( SCIPsetIntParam(subscip, "branching/inference/priority", INT_MAX/4) );
1010  }
1011
1012  /* enable conflict analysis, disable analysis of boundexceeding LPs, and restrict conflict pool */
1013  if( !SCIPisParamFixed(subscip, "conflict/enable") )
1014  {
1015  SCIP_CALL( SCIPsetBoolParam(subscip, "conflict/enable", TRUE) );
1016  }
1017  if( !SCIPisParamFixed(subscip, "conflict/useboundlp") )
1018  {
1019  SCIP_CALL( SCIPsetCharParam(subscip, "conflict/useboundlp", 'o') );
1020  }
1021  if( !SCIPisParamFixed(subscip, "conflict/maxstoresize") )
1022  {
1023  SCIP_CALL( SCIPsetIntParam(subscip, "conflict/maxstoresize", 100) );
1024  }
1025
1026  /* speed up sub-SCIP by not checking dual LP feasibility */
1027  SCIP_CALL( SCIPsetBoolParam(subscip, "lp/checkdualfeas", FALSE) );
1028
1029  /* employ a limit on the number of enforcement rounds in the quadratic constraint handlers; this fixes the issue that
1030  * sometimes the quadratic constraint handler needs hundreds or thousands of enforcement rounds to determine the
1031  * feasibility status of a single node without fractional branching candidates by separation (namely for uflquad
1032  * instances); however, the solution status of the sub-SCIP might get corrupted by this; hence no decutions shall be
1033  * made for the original SCIP
1034  */
1036  {
1037  SCIP_CALL( SCIPsetIntParam(subscip, "constraints/quadratic/enfolplimit", 10) );
1038  }
1039
1040  /* add an objective cutoff */
1041  assert( !SCIPisInfinity(scip, SCIPgetUpperbound(scip)) );
1042
1043  upperbound = SCIPgetUpperbound(scip) - SCIPsumepsilon(scip);
1044  if( !SCIPisInfinity(scip, -1.0 * SCIPgetLowerbound(scip)) )
1045  {
1046  cutoff = (1 - heurdata->minimprove) * SCIPgetUpperbound(scip)
1047  + heurdata->minimprove * SCIPgetLowerbound(scip);
1048  }
1049  else
1050  {
1051  if( SCIPgetUpperbound(scip) >= 0 )
1052  cutoff = (1 - heurdata->minimprove) * SCIPgetUpperbound(scip);
1053  else
1054  cutoff = (1 + heurdata->minimprove) * SCIPgetUpperbound(scip);
1055  }
1056  cutoff = MIN(upperbound, cutoff);
1057  SCIP_CALL(SCIPsetObjlimit(subscip, cutoff));
1058
1059  /* set solve limits for sub-SCIP */
1060  SCIP_CALL( setLimits(subscip, solvelimits) );
1061
1062  return SCIP_OKAY;
1063 }
1064
1065 /** determine limits for a sub-SCIP */
1066 static
1068  SCIP* scip, /**< SCIP data structure */
1069  SCIP_HEUR* heur, /**< this heuristic */
1070  SOLVELIMITS* solvelimits, /**< pointer to solving limits data structure */
1071  SCIP_Bool* runagain /**< can we solve another sub-SCIP with these limits */
1072  )
1073 {
1074  SCIP_HEURDATA* heurdata;
1075  SCIP_Real maxnnodesr;
1076  SCIP_Longint maxnnodes;
1077  assert(scip != NULL);
1078  assert(heur != NULL);
1079  assert(solvelimits != NULL);
1080  assert(runagain != NULL);
1081
1082  heurdata = SCIPheurGetData(heur);
1083
1084  /* check whether there is enough time and memory left */
1085  SCIP_CALL( SCIPgetRealParam(scip, "limits/time", &solvelimits->timelimit) );
1086  if( !SCIPisInfinity(scip, solvelimits->timelimit) )
1087  solvelimits->timelimit -= SCIPgetSolvingTime(scip);
1088  SCIP_CALL( SCIPgetRealParam(scip, "limits/memory", &solvelimits->memorylimit) );
1089
1090  /* substract the memory already used by the main SCIP and the estimated memory usage of external software */
1091  if( !SCIPisInfinity(scip, solvelimits->memorylimit) )
1092  {
1093  solvelimits->memorylimit -= SCIPgetMemUsed(scip)/1048576.0;
1094  solvelimits->memorylimit -= SCIPgetMemExternEstim(scip)/1048576.0;
1095  }
1096
1097  /* abort if no time is left or not enough memory to create a copy of SCIP, including external memory usage */
1098  if( solvelimits->timelimit <= 0.0 || solvelimits->memorylimit <= 2.0*SCIPgetMemExternEstim(scip)/1048576.0 )
1099  *runagain = FALSE;
1100
1101  /* calculate the maximal number of branching nodes until heuristic is aborted */
1102  maxnnodesr = heurdata->nodesquot * SCIPgetNNodes(scip);
1103
1104  /* reward gins if it succeeded often, count the setup costs for the sub-MIP as 100 nodes */
1105  maxnnodesr *= 1.0 + 2.0 * (SCIPheurGetNBestSolsFound(heur)+1.0)/(heurdata->nsubmips + 1.0);
1106  maxnnodes = (SCIP_Longint)(maxnnodesr - 100.0 * heurdata->nsubmips);
1107  maxnnodes += heurdata->nodesofs;
1108
1109  /* determine the node limit for the current process */
1110  solvelimits->nodelimit = maxnnodes - heurdata->usednodes;
1111  solvelimits->nodelimit = MIN(solvelimits->nodelimit, heurdata->maxnodes);
1112
1113  /* check whether we have enough nodes left to call subproblem solving */
1114  if( solvelimits->nodelimit < heurdata->minnodes )
1115  *runagain = FALSE;
1116
1117  return SCIP_OKAY;
1118 }
1119
1120 /** updates heurdata after a run of GINS */
1121 static
1123  SCIP* scip, /**< original SCIP data structure */
1124  SCIP_HEURDATA* heurdata /**< primal heuristic data */
1125  )
1126 {
1127  /* increase number of failures, calculate next node at which GINS should be called and update actual solutions */
1128  heurdata->nfailures++;
1129  heurdata->nextnodenumber = (heurdata->nfailures <= 25
1130  ? SCIPgetNNodes(scip) + 100*(2LL << heurdata->nfailures) /*lint !e703*/
1131  : SCIP_LONGINT_MAX);
1132 }
1133
1134 #ifdef SCIP_STATISTIC
1135 /** gets the average neighborhood size of all selected variables */
1136 static
1137 SCIP_Real heurdataAvgNeighborhoodSize(
1138  SCIP_HEURDATA* heurdata /**< heuristic data */
1139  )
1140 {
1141  return heurdata->sumneighborhoodvars / (MAX(1.0, (SCIP_Real)heurdata->nneighborhoods));
1142 }
1143
1144 /** prints a histogram */
1145 static
1146 void printHistogram(
1147  SCIP* scip, /**< SCIP data structure */
1148  int* histogram, /**< histogram values */
1149  const char* name /**< display name of this histogram */
1150  )
1151 {
1152  int i;
1153
1154  SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL, "Gins: %s", name);
1155
1156  /* write out entries of this histogram */
1157  for( i = 0; i < NHISTOGRAMBINS; ++i )
1158  SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL, " %d", histogram[i]);
1160 }
1161 #endif
1162
1163 /*
1164  * Callback methods of primal heuristic
1165  */
1166
1167 /** copy method for primal heuristic plugins (called when SCIP copies plugins) */
1168 static
1169 SCIP_DECL_HEURCOPY(heurCopyGins)
1170 { /*lint --e{715}*/
1171  assert(scip != NULL);
1172  assert(heur != NULL);
1173  assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0);
1175  /* call inclusion method of primal heuristic */
1176  SCIP_CALL( SCIPincludeHeurGins(scip) );
1177
1178  return SCIP_OKAY;
1179 }
1180
1181 /** destructor of primal heuristic to free user data (called when SCIP is exiting) */
1182 static
1183 SCIP_DECL_HEURFREE(heurFreeGins)
1184 { /*lint --e{715}*/
1185  SCIP_HEURDATA* heurdata;
1186
1187  assert(heur != NULL);
1188  assert(scip != NULL);
1189
1190  /* get heuristic data */
1191  heurdata = SCIPheurGetData(heur);
1192  assert(heurdata != NULL);
1193
1194  /* free heuristic data */
1195  SCIPfreeBlockMemory(scip, &heurdata);
1196  SCIPheurSetData(heur, NULL);
1197
1198  return SCIP_OKAY;
1199 }
1200
1201 /** initialization method of primal heuristic (called after problem was transformed) */
1202 static
1203 SCIP_DECL_HEURINIT(heurInitGins)
1204 { /*lint --e{715}*/
1205  SCIP_HEURDATA* heurdata;
1206
1207  assert(heur != NULL);
1208  assert(scip != NULL);
1209
1210  /* get heuristic's data */
1211  heurdata = SCIPheurGetData(heur);
1212  assert(heurdata != NULL);
1213  assert(heurdata->randnumgen == NULL);
1214
1215  /* initialize data */
1216  heurdata->usednodes = 0;
1217  SCIP_CALL( SCIPcreateRandom(scip, &heurdata->randnumgen, DEFAULT_RANDSEED, TRUE) );
1218  heurdata->sumdiscneighborhoodvars = heurdata->sumneighborhoodvars = 0;
1219  heurdata->nneighborhoods = 0;
1220  heurdata->maxseendistance = 0;
1221  heurdata->nsubmips = 0;
1222  heurdata->nfailures = 0;
1223  heurdata->nextnodenumber = 0;
1224
1225 #ifdef SCIP_STATISTIC
1226  resetHistogram(heurdata->conscontvarshist);
1227  resetHistogram(heurdata->consdiscvarshist);
1228  resetHistogram(heurdata->conscontvarshist);
1229 #endif
1230
1231  return SCIP_OKAY;
1232 }
1233
1234 /** initialization method of primal heuristic (called after problem was transformed) */
1235 static
1236 SCIP_DECL_HEUREXIT(heurExitGins)
1237 { /*lint --e{715}*/
1238  SCIP_HEURDATA* heurdata;
1239
1240  assert(heur != NULL);
1241  assert(scip != NULL);
1242
1243  /* get heuristic's data */
1244  heurdata = SCIPheurGetData(heur);
1245  assert(heurdata != NULL);
1246
1247  SCIPstatistic(
1248  SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL, "Gins: Avg Neighborhood size: %.1f Avg. discrete neighboorhood vars: %.1f\n",
1249  heurdataAvgNeighborhoodSize(heurdata), heurdataAvgDiscreteNeighborhoodSize(heurdata));
1250  SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL, "Gins: Max seen distance %d\n", heurdata->maxseendistance);
1251  printHistogram(scip, heurdata->consvarshist, "Constraint density histogram");
1252  printHistogram(scip, heurdata->conscontvarshist, "Constraint continuous density histogram");
1253  printHistogram(scip, heurdata->consdiscvarshist, "Constraint discrete density histogram");
1254  )
1255
1256  SCIPfreeRandom(scip, &heurdata->randnumgen);
1257  heurdata->randnumgen = NULL;
1258
1259  return SCIP_OKAY;
1260 }
1261
1262 /** execution method of primal heuristic */
1263 static
1264 SCIP_DECL_HEUREXEC(heurExecGins)
1265 { /*lint --e{715}*/
1266  SCIP_HEURDATA* heurdata; /* heuristic's data */
1267  SCIP* subscip; /* the subproblem created by gins */
1268  SCIP_VAR** vars; /* original problem's variables */
1269  SCIP_VAR** subvars; /* subproblem's variables */
1270  SCIP_VAR** fixedvars;
1271  SCIP_Real* fixedvals;
1272  ROLLINGHORIZON* rollinghorizon; /* data structure for rolling horizon approach */
1273  SCIP_HASHMAP* varmapfw; /* mapping of SCIP variables to sub-SCIP variables */
1274
1275  int nvars; /* number of original problem's variables */
1276  int i;
1277  int nfixedvars;
1278  SOLVELIMITS solvelimits;
1279  SCIP_Bool runagain;
1280
1281  SCIP_Bool success;
1282
1283  assert(heur != NULL);
1284  assert(scip != NULL);
1285  assert(result != NULL);
1286
1287  /* get heuristic's data */
1288  heurdata = SCIPheurGetData(heur);
1289  assert(heurdata != NULL);
1290
1291  *result = SCIP_DELAYED;
1292
1293  /* only call heuristic, if feasible solution is available */
1294  if( SCIPgetNSols(scip) <= 0 )
1295  return SCIP_OKAY;
1296
1297  /* in case of many unsuccessful calls, the nextnodenumber is increased to prevent us from running too often */
1298  if( SCIPgetNNodes(scip) < heurdata->nextnodenumber )
1299  return SCIP_OKAY;
1300
1301  /* only call heuristic, if the best solution comes from transformed problem */
1302  assert(SCIPgetBestSol(scip) != NULL);
1303  if( SCIPsolIsOriginal(SCIPgetBestSol(scip)) )
1304  return SCIP_OKAY;
1305
1306  /* only call heuristic, if enough nodes were processed since last incumbent */
1307  if( SCIPgetNNodes(scip) - SCIPgetSolNodenum(scip,SCIPgetBestSol(scip)) < heurdata->nwaitingnodes )
1308  return SCIP_OKAY;
1309
1310  *result = SCIP_DIDNOTRUN;
1311
1312  /* only call heuristic, if discrete variables are present */
1313  if( SCIPgetNBinVars(scip) == 0 && SCIPgetNIntVars(scip) == 0 )
1314  return SCIP_OKAY;
1315
1316  if( SCIPisStopped(scip) )
1317  return SCIP_OKAY;
1318
1319  runagain = TRUE;
1320
1321  /* determine solving limits for the sub-SCIP for the first time */
1322  SCIP_CALL( determineLimits(scip, heur, &solvelimits, &runagain) );
1323
1324  if( ! runagain )
1325  return SCIP_OKAY;
1326
1327  *result = SCIP_DIDNOTFIND;
1328
1329  SCIP_CALL( SCIPgetVarsData(scip, &vars, &nvars, NULL, NULL, NULL, NULL) );
1330  SCIP_CALL( SCIPallocBufferArray(scip, &fixedvars, nvars) );
1331  SCIP_CALL( SCIPallocBufferArray(scip, &fixedvals, nvars) );
1332
1333  /* only create a rolling horizon data structure if we need to keep it */
1334  if( heurdata->userollinghorizon )
1335  SCIP_CALL( rollingHorizonCreate(scip, &rollinghorizon) );
1336  else
1337  rollinghorizon = NULL;
1338
1339  do
1340  {
1341  /* create a new problem, by fixing all variables except for a small neighborhood */
1342  SCIP_CALL( determineVariableFixings(scip, fixedvars, fixedvals, &nfixedvars, heurdata, rollinghorizon, &success) );
1343
1344  /* terminate if it was not possible to create the subproblem */
1345  if( !success )
1346  {
1347  SCIPdebugMsg(scip, "Could not create the subproblem -> skip call\n");
1348
1349  /* do not count this as a call to the heuristic */
1350  *result = SCIP_DIDNOTRUN;
1351
1352  /* count this as a failure and increase the number of waiting nodes until the next call */
1353  updateFailureStatistic(scip, heurdata);
1354  goto TERMINATE;
1355  }
1356
1357  /* initializing the subproblem */
1358  SCIP_CALL( SCIPallocBufferArray(scip, &subvars, nvars) );
1359  SCIP_CALL( SCIPcreate(&subscip) );
1360  ++heurdata->nsubmips;
1361
1362  /* create the variable mapping hash map */
1363  SCIP_CALL( SCIPhashmapCreate(&varmapfw, SCIPblkmem(subscip), nvars) );
1364
1365  /* create a problem copy as sub SCIP */
1366  SCIP_CALL( SCIPcopyLargeNeighborhoodSearch(scip, subscip, varmapfw, "gins", fixedvars, fixedvals, nfixedvars,
1367  heurdata->uselprows, heurdata->copycuts, &success, NULL) );
1368
1369  for( i = 0; i < nvars; i++ )
1370  subvars[i] = (SCIP_VAR*) SCIPhashmapGetImage(varmapfw, vars[i]);
1371
1372  /* free hash map */
1373  SCIPhashmapFree(&varmapfw);
1374
1375  /* set up limits for the subproblem */
1376  SCIP_CALL( setupSubScip(scip, subscip, &solvelimits, heur) );
1377
1378  /* solve the subproblem */
1379  SCIPdebugMsg(scip, "Solve Gins subMIP\n");
1380
1381  /* Errors in solving the subproblem should not kill the overall solving process
1382  * Hence, the return code is caught and a warning is printed, only in debug mode, SCIP will stop.
1383  */
1384  SCIP_CALL_ABORT( SCIPsolve(subscip) );
1385
1386  /* transfer variable statistics from sub-SCIP */
1387  SCIP_CALL( SCIPmergeVariableStatistics(subscip, scip, subvars, vars, nvars) );
1388
1389  heurdata->usednodes += SCIPgetNNodes(subscip);
1390
1391  /* check, whether a solution was found */
1392  if( SCIPgetNSols(subscip) > 0 )
1393  {
1394  SCIP_SOL** subsols;
1395  int nsubsols;
1396
1397  /* check, whether a solution was found;
1398  * due to numerics, it might happen that not all solutions are feasible -> try all solutions until one was accepted
1399  */
1400  nsubsols = SCIPgetNSols(subscip);
1401  subsols = SCIPgetSols(subscip);
1402  success = FALSE;
1403  for( i = 0; i < nsubsols && !success; ++i )
1404  {
1405  SCIP_CALL( createNewSol(scip, subscip, subvars, heur, subsols[i], &success) );
1406  }
1407  if( success )
1408  *result = SCIP_FOUNDSOL;
1409  }
1410
1411  /* free subproblem */
1412  SCIPfreeBufferArray(scip, &subvars);
1413  SCIP_CALL( SCIPfree(&subscip) );
1414
1415  /* check if we want to run another rolling horizon iteration */
1416  runagain = (*result == SCIP_FOUNDSOL) && heurdata->userollinghorizon;
1417  if( runagain )
1418  {
1419  assert(rollinghorizon != NULL);
1420  SCIP_CALL( determineLimits(scip, heur, &solvelimits, &runagain ) );
1421  runagain = runagain && rollingHorizonRunAgain(scip, rollinghorizon, heurdata);
1422  }
1423  }
1424  while( runagain );
1425
1426  /* delay the heuristic in case it was not successful */
1427  if( *result != SCIP_FOUNDSOL )
1428  updateFailureStatistic(scip, heurdata);
1429
1430 TERMINATE:
1431
1432  /* only free the rolling horizon data structure if we need to keep it */
1433  if( heurdata->userollinghorizon )
1434  {
1435  SCIP_CALL( rollingHorizonFree(scip, &rollinghorizon) );
1436  }
1437
1438  SCIPfreeBufferArray(scip, &fixedvals);
1439  SCIPfreeBufferArray(scip, &fixedvars);
1440
1441  return SCIP_OKAY;
1442 }
1443
1444 /*
1445  * primal heuristic specific interface methods
1446  */
1447
1448 /** creates the gins primal heuristic and includes it in SCIP */
1450  SCIP* scip /**< SCIP data structure */
1451  )
1452 {
1453  SCIP_HEURDATA* heurdata;
1454  SCIP_HEUR* heur;
1455
1456  /* create Gins primal heuristic data */
1457  SCIP_CALL( SCIPallocBlockMemory(scip, &heurdata) );
1458  heurdata->randnumgen = NULL;
1459
1460  /* include primal heuristic */
1461  SCIP_CALL( SCIPincludeHeurBasic(scip, &heur,
1463  HEUR_MAXDEPTH, HEUR_TIMING, HEUR_USESSUBSCIP, heurExecGins, heurdata) );
1464
1465  assert(heur != NULL);
1466
1467  /* set non-NULL pointers to callback methods */
1468  SCIP_CALL( SCIPsetHeurCopy(scip, heur, heurCopyGins) );
1469  SCIP_CALL( SCIPsetHeurFree(scip, heur, heurFreeGins) );
1470  SCIP_CALL( SCIPsetHeurInit(scip, heur, heurInitGins) );
1471  SCIP_CALL( SCIPsetHeurExit(scip, heur, heurExitGins) );
1472
1473  /* add gins primal heuristic parameters */
1474  SCIP_CALL( SCIPaddIntParam(scip, "heuristics/" HEUR_NAME "/nodesofs",
1475  "number of nodes added to the contingent of the total nodes",
1476  &heurdata->nodesofs, FALSE, DEFAULT_NODESOFS, 0, INT_MAX, NULL, NULL) );
1477
1478  SCIP_CALL( SCIPaddIntParam(scip, "heuristics/" HEUR_NAME "/maxnodes",
1479  "maximum number of nodes to regard in the subproblem",
1480  &heurdata->maxnodes, TRUE, DEFAULT_MAXNODES, 0, INT_MAX, NULL, NULL) );
1481
1482  SCIP_CALL( SCIPaddIntParam(scip, "heuristics/" HEUR_NAME "/minnodes",
1483  "minimum number of nodes required to start the subproblem",
1484  &heurdata->minnodes, TRUE, DEFAULT_MINNODES, 0, INT_MAX, NULL, NULL) );
1485
1486  SCIP_CALL( SCIPaddIntParam(scip, "heuristics/" HEUR_NAME "/nwaitingnodes",
1487  "number of nodes without incumbent change that heuristic should wait",
1488  &heurdata->nwaitingnodes, TRUE, DEFAULT_NWAITINGNODES, 0, INT_MAX, NULL, NULL) );
1489
1490  SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/nodesquot",
1491  "contingent of sub problem nodes in relation to the number of nodes of the original problem",
1492  &heurdata->nodesquot, FALSE, DEFAULT_NODESQUOT, 0.0, 1.0, NULL, NULL) );
1493
1494  SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/minfixingrate",
1495  "percentage of integer variables that have to be fixed",
1496  &heurdata->minfixingrate, FALSE, DEFAULT_MINFIXINGRATE, SCIPsumepsilon(scip), 1.0-SCIPsumepsilon(scip), NULL, NULL) );
1497
1498  SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/minimprove",
1499  "factor by which " HEUR_NAME " should at least improve the incumbent",
1500  &heurdata->minimprove, TRUE, DEFAULT_MINIMPROVE, 0.0, 1.0, NULL, NULL) );
1501
1502  SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/uselprows",
1503  "should subproblem be created out of the rows in the LP rows?",
1504  &heurdata->uselprows, TRUE, DEFAULT_USELPROWS, NULL, NULL) );
1505
1506  SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/copycuts",
1507  "if uselprows == FALSE, should all active cuts from cutpool be copied to constraints in subproblem?",
1508  &heurdata->copycuts, TRUE, DEFAULT_COPYCUTS, NULL, NULL) );
1509
1510  SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/fixcontvars",
1511  "should continuous variables outside the neighborhoods be fixed?",
1512  &heurdata->fixcontvars, TRUE, DEFAULT_FIXCONTVARS, NULL, NULL) );
1513
1514  SCIP_CALL( SCIPaddIntParam(scip, "heuristics/" HEUR_NAME "/bestsollimit",
1515  "limit on number of improving incumbent solutions in sub-CIP",
1516  &heurdata->bestsollimit, FALSE, DEFAULT_BESTSOLLIMIT, -1, INT_MAX, NULL, NULL) );
1517
1518  SCIP_CALL( SCIPaddIntParam(scip, "heuristics/" HEUR_NAME "/maxdistance",
1519  "maximum distance to selected variable to enter the subproblem, or -1 to select the distance "
1520  "that best approximates the minimum fixing rate from below",
1521  &heurdata->maxdistance, FALSE, DEFAULT_MAXDISTANCE, -1, INT_MAX, NULL, NULL) );
1522
1523  SCIP_CALL( SCIPaddCharParam(scip, "heuristics/" HEUR_NAME "/potential",
1524  "the reference point to compute the neighborhood potential: (r)oot or (p)seudo solution",
1525  &heurdata->potential, TRUE, DEFAULT_POTENTIAL, "pr", NULL, NULL) );
1526
1527  SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/userollinghorizon",
1528  "should the heuristic solve a sequence of sub-MIP's around the first selected variable",
1529  &heurdata->userollinghorizon, TRUE, DEFAULT_USEROLLINGHORIZON, NULL, NULL) );
1530
1531  SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/relaxdenseconss",
1532  "should dense constraints (at least as dense as 1 - minfixingrate) be ignored by connectivity graph?",
1533  &heurdata->relaxdenseconss, TRUE, DEFAULT_RELAXDENSECONSS, NULL, NULL) );
1534
1535  SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/rollhorizonlimfac",
1536  "limiting percentage for variables already used in sub-SCIPs to terminate rolling horizon approach",
1537  &heurdata->rollhorizonlimfac, TRUE, DEFAULT_ROLLHORIZONLIMFAC, 0.0, 1.0, NULL, NULL) );
1538
1539  return SCIP_OKAY;
1540 }
static SCIP_Real heurdataAvgDiscreteNeighborhoodSize(SCIP_HEURDATA *heurdata)
Definition: heur_gins.c:518
#define SCIPfreeBlockMemoryArray(scip, ptr, num)
Definition: scip_mem.h:97
static SCIP_RETCODE rollingHorizonCreate(SCIP *scip, ROLLINGHORIZON **rollinghorizon)
Definition: heur_gins.c:222
SCIP_Bool SCIPisPositive(SCIP *scip, SCIP_Real val)
#define NULL
Definition: def.h:253
SCIP_Bool SCIPisStopped(SCIP *scip)
Definition: scip_general.c:686
SCIP_Real SCIPsumepsilon(SCIP *scip)
#define SCIPallocBlockMemoryArray(scip, ptr, num)
Definition: scip_mem.h:80
SCIP_CONSHDLR * SCIPfindConshdlr(SCIP *scip, const char *name)
Definition: scip_cons.c:876
const char * SCIPheurGetName(SCIP_HEUR *heur)
Definition: heur.c:1254
public methods for SCIP parameter handling
static void rollingHorizonStoreDistances(SCIP *scip, ROLLINGHORIZON *rollinghorizon, int *distances)
Definition: heur_gins.c:285
void SCIPfreeRandom(SCIP *scip, SCIP_RANDNUMGEN **randnumgen)
static SCIP_DECL_HEURCOPY(heurCopyGins)
Definition: heur_gins.c:1174
public methods for node selector plugins
public methods for memory management
#define DEFAULT_MAXDISTANCE
Definition: heur_gins.c:95
SCIP_HEURDATA * SCIPheurGetData(SCIP_HEUR *heur)
Definition: heur.c:1165
#define HEUR_FREQ
Definition: heur_gins.c:73
#define DEFAULT_NODESOFS
Definition: heur_gins.c:79
SCIP_EXPORT SCIP_Bool SCIPsolIsOriginal(SCIP_SOL *sol)
Definition: sol.c:2470
#define SCIPallocClearBlockMemoryArray(scip, ptr, num)
Definition: scip_mem.h:84
SCIP_Real SCIPgetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var)
Definition: scip_sol.c:1352
public solving methods
public methods for timing
static SCIP_RETCODE selectNextVariable(SCIP *scip, SCIP_HEURDATA *heurdata, ROLLINGHORIZON *rollinghorizon, int *distances, SCIP_VAR **selvar, int *selvarmaxdistance)
Definition: heur_gins.c:717
SCIP_RETCODE SCIPvariableGraphCreate(SCIP *scip, SCIP_VGRAPH **vargraph, SCIP_Bool relaxdenseconss, SCIP_Real relaxdensity, int *nrelaxedconstraints)
Definition: heur.c:1792
SCIP_RETCODE SCIPvariablegraphBreadthFirst(SCIP *scip, SCIP_VGRAPH *vargraph, SCIP_VAR **startvars, int nstartvars, int *distances, int maxdistance, int maxvars, int maxbinintvars)
Definition: heur.c:1491
SCIP_Real SCIPgetSolvingTime(SCIP *scip)
Definition: scip_timing.c:359
void SCIPverbMessage(SCIP *scip, SCIP_VERBLEVEL msgverblevel, FILE *file, const char *formatstr,...)
Definition: scip_message.c:215
#define FALSE
Definition: def.h:73
SCIP_EXPORT SCIP_Real SCIPvarGetObj(SCIP_VAR *var)
Definition: var.c:17200
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:794
static SCIP_RETCODE setLimits(SCIP *subscip, SOLVELIMITS *solvelimits)
Definition: heur_gins.c:955
#define TRUE
Definition: def.h:72
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:53
methods commonly used by primal heuristics
#define DEFAULT_MAXNODES
Definition: heur_gins.c:80
#define DEFAULT_MINFIXINGRATE
Definition: heur_gins.c:83
SCIP_RETCODE SCIPsolve(SCIP *scip)
Definition: scip_solve.c:2535
void * SCIPhashmapGetImage(SCIP_HASHMAP *hashmap, void *origin)
Definition: misc.c:3078
struct SCIP_HeurData SCIP_HEURDATA
Definition: type_heur.h:51
SCIP_EXPORT SCIP_Bool SCIPvarIsActive(SCIP_VAR *var)
Definition: var.c:17025
public methods for problem variables
#define HEUR_DISPCHAR
Definition: heur_gins.c:71
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_param.c:47
#define SCIPfreeBlockMemory(scip, ptr)
Definition: scip_mem.h:95
SCIP_Longint SCIPgetMemUsed(SCIP *scip)
Definition: scip_mem.c:90
SCIP_Real timelimit
Definition: heur_alns.c:446
SCIP_RETCODE SCIPsetSubscipsOff(SCIP *scip, SCIP_Bool quiet)
Definition: scip_param.c:891
#define SCIPduplicateBufferArray(scip, ptr, source, num)
Definition: scip_mem.h:119
SCIP_Real SCIPgetUpperbound(SCIP *scip)
#define SCIP_LONGINT_MAX
Definition: def.h:150
#define SCIPfreeBufferArray(scip, ptr)
Definition: scip_mem.h:123
#define SCIPallocBlockMemory(scip, ptr)
Definition: scip_mem.h:78
static SCIP_RETCODE determineMaxDistance(SCIP *scip, SCIP_HEURDATA *heurdata, int *distances, int *choosevardistance)
Definition: heur_gins.c:462
SCIP_RETCODE SCIPsetHeurInit(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURINIT((*heurinit)))
Definition: scip_heur.c:184
#define SCIPdebugMsg
Definition: scip_message.h:69
#define DEFAULT_ROLLHORIZONLIMFAC
Definition: heur_gins.c:103
SCIP_EXPORT void SCIPsortInt(int *intarray, int len)
SCIP_Longint SCIPheurGetNBestSolsFound(SCIP_HEUR *heur)
Definition: heur.c:1400
int lastmaxdistance
Definition: heur_gins.c:123
SCIP_Bool SCIPisInfinity(SCIP *scip, SCIP_Real val)
int SCIPgetNIntVars(SCIP *scip)
Definition: scip_prob.c:2077
public methods for numerical tolerances
SCIP_RETCODE SCIPcreateRandom(SCIP *scip, SCIP_RANDNUMGEN **randnumgen, unsigned int initialseed, SCIP_Bool useglobalseed)
SCIP_RETCODE SCIPcreateSol(SCIP *scip, SCIP_SOL **sol, SCIP_HEUR *heur)
Definition: scip_sol.c:319
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:895
SCIP_RETCODE SCIPsetObjlimit(SCIP *scip, SCIP_Real objlimit)
Definition: scip_prob.c:1421
public methods for querying solving statistics
int SCIPgetNSols(SCIP *scip)
Definition: scip_sol.c:2205
SCIP_EXPORT SCIP_Real SCIPvarGetRootSol(SCIP_VAR *var)
Definition: var.c:12842
SCIP_Bool SCIPisLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_RETCODE SCIPsetRealParam(SCIP *scip, const char *name, SCIP_Real value)
Definition: scip_param.c:612
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_heur.c:107
SCIP_Longint SCIPgetNNodes(SCIP *scip)
SCIP_RETCODE SCIPcreate(SCIP **scip)
Definition: scip_general.c:282
SCIP_Real memorylimit
Definition: heur_alns.c:445
SCIP_EXPORT const char * SCIPvarGetName(SCIP_VAR *var)
Definition: var.c:16738
#define HEUR_NAME
Definition: heur_gins.c:69
#define DEFAULT_FIXCONTVARS
Definition: heur_gins.c:93
SCIP_EXPORT SCIP_Bool SCIPvarIsIntegral(SCIP_VAR *var)
Definition: var.c:16929
#define DEFAULT_USEROLLINGHORIZON
Definition: heur_gins.c:102
#define SCIPerrorMessage
Definition: pub_message.h:45
SCIP_BRANCHRULE * SCIPfindBranchrule(SCIP *scip, const char *name)
Definition: scip_branch.c:286
static void updateFailureStatistic(SCIP *scip, SCIP_HEURDATA *heurdata)
Definition: heur_gins.c:1127
SCIP_VGRAPH * variablegraph
Definition: heur_gins.c:118
BMS_BLKMEM * SCIPblkmem(SCIP *scip)
Definition: scip_mem.c:47
SCIP_Bool SCIPisZero(SCIP *scip, SCIP_Real val)
SCIP_EXPORT SCIP_Bool SCIPsortedvecFindInt(int *intarray, int val, int len, int *pos)
LNS heuristic that tries to delimit the search region to a neighborhood in the constraint graph...
void SCIPheurSetData(SCIP_HEUR *heur, SCIP_HEURDATA *heurdata)
Definition: heur.c:1175
static SCIP_RETCODE setupSubScip(SCIP *scip, SCIP *subscip, SOLVELIMITS *solvelimits, SCIP_HEUR *heur)
Definition: heur_gins.c:972
#define DEFAULT_RELAXDENSECONSS
Definition: heur_gins.c:99
#define REALABS(x)
Definition: def.h:188
SCIP_RETCODE SCIPmergeVariableStatistics(SCIP *sourcescip, SCIP *targetscip, SCIP_VAR **sourcevars, SCIP_VAR **targetvars, int nvars)
Definition: scip_copy.c:1180
public methods for problem copies
public methods for primal CIP solutions
SCIP_NODESEL * SCIPfindNodesel(SCIP *scip, const char *name)
Definition: scip_nodesel.c:224
#define SCIP_CALL(x)
Definition: def.h:365
#define HEUR_FREQOFS
Definition: heur_gins.c:74
#define DEFAULT_POTENTIAL
Definition: heur_gins.c:94
SCIP_RETCODE SCIPsetPresolving(SCIP *scip, SCIP_PARAMSETTING paramsetting, SCIP_Bool quiet)
Definition: scip_param.c:940
static SCIP_DECL_HEURFREE(heurFreeGins)
Definition: heur_gins.c:1188
#define DEFAULT_NODESQUOT
Definition: heur_gins.c:84
SCIP_RETCODE SCIPsetCharParam(SCIP *scip, const char *name, char value)
Definition: scip_param.c:670
SCIP_Longint nodelimit
Definition: heur_alns.c:444
int SCIPgetNOrigVars(SCIP *scip)
Definition: scip_prob.c:2427
static SCIP_DECL_HEUREXEC(heurExecGins)
Definition: heur_gins.c:1269
public methods for primal heuristic plugins and divesets
public methods for constraint handler plugins and constraints
#define DEFAULT_BESTSOLLIMIT
Definition: heur_gins.c:92
void SCIPvariableGraphFree(SCIP *scip, SCIP_VGRAPH **vargraph)
Definition: heur.c:1830
SCIP_RETCODE SCIPgetRealParam(SCIP *scip, const char *name, SCIP_Real *value)
Definition: scip_param.c:297
SCIP_Longint SCIPgetSolNodenum(SCIP *scip, SCIP_SOL *sol)
Definition: scip_sol.c:1648
#define DEFAULT_MINNODES
Definition: heur_gins.c:82
#define SCIPallocBufferArray(scip, ptr, num)
Definition: scip_mem.h:111
#define DEFAULT_USELPROWS
Definition: heur_gins.c:86
public data structures and miscellaneous methods
int SCIPrandomGetInt(SCIP_RANDNUMGEN *randnumgen, int minrandval, int maxrandval)
Definition: misc.c:9618
SCIP_RETCODE SCIPsetSolVals(SCIP *scip, SCIP_SOL *sol, int nvars, SCIP_VAR **vars, SCIP_Real *vals)
Definition: scip_sol.c:1254
#define SCIP_Bool
Definition: def.h:70
SCIP_RETCODE SCIPhashmapCreate(SCIP_HASHMAP **hashmap, BMS_BLKMEM *blkmem, int mapsize)
Definition: misc.c:2891
SCIP_RETCODE SCIPsetHeurExit(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEUREXIT((*heurexit)))
Definition: scip_heur.c:200
SCIP_EXPORT SCIP_Real SCIPvarGetUbGlobal(SCIP_VAR *var)
Definition: var.c:17362
#define DEFAULT_COPYCUTS
Definition: heur_gins.c:89
SCIP_RETCODE SCIPincludeHeurGins(SCIP *scip)
Definition: heur_gins.c:1454
static SCIP_RETCODE selectInitialVariable(SCIP *scip, SCIP_HEURDATA *heurdata, SCIP_VGRAPH *vargraph, int *distances, SCIP_VAR **selvar, int *selvarmaxdistance)
Definition: heur_gins.c:527
SCIP_Bool SCIPisParamFixed(SCIP *scip, const char *name)
Definition: scip_param.c:209
static SCIP_Bool rollingHorizonRunAgain(SCIP *scip, ROLLINGHORIZON *rollinghorizon, SCIP_HEURDATA *heurdata)
Definition: heur_gins.c:268
#define MIN(x, y)
Definition: def.h:223
#define BMScopyMemoryArray(ptr, source, num)
Definition: memory.h:124
#define HEUR_PRIORITY
Definition: heur_gins.c:72
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_param.c:129
#define HEUR_TIMING
Definition: heur_gins.c:76
#define SCIP_REAL_MIN
Definition: def.h:166
static SCIP_DECL_HEURINIT(heurInitGins)
Definition: heur_gins.c:1208
SCIP_RETCODE SCIPsetLongintParam(SCIP *scip, const char *name, SCIP_Longint value)
Definition: scip_param.c:554
methods for sorting joint arrays of various types
SCIP_RETCODE SCIPgetSolVals(SCIP *scip, SCIP_SOL *sol, int nvars, SCIP_VAR **vars, SCIP_Real *vals)
Definition: scip_sol.c:1389
static SCIP_RETCODE determineLimits(SCIP *scip, SCIP_HEUR *heur, SOLVELIMITS *solvelimits, SCIP_Bool *runagain)
Definition: heur_gins.c:1072
public methods for branching rule plugins and branching
general public methods
#define MAX(x, y)
Definition: def.h:222
public methods for solutions
public methods for random numbers
static SCIP_RETCODE createNewSol(SCIP *scip, SCIP *subscip, SCIP_VAR **subvars, SCIP_HEUR *heur, SCIP_SOL *subsol, SCIP_Bool *success)
Definition: heur_gins.c:909
#define DEFAULT_MINIMPROVE
Definition: heur_gins.c:81
SCIP_SOL ** SCIPgetSols(SCIP *scip)
Definition: scip_sol.c:2254
SCIP_Real SCIPgetLowerbound(SCIP *scip)
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:389
SCIP_EXPORT SCIP_Real SCIPvarGetLbGlobal(SCIP_VAR *var)
Definition: var.c:17352
SCIP_RETCODE SCIPsetHeurCopy(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURCOPY((*heurcopy)))
Definition: scip_heur.c:152
public methods for message output
SCIP_RETCODE SCIPgetVarsData(SCIP *scip, SCIP_VAR ***vars, int *nvars, int *nbinvars, int *nintvars, int *nimplvars, int *ncontvars)
Definition: scip_prob.c:1861
int * distances
Definition: heur_gins.c:119
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_param.c:73
void SCIPhashmapFree(SCIP_HASHMAP **hashmap)
Definition: misc.c:2925
#define SCIPstatistic(x)
Definition: pub_message.h:101
#define SCIP_Real
Definition: def.h:164
SCIP_Bool SCIPisLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
public methods for message handling
SCIP_Bool SCIPisGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
static SCIP_DECL_HEUREXIT(heurExitGins)
Definition: heur_gins.c:1241
#define SCIP_Longint
Definition: def.h:149
static SCIP_Real getPotential(SCIP *scip, SCIP_HEURDATA *heurdata, SCIP_SOL *sol, SCIP_VAR **vars, int nvars)
Definition: heur_gins.c:308
SCIP_RETCODE SCIPsetBoolParam(SCIP *scip, const char *name, SCIP_Bool value)
Definition: scip_param.c:438
int SCIPgetNBinVars(SCIP *scip)
Definition: scip_prob.c:2032
SCIP_RETCODE SCIPsetHeurFree(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURFREE((*heurfree)))
Definition: scip_heur.c:168
SCIP_EXPORT int SCIPvarGetProbindex(SCIP_VAR *var)
Definition: var.c:17045
static SCIP_RETCODE rollingHorizonFree(SCIP *scip, ROLLINGHORIZON **rollinghorizon)
Definition: heur_gins.c:246
#define HEUR_MAXDEPTH
Definition: heur_gins.c:75
#define BMSclearMemoryArray(ptr, num)
Definition: memory.h:120
public methods for primal heuristics
SCIP_RETCODE SCIPfree(SCIP **scip)
Definition: scip_general.c:314
SCIP_Longint SCIPgetMemExternEstim(SCIP *scip)
Definition: scip_mem.c:116
#define DEFAULT_NWAITINGNODES
Definition: heur_gins.c:85
#define SCIP_CALL_ABORT(x)
Definition: def.h:344
SCIP_Bool * used
Definition: heur_gins.c:121
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_sol.c:3218
#define HEUR_DESC
Definition: heur_gins.c:70
public methods for global and local (sub)problems
static SCIP_Bool isVariableInNeighborhood(SCIP_VAR *var, int *distances, int maxdistance)
Definition: heur_gins.c:373
#define HEUR_USESSUBSCIP
Definition: heur_gins.c:77
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_param.c:157
SCIP_SOL * SCIPgetBestSol(SCIP *scip)
Definition: scip_sol.c:2304
SCIP_RETCODE SCIPsetIntParam(SCIP *scip, const char *name, int value)
Definition: scip_param.c:496
SCIP_RETCODE SCIPsetSeparating(SCIP *scip, SCIP_PARAMSETTING paramsetting, SCIP_Bool quiet)
Definition: scip_param.c:966
#define DEFAULT_RANDSEED
Definition: heur_gins.c:98
memory allocation routines