# 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 scipopt.org. */
13 /* */
14 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
15
16 /**@file heur_gins.c
17  * @ingroup DEFPLUGINS_HEUR
18  * @brief LNS heuristic that tries to delimit the search region to a neighborhood in the constraint graph
19  * @author Gregor Hendel
20  *
21  * Graph Induced Neighborhood Search (GINS) is a Large Neighborhood Search Heuristic that attempts to improve
22  * an incumbent solution by fixing a suitable percentage of integer variables to the incumbent and
23  * solving the resulting, smaller and presumably easier sub-MIP.
24  *
25  * Its search neighborhoods are based on distances in a bipartite graph \f$G\f$ with the variables and constraints as nodes
26  * and an edge between a variable and a constraint, if the variable is part of the constraint.
27  * 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
28  * are connected to \f$v\f$ by a path not longer than \f$2 \cdot k\f$. Intuitively, a judiciously chosen neighborhood size
29  * allows to consider a local portion of the overall problem.
30  *
31  * An initial variable selection is made by randomly sampling different neighborhoods across the whole main problem.
32  * The neighborhood that offers the largest potential for improvement is selected to become the local search neighborhood,
33  * while all variables outside the neighborhood are fixed to their incumbent solution values.
34  *
35  * GINS also supports a rolling horizon approach, during which several local neighborhoods are considered
36  * with increasing distance to the variable selected for the initial sub-problem. The rolling horizon approach ends
37  * if no improvement could be found or a sufficient part of the problem component variables has been part of
38  * at least one neighborhood.
39  */
40
41 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
42
43 #include "blockmemshell/memory.h"
44 #include "scip/heur_gins.h"
45 #include "scip/heuristics.h"
46 #include "scip/pub_dcmp.h"
47 #include "scip/pub_heur.h"
48 #include "scip/pub_message.h"
49 #include "scip/pub_misc.h"
50 #include "scip/pub_misc_sort.h"
51 #include "scip/pub_sol.h"
52 #include "scip/pub_var.h"
53 #include "scip/scip_branch.h"
54 #include "scip/scip_cons.h"
55 #include "scip/scip_copy.h"
56 #include "scip/scip_dcmp.h"
57 #include "scip/scip_general.h"
58 #include "scip/scip_heur.h"
59 #include "scip/scip_mem.h"
60 #include "scip/scip_message.h"
61 #include "scip/scip_nodesel.h"
62 #include "scip/scip_numerics.h"
63 #include "scip/scip_param.h"
64 #include "scip/scip_prob.h"
65 #include "scip/scip_randnumgen.h"
66 #include "scip/scip_sol.h"
67 #include "scip/scip_solve.h"
68 #include "scip/scip_solvingstats.h"
69 #include "scip/scip_timing.h"
70 #include <string.h>
71
72 #define HEUR_NAME "gins"
73 #define HEUR_DESC "gins works on k-neighborhood in a variable-constraint graph"
74 #define HEUR_DISPCHAR SCIP_HEURDISPCHAR_LNS
75 #define HEUR_PRIORITY -1103000
76 #define HEUR_FREQ 20
77 #define HEUR_FREQOFS 8
78 #define HEUR_MAXDEPTH -1
79 #define HEUR_TIMING SCIP_HEURTIMING_AFTERNODE
80 #define HEUR_USESSUBSCIP TRUE /**< does the heuristic use a secondary SCIP instance? */
81
82 #define DEFAULT_NODESOFS 500 /**< number of nodes added to the contingent of the total nodes */
83 #define DEFAULT_MAXNODES 5000 /**< maximum number of nodes to regard in the subproblem */
84 #define DEFAULT_MINIMPROVE 0.01 /**< factor by which Gins should at least improve the incumbent */
85 #define DEFAULT_MINNODES 50 /**< minimum number of nodes to regard in the subproblem */
86 #define DEFAULT_MINFIXINGRATE 0.66 /**< minimum percentage of integer variables that have to be fixed */
87 #define DEFAULT_NODESQUOT 0.15 /**< subproblem nodes in relation to nodes of the original problem */
88 #define DEFAULT_NWAITINGNODES 100 /**< number of nodes without incumbent change that heuristic should wait */
89 #define DEFAULT_USELPROWS FALSE /**< should subproblem be created out of the rows in the LP rows,
90  * otherwise, the copy constructors of the constraints handlers are used */
91 #define DEFAULT_COPYCUTS TRUE /**< if DEFAULT_USELPROWS is FALSE, then should all active cuts from the
92  * cutpool of the original scip be copied to constraints of the subscip */
93 #define DEFAULT_BESTSOLLIMIT 3 /**< limit on number of improving incumbent solutions in sub-CIP */
94 #define DEFAULT_FIXCONTVARS FALSE /**< should continuous variables outside the neighborhoods get fixed? */
95 #define DEFAULT_POTENTIAL 'r' /**< the reference point to compute the neighborhood potential: (r)oot, (l)ocal lp, or (p)seudo solution */
96 #define DEFAULT_MAXDISTANCE 3 /**< maximum distance to selected variable to enter the subproblem, or -1 to
97  * select the distance that best approximates the minimum fixing rate from below */
98 #define DEFAULT_RANDSEED 71
99 #define DEFAULT_RELAXDENSECONSS FALSE /**< should dense constraints (at least as dense as 1 - minfixingrate) be
100  * ignored by connectivity graph? */
101 #define DEFAULT_USEROLLINGHORIZON TRUE /**< should the heuristic solve a sequence of sub-MIP's around the first selected variable */
102 #define DEFAULT_ROLLHORIZONLIMFAC 0.4 /**< limiting percentage for variables already used in sub-SCIPs to terminate rolling
103  * horizon approach */
104 #define DEFAULT_USEDECOMP TRUE /**< should user decompositions be considered, if available? */
105 #define DEFAULT_USEDECOMPROLLHORIZON FALSE /**< should user decompositions be considered for initial selection in rolling horizon, if available? */
106 #define DEFAULT_USESELFALLBACK TRUE /**< should random initial variable selection be used if decomposition was not successful? */
107 #define DEFAULT_OVERLAP 0.0 /**< overlap of blocks between runs - 0.0: no overlap, 1.0: shift by only 1 block */
108 #define DEFAULT_CONSECUTIVEBLOCKS TRUE /**< should blocks be treated consecutively (sorted by ascending label?) */
109 #ifdef SCIP_STATISTIC
110 #define NHISTOGRAMBINS 10 /**< number of bins for histograms */
111 #endif
114 /*
115  * Data structures
116  */
117
118 /** rolling horizon data structure to control multiple LNS heuristic runs away from an original source variable */
119 struct RollingHorizon
120 {
121  SCIP_VGRAPH* variablegraph; /**< variable graph data structure for breadth-first-search neighborhoods */
122  int* distances; /**< distances of the heuristic rolling horizon from the original source
123  * variable indexed by probindex */
124  SCIP_Bool* used; /**< array that represents for every variable whether it has been used
125  * in a neighborhood indexed by probindex */
126  int lastmaxdistance; /**< the last distance k for a neighborhood, will be decreased
127  * during the rolling horizon if the selected neighborhood is too large */
128  int lastdistance; /**< last distance from originally selected variable in iteration zero */
129  int distancessize; /**< size of the distances and used arrays */
130  int niterations; /**< counter for the number of rolling horizon iterations */
131  int nused; /**< counts the number variables that have been part of any neighborhood
132  * during the rolling horizon approach */
133  int nnonreachable; /**< counter for the number of nonreachable variables (distance -1) from
134  * the initially selected variable */
135 };
137
138 /** data structure to enable GINS to solve multiple decompositions in a sequential process */
139 struct DecompHorizon
140 {
141  SCIP_DECOMP* decomp; /**< decomposition data structure used for this horizon */
142  SCIP_VAR** vars; /**< variables sorted by block indices */
143  SCIP_SOL** lastsolblock; /**< last solution for which block was part of the sub-SCIP */
144  SCIP_Real* potential; /**< potential of each block */
145  int* blocklabels; /**< sorted block labels of all variable blocks that satisfy the requirements */
146  int* varblockend; /**< block end indices in sorted variables array (position of first variable of next block) */
147  int* ndiscretevars; /**< number of binary and integer variables in each block */
148  int* blockindices; /**< block indices (from 0 to nblocks) with respect to sorting of blocks */
149  int* nvars; /**< number of variables (including continuous and implicit integers) in each block */
150  SCIP_Bool* suitable; /**< TRUE if a block is suitable */
151  int nsuitableblocks; /**< the total number of suitable blocks */
152  int lastblockpos; /**< last remembered block position (in block indices, i.e., regarding sorting) */
153  int nblocks; /**< the number of available variable blocks, only available after initialization */
154  int memsize; /**< storage size of the used arrays */
155  int varsmemsize; /**< storage size of the vars array */
156  int overlapinterval[2]; /**< block positions of last interval forbidden by overlap */
157  SCIP_Bool init; /**< has the decomposition horizon been initialized? */
158 };
161 /** data structure to hold elements that are taboo */
162 struct TabooList
163 {
164  int* taboolabels; /**< labels or indices that are currently taboo */
165  int* sortedlabels; /**< array of labels in sorted order for quicker finding */
166  int memsize; /**< storage capacity of taboolabels */
167  int ntaboolabels; /**< number of elements contained in taboo list */
168  SCIP_Bool needssorting; /**< has an element been added since the last sort? */
169 };
170 typedef struct TabooList TABOOLIST;
172 /** primal heuristic data */
173 struct SCIP_HeurData
174 {
175  int nodesofs; /**< number of nodes added to the contingent of the total nodes */
176  int maxnodes; /**< maximum number of nodes to regard in the subproblem */
177  int minnodes; /**< minimum number of nodes to regard in the subproblem */
178  SCIP_Real minfixingrate; /**< minimum percentage of integer variables that have to be fixed */
179  SCIP_Real overlap; /**< overlap of blocks between runs - 0.0: no overlap, 1.0: shift by only 1 block */
180  int nwaitingnodes; /**< number of nodes without incumbent change that heuristic should wait */
181  SCIP_Real minimprove; /**< factor by which Gins should at least improve the incumbent */
182  SCIP_Longint usednodes; /**< nodes already used by Gins in earlier calls */
183  SCIP_Real nodesquot; /**< subproblem nodes in relation to nodes of the original problem */
184  SCIP_Real rollhorizonlimfac; /**< limiting percentage for variables already used in sub-SCIPs to terminate
185  * rolling horizon approach */
186  DECOMPHORIZON* decomphorizon; /**< decomposition horizon data structure */
187  SCIP_RANDNUMGEN* randnumgen; /**< random number generator */
188  SCIP_SOL* lastinitsol; /**< last solution used for selection of initial variable */
189  TABOOLIST* taboolist; /**< taboo list of block labels that should not be used */
190  SCIP_Bool uselprows; /**< should subproblem be created out of the rows in the LP rows? */
191  SCIP_Bool copycuts; /**< if uselprows == FALSE, should all active cuts from cutpool be copied
192  * to constraints in subproblem? */
193  SCIP_Bool allblocksunsuitable; /**< remember if all blocks are unsuitable w.r.t. the current incumbent solution */
194  SCIP_Bool fixcontvars; /**< should continuous variables outside the neighborhoods get fixed? */
195  int bestsollimit; /**< limit on number of improving incumbent solutions in sub-CIP */
196  int maxdistance; /**< maximum distance to selected variable to enter the subproblem, or -1 to
197  * select the distance that best approximates the minimum fixing rate from below */
198  int sumneighborhoodvars;/**< neighborhood variables sum over all seen neighborhoods */
199  int sumdiscneighborhoodvars; /**< neighborhood discrete variables sum over all seen neighboorhoods */
200  int nneighborhoods; /**< number of calculated neighborhoods */
201  int nsubmips; /**< counter for the number of sub-MIP's that can be higher than the number of
202  * calls of this heuristic */
203  SCIP_Bool consecutiveblocks; /**< should blocks be treated consecutively (sorted by ascending label?) */
204  SCIP_Bool relaxdenseconss; /**< should dense constraints (at least as dense as 1 - minfixingrate) be
205  * ignored by connectivity graph? */
206  SCIP_Bool userollinghorizon; /**< should the heuristic solve a sequence of sub-MIP's around the first
207  * selected variable */
208  SCIP_Bool usedecomp; /**< should user decompositions be considered, if available? */
209  SCIP_Bool usedecomprollhorizon;/**< should user decompositions be considered for initial selection in rolling horizon, if available? */
210  SCIP_Bool useselfallback; /**< should random initial variable selection be used if decomposition was not successful? */
211  char potential; /**< the reference point to compute the neighborhood potential: (r)oot or
212  * (p)seudo solution */
213  int maxseendistance; /**< maximum of all distances between two variables */
214 #ifdef SCIP_STATISTIC
215  int consvarshist[NHISTOGRAMBINS]; /**< histogram that summarizes the densities of the constraints */
216  int consdiscvarshist[NHISTOGRAMBINS]; /**< histogram that summarizes the discrete variable densities of the constraints */
217  int conscontvarshist[NHISTOGRAMBINS]; /**< histogram that summarizes the continuous variable densities of the constraints */
218 #endif
219  int nrelaxedconstraints; /**< number of constraints that were relaxed */
220  int nfailures; /**< counter for the number of unsuccessful runs of this heuristic */
221  SCIP_Longint nextnodenumber; /**< the next node number at which the heuristic should be called again */
222  SCIP_Longint targetnodes; /**< number of target nodes, slightly increasing if (stall) node limit is hit */
223 };
224
225 /** represents limits for the sub-SCIP solving process */
226 struct SolveLimits
227 {
228  SCIP_Longint nodelimit; /**< maximum number of solving nodes for the sub-SCIP */
229  SCIP_Longint stallnodelimit; /**< limit on the number of stall nodes (nodes after last incumbent) */
230 };
231 typedef struct SolveLimits SOLVELIMITS;
232
233 /*
234  * Local methods
235  */
237 #ifdef SCIP_STATISTIC
238 /** resets a histogram */
239 static
240 void resetHistogram(
241  int* histogram /**< the histogram */
242  )
243 {
244  BMSclearMemoryArray(histogram, NHISTOGRAMBINS);
245 }
246
247 /** adds a ratio to the histogram at the right position */
248 static
250  int* histogram, /**< the histogram */
251  int value, /**< the value */
252  int basevalue /**< base value */
253  )
254 {
255  SCIP_Real ratio;
256  int index;
257  assert(value <= basevalue);
258  ratio = value/ MAX(1.0, (SCIP_Real)basevalue);
259
260  index = (int)(ratio * NHISTOGRAMBINS);
261  ++histogram[index];
262 }
263
264 #endif
265
266
267 /** check if enough fixings have been found */
268 static
270  SCIP* scip, /**< SCIP data structure */
271  SCIP_HEURDATA* heurdata, /**< heuristic data */
272  int nfixings /**< actual number of fixings */
273  )
274 {
275  int fixthreshold;
276  int nvars = SCIPgetNVars(scip);
277  int nbinvars = SCIPgetNBinVars(scip);
278  int nintvars = SCIPgetNIntVars(scip);
279  fixthreshold = (int)(heurdata->minfixingrate * (heurdata->fixcontvars ? nvars : (nbinvars + nintvars)));
280
281  /* compare actual number of fixings to limit; if we fixed not enough variables we terminate here;
282  * we also terminate if no discrete variables are left
283  */
284  if( nfixings < fixthreshold )
285  {
286  SCIPdebugMsg(scip, "Fixed %d < %d variables in gins heuristic, stopping\n", nfixings, fixthreshold);
287
288  return FALSE;
289  }
290  else
291  {
292  SCIPdebugMsg(scip, "Fixed enough (%d >= %d) variables in gins heuristic\n", nfixings, fixthreshold);
293
294  return TRUE;
295  }
296 }
297
298 /** get the potential of a subset of variables (distance to a reference point such as the pseudo-solution or root
299  * LP solution)
300  */
301 static
303  SCIP* scip, /**< SCIP data structure */
304  SCIP_HEURDATA* heurdata, /**< heuristic data */
305  SCIP_SOL* sol, /**< solution */
306  SCIP_VAR** vars, /**< variable array */
307  int nvars /**< length of variable array */
308  )
309 {
310  SCIP_Real potential;
311  int i;
312
313  assert(scip != NULL);
314  assert(vars != NULL);
315  assert(sol != NULL);
316
317  if( nvars == 0 )
318  return 0.0;
319
320  potential = 0.0;
321
322  for( i = 0; i < nvars; ++i )
323  {
324  SCIP_Real objdelta;
325  SCIP_VAR* var;
326  SCIP_Real referencepoint;
327  SCIP_Real varobj;
328
329  var = vars[i];
330  assert(var != NULL);
331  varobj = SCIPvarGetObj(var);
332
333  if( SCIPisZero(scip, varobj) )
334  continue;
335
336  /* determine the reference point for potential computation */
337  switch( heurdata->potential )
338  {
339  /* use difference to pseudo solution using the bound in the objective direction */
340  case 'p':
341  referencepoint = varobj > 0.0 ? SCIPvarGetLbGlobal(var) : SCIPvarGetUbGlobal(var);
342  break;
343
344  /* use root LP solution difference */
345  case 'r':
346  referencepoint = SCIPvarGetRootSol(var);
347  break;
348
349  /* use local LP solution */
350  case 'l':
351  referencepoint = SCIPgetSolVal(scip, NULL, var);
352  break;
353  default:
354  SCIPerrorMessage("Unknown potential computation %c specified\n", heurdata->potential);
355  referencepoint = 0.0;
356  break;
357  }
358
359  if( SCIPisInfinity(scip, REALABS(referencepoint)) )
360  continue;
361
362  /* calculate the delta to the variables best bound */
363  objdelta = (SCIPgetSolVal(scip, sol, var) - referencepoint) * varobj;
364  potential += objdelta;
365  }
366
367  return potential;
368 }
369
370 /** (re)set overlap interval of decomposition horizon */
371 static
373  DECOMPHORIZON* decomphorizon, /**< decomposition horizon data structure */
374  int leftborder, /**< left interval border */
375  int rightborder /**< right interval border */
376  )
377 {
378  assert(decomphorizon != NULL);
379  assert(leftborder <= rightborder);
380
381  decomphorizon->overlapinterval[0] = leftborder;
382  decomphorizon->overlapinterval[1] = rightborder;
383 }
384
385 /** create a decomp horizon data structure */
386 static
388  SCIP* scip, /**< SCIP data structure */
389  DECOMPHORIZON** decomphorizon, /**< pointer to store decomposition horizon */
390  SCIP_DECOMP* decomp /**< decomposition in transformed space */
391  )
392 {
393  DECOMPHORIZON* decomphorizonptr;
394  int nblocks;
395  int memsize;
396
397  assert(scip != NULL);
398  assert(decomphorizon != NULL);
399  assert(decomp != NULL);
400
401  nblocks = SCIPdecompGetNBlocks(decomp);
402
403  assert(nblocks >= 1);
404
405  /* account an additional slot for the border */
406  SCIP_CALL( SCIPallocBlockMemory(scip, decomphorizon) );
407  decomphorizonptr = *decomphorizon;
408  decomphorizonptr->decomp = decomp;
409  decomphorizonptr->memsize = memsize = nblocks + 1;
410
411  /* allocate storage for block related information */
412  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &decomphorizonptr->blocklabels, memsize) );
413  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &decomphorizonptr->varblockend, memsize) );
414  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &decomphorizonptr->suitable, memsize) );
415  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &decomphorizonptr->ndiscretevars, memsize) );
416  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &decomphorizonptr->nvars, memsize) );
417  SCIP_CALL( SCIPallocClearBlockMemoryArray(scip, &decomphorizonptr->lastsolblock, memsize) );
418  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &decomphorizonptr->potential, memsize) );
419  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &decomphorizonptr->blockindices, memsize) );
420
421  decomphorizonptr->lastblockpos = INT_MIN; /* cannot use -1 because this is defined for linking variables */
422
423  /* initialize data later */
424  decomphorizonptr->init = FALSE;
425  decomphorizonptr->vars = NULL;
426  decomphorizonptr->varsmemsize = 0;
427
428  return SCIP_OKAY;
429 }
430
431 /** free a decomp horizon data structure */
432 static
433 void decompHorizonFree(
434  SCIP* scip, /**< SCIP data structure */
435  DECOMPHORIZON** decomphorizon /**< pointer to decomposition horizon that should be freed */
436  )
437 {
438  DECOMPHORIZON* decomphorizonptr;
439
440  assert(scip != NULL);
441  assert(decomphorizon != NULL);
442
443  /* empty horizon */
444  if( *decomphorizon == NULL )
445  return;
446
447  decomphorizonptr = *decomphorizon;
448  SCIPfreeBlockMemoryArrayNull(scip, &decomphorizonptr->vars, decomphorizonptr->varsmemsize);
449
450  SCIPfreeBlockMemoryArray(scip, &decomphorizonptr->blocklabels, decomphorizonptr->memsize);
451  SCIPfreeBlockMemoryArray(scip, &decomphorizonptr->varblockend, decomphorizonptr->memsize);
452  SCIPfreeBlockMemoryArray(scip, &decomphorizonptr->suitable, decomphorizonptr->memsize);
453  SCIPfreeBlockMemoryArray(scip, &decomphorizonptr->ndiscretevars, decomphorizonptr->memsize);
454  SCIPfreeBlockMemoryArray(scip, &decomphorizonptr->nvars, decomphorizonptr->memsize);
455  SCIPfreeBlockMemoryArray(scip, &decomphorizonptr->lastsolblock, decomphorizonptr->memsize);
456  SCIPfreeBlockMemoryArray(scip, &decomphorizonptr->potential, decomphorizonptr->memsize);
457  SCIPfreeBlockMemoryArray(scip, &decomphorizonptr->blockindices, decomphorizonptr->memsize);
458
459  SCIPfreeBlockMemory(scip, decomphorizon);
460
461  *decomphorizon = NULL;
462 }
463
464 /** check if another run should be performed within the current decomposition horizon */
465 static
467  SCIP* scip, /**< SCIP data structure */
468  DECOMPHORIZON* decomphorizon /**< decomposition horizon data structure */
469  )
470 {
471  assert(scip != NULL);
472  assert(decomphorizon != NULL);
473
474  assert(decomphorizon->lastblockpos >= 0);
475  assert(decomphorizon->lastblockpos < decomphorizon->nblocks);
476
477  return TRUE;
478 }
479
480 /** return TRUE if the decomposition horizon has already been initialized, FALSE otherwise */
481 static
483  DECOMPHORIZON* decomphorizon /**< decomposition horizon data structure */
484  )
485 {
486  assert(decomphorizon != NULL);
488  return decomphorizon->init;
489 }
490
491 /** compares two block indices
492  * result:
493  * < 0: ind1 comes before (is better than) ind2
494  * = 0: both indices have the same value
495  * > 0: ind2 comes after (is worse than) ind2
496  */
497 static
498 SCIP_DECL_SORTINDCOMP(sortIndCompDecompHorizon)
499 {
500  DECOMPHORIZON* decomphorizon = (DECOMPHORIZON*)dataptr;
501  SCIP_Real potentialbysize1;
502  SCIP_Real potentialbysize2;
504  assert(decomphorizon != NULL);
505  assert(ind1 >= 0);
506  assert(ind2 >= 0);
507  assert(ind1 < decomphorizon->nblocks);
508  assert(ind2 < decomphorizon->nblocks);
509
510  if( ind1 == ind2 )
511  return 0;
512
513  /* linking variables are always sorted up front */
514  if( decomphorizon->blocklabels[ind1] == SCIP_DECOMP_LINKVAR )
515  return -1;
516  else if( decomphorizon->blocklabels[ind2] == SCIP_DECOMP_LINKVAR )
517  return 1;
518
519  /* if one of the blocks is not suitable, return the other block */
520  if( ! (decomphorizon->suitable[ind1] && decomphorizon->suitable[ind2]) )
521  {
522  /* prefer the suitable block; break ties based on block position */
523  if( decomphorizon->suitable[ind1] )
524  return -1;
525  else if( decomphorizon->suitable[ind2] )
526  return 1;
527  else
528  return ind1 - ind2;
529  }
530
531  assert(decomphorizon->suitable[ind1] && decomphorizon->suitable[ind2]);
532
533  potentialbysize1 = decomphorizon->potential[ind1] / (SCIP_Real)(MAX(decomphorizon->ndiscretevars[ind1], 1.0));
534  potentialbysize2 = decomphorizon->potential[ind2] / (SCIP_Real)(MAX(decomphorizon->ndiscretevars[ind2], 1.0));
535
536  /* prefer the block with higher potential */
537  if( potentialbysize1 > potentialbysize2 )
538  return -1;
539  else if( potentialbysize2 > potentialbysize1 )
540  return 1;
541
542  /* finally, prefer the block with fewer discrete variables */
543  return decomphorizon->ndiscretevars[ind1] - decomphorizon->ndiscretevars[ind2];
544 }
545
546 /** initialize decomposition horizon data structure by setting up data structures and analyzing blocks */
547 static
549  SCIP* scip, /**< SCIP data structure */
550  DECOMPHORIZON* decomphorizon, /**< decomposition horizon data structure */
551  SCIP_HEURDATA* heurdata /**< heuristic data structure */
552  )
553 {
554  SCIP_VAR** vars;
555  SCIP_VAR** varscopy;
556  int* varlabels;
557  int nvars;
558  int currblockstart;
559  int blockpos;
560  int nstblblocks;
562  int b;
563
564  SCIP_DECOMP* decomp = decomphorizon->decomp;
565
566  assert(scip != NULL);
567  assert(decomp != NULL);
568  assert(! SCIPdecompIsOriginal(decomp));
569
570  vars = SCIPgetVars(scip);
571  nvars = SCIPgetNVars(scip);
572  ncontvarsscip = SCIPgetNContVars(scip) + SCIPgetNImplVars(scip);
573
574  assert(vars != NULL);
575
576  /* get variable labels from decomposition */
577  SCIP_CALL( SCIPallocBufferArray(scip, &varlabels, nvars) );
578  SCIP_CALL( SCIPduplicateBlockMemoryArray(scip, &varscopy, vars, nvars) );
579
580  SCIPdecompGetVarsLabels(decomp, varscopy, varlabels, nvars);
581
582  /* sort labels and variables */
583  SCIPsortIntPtr(varlabels, (void **)varscopy, nvars);
584  decomphorizon->vars = varscopy;
585  decomphorizon->varsmemsize = nvars;
586
587  blockpos = 0;
588  currblockstart = 0;
589  nstblblocks = 0;
590  /* loop over blocks, and check if they are suitable or not for the improvement heuristic */
591  while( currblockstart < nvars )
592  {
593  int blocklabel;
594  int currblockend;
595  int ndiscretevars;
596  int nfixedvars;
597  SCIP_Bool suitable;
598  assert(blockpos < decomphorizon->memsize);
599
600  blocklabel = varlabels[currblockstart];
601  currblockend = currblockstart;
602  ndiscretevars = 0;
603
604  /* determine the block size and the variable types */
605  do
606  {
607  if( SCIPvarGetType(varscopy[currblockend]) < SCIP_VARTYPE_IMPLINT )
608  ++ndiscretevars;
609
610  currblockend++;
611  }
612  while( currblockend < nvars && varlabels[currblockend] == blocklabel );
613
614  if( heurdata->fixcontvars )
615  nfixedvars = nvars - (currblockend - currblockstart);
616  else
617  nfixedvars = nvars - ncontvarsscip - ndiscretevars;
618
619  suitable = nfixedvars > heurdata->minfixingrate * (heurdata->fixcontvars ? nvars : nvars - ncontvarsscip);
620
621  decomphorizon->suitable[blockpos] = suitable;
622  decomphorizon->blocklabels[blockpos] = blocklabel;
623  decomphorizon->varblockend[blockpos] = currblockend;
624  decomphorizon->nvars[blockpos] = currblockend - currblockstart;
625  decomphorizon->ndiscretevars[blockpos] = ndiscretevars;
626
627  currblockstart = currblockend;
628  nstblblocks += (suitable ? 1 : 0);
629
630  blockpos++;
631  }
632
633  /* not necessarily all blocks have variables; store number of available blocks */
634  decomphorizon->nblocks = blockpos;
635  decomphorizon->nsuitableblocks = nstblblocks;
636
637  /* initialize block indices (identical to blockposition initially) */
638  for( b = 0; b < decomphorizon->nblocks; ++b )
639  decomphorizon->blockindices[b] = b;
640
641  decompHorizonSetOverlapInterval(decomphorizon, -1, -1);
642
643  SCIPdebugMsg(scip, "Initialized decomposition horizon for %d blocks (%d suitable)\n",
644  decomphorizon->nblocks,
645  decomphorizon->nsuitableblocks);
646
647  SCIPfreeBufferArray(scip, &varlabels);
648
649  decomphorizon->init = TRUE;
650
651  return SCIP_OKAY;
652 }
653
654 /** get the first block position of the consecutive interval with the highest potential */
655 static
657  SCIP* scip, /**< SCIP data structure */
658  DECOMPHORIZON* decomphorizon, /**< decomposition horizon data structure */
659  SCIP_HEURDATA* heurdata, /**< heuristic data */
660  int maxblocksize /**< maximum block size in number of variables */
661  )
662 {
663  SCIP_SOL* bestsol;
664  SCIP_Real intervalpotential;
665  int b;
666  int nintervalvars;
667  int b1;
668  int b2;
669  int bestpos;
670  SCIP_Real maxpotential;
673
674  assert(scip != NULL);
675  assert(decomphorizon != NULL);
676  bestsol = SCIPgetBestSol(scip);
677  assert(bestsol != NULL);
678
680  bestpos = 0;
681
682  /* recompute potential of blocks */
683  for( b = 0; b < decomphorizon->nblocks; ++b )
684  {
685  /* unsuitable blocks are left out and should not be contained in an interval */
686  if( ! decomphorizon->suitable[b] )
687  {
688  decomphorizon->potential[b] = SCIP_REAL_MIN;
689  continue;
690  }
691
692  /* store the potential of this block */
693  decomphorizon->potential[b] = getPotential(scip, heurdata, bestsol,
694  &decomphorizon->vars[b == 0 ? 0 : decomphorizon->varblockend[b - 1]], decomphorizon->nvars[b]);
695  }
696
697  /* sort the blocks such that the suitable blocks with the highest potential come first */
698  if( ! heurdata->consecutiveblocks )
699  {
700  SCIPsortInd(decomphorizon->blockindices, sortIndCompDecompHorizon, (void*)decomphorizon, decomphorizon->nblocks);
701
702  /* best potential block is now at the front (actual block position is retrieved from blockindices */
703  SCIPdebugMsg(scip, "New potential based sorting with trailing block: 0 (label %d, potential %.4g)\n",
704  decomphorizon->blocklabels[decomphorizon->blockindices[0]], decomphorizon->potential[decomphorizon->blockindices[0]]);
705
706  return 0;
707  }
708
709  /* compute the consecutive blocks interval with largest potential */
710  b1 = linkvarsexist ? 0 : -1;
711  b2 = -1;
712  nintervalvars = 0;
713  intervalpotential = 0.0;
714  maxpotential = 0.0;
716
717  while( b1 < decomphorizon->nblocks - 1 )
718  {
719  int blockindb1;
720  int blockindb2;
721  ++b1;
722  blockindb1 = decomphorizon->blockindices[b1];
723
724  if( ! decomphorizon->suitable[decomphorizon->blockindices[b1]] )
725  {
726  nintervalvars = 0;
727  intervalpotential = 0.0;
729  b2 = b1;
730  continue;
731  }
732
733  /* interval starts at b1 */
734  if( b2 < b1 )
735  {
736  nintervalvars = decomphorizon->ndiscretevars[blockindb1];
737  assert(nintervalvars < maxblocksize); /* otherwise, it wasn't suitable */
738  intervalpotential = decomphorizon->potential[blockindb1];
740  b2 = b1;
741  }
742  /* subtract the variables from the previous block */
743  else
744  {
745  int prevblockind;
746  assert(b1 > (linkvarsexist ? 1 : 0));
747  prevblockind = decomphorizon->blockindices[b1 - 1];
748  assert(decomphorizon->suitable[prevblockind]);
749  nintervalvars -= decomphorizon->ndiscretevars[prevblockind];
750  intervalpotential -= decomphorizon->potential[prevblockind];
751  }
752
753  /* check if block allows to include linking variables */
754  if( ! withlinkvars && linkvarsexist && decomphorizon->ndiscretevars[0] + decomphorizon->ndiscretevars[blockindb1] < maxblocksize )
755  {
757  nintervalvars = decomphorizon->ndiscretevars[0] + decomphorizon->ndiscretevars[blockindb1];
758  b2 = b1;
759  }
760  else if( withlinkvars && decomphorizon->ndiscretevars[0] + decomphorizon->ndiscretevars[blockindb1] >= maxblocksize )
761  {
763  nintervalvars = decomphorizon->ndiscretevars[blockindb1];
764  b2 = b1;
765  }
766
767  /* extend the interval by further blocks, if possible */
768  while( ++b2 < decomphorizon->nblocks )
769  {
770  blockindb2 = decomphorizon->blockindices[b2];
771
772  if( ! decomphorizon->suitable[blockindb2] || nintervalvars + decomphorizon->ndiscretevars[blockindb2] >= maxblocksize )
773  break;
774
775  nintervalvars += decomphorizon->ndiscretevars[blockindb2];
776  intervalpotential += decomphorizon->potential[blockindb2];
777  }
778
779  /* store the start of the interval with maximum potential */
780  if( intervalpotential > maxpotential )
781  {
782  bestpos = b1; /* because pos is incremented by 1 again */
783  maxpotential = intervalpotential;
784  }
785  }
786
787  SCIPdebugMsg(scip, "Potential based selection chooses interval starting from block %d with potential %.1g\n",
788  bestpos, maxpotential);
789
790  return bestpos;
791 }
792
793 /** has this block been used too recently? */
794 static
796  SCIP* scip, /**< SCIP data structure */
797  DECOMPHORIZON* decomphorizon, /**< decomposition horizon data structure */
798  int blockpos /**< position of block */
799  )
800 {
801  assert(scip != NULL);
802  assert(decomphorizon != NULL);
803  assert(0 <= blockpos);
804  assert(blockpos < decomphorizon->nblocks);
805
806  return (decomphorizon->lastsolblock[decomphorizon->blockindices[blockpos]] == SCIPgetBestSol(scip) ||
807  (decomphorizon->overlapinterval[0] <= blockpos && blockpos <= decomphorizon->overlapinterval[1]));
808 }
809
810 /** query the start and end of the next suitable block after the last @p lastblockused
811  *
812  * @return TRUE if next suitable block could be found, otherwise FALSE
813  */
814 static
816  SCIP* scip, /**< SCIP data structure */
817  DECOMPHORIZON* decomphorizon, /**< decomposition horizon data structure */
818  SCIP_HEURDATA* heurdata, /**< heuristic data */
819  int maxblocksize, /**< maximum block size in number of variables */
820  int* blockintervalstart, /**< pointer to store position of first block of interval */
821  int* blockintervalend, /**< pointer to store position of last block of interval */
822  int* nextblocklabel, /**< pointer to store label of the next suitable block */
823  SCIP_Bool* fixlinkvars /**< should the linking variables be fixed, as well? */
824  )
825 {
826  SCIP_Bool found;
827  int pos;
828  int firstpos;
829  SCIP_SOL* bestsol;
830  assert(decomphorizon != NULL);
831  assert(blockintervalstart != NULL);
832  assert(blockintervalend != NULL);
833  assert(nextblocklabel != NULL);
835
836  assert(decomphorizon->init);
837
838  if( decomphorizon->nsuitableblocks == 0 )
839  {
840  return FALSE;
841  }
842
843  /* get the last block position that was used by the heuristic. Search for it, and continue with the next block. */
844  found = decomphorizon->lastblockpos >= 0;
845  firstpos = decomphorizon->lastblockpos;
846  assert(! found || (firstpos >= 0 && firstpos < decomphorizon->nblocks));
847
848  bestsol = SCIPgetBestSol(scip);
849
850  /* choose first position based on potential; subtract -1 because we immediately increase it */
851  if( ! found || bestsol != decomphorizon->lastsolblock[decomphorizon->blockindices[firstpos]] )
852  firstpos = decompHorizonGetFirstPosBestPotential(scip, decomphorizon, heurdata, maxblocksize) - 1;
853
854  /* that's why we subtract 1 from potential based position computation */
855  pos = (firstpos + 1) % decomphorizon->nblocks;
856
857  while( pos < decomphorizon->nblocks &&
858  (! decomphorizon->suitable[decomphorizon->blockindices[pos]] || decomphorizon->blocklabels[decomphorizon->blockindices[pos]] == SCIP_DECOMP_LINKVAR ||
859  decompHorizonBlockUsedRecently(scip, decomphorizon, pos)) )
860  pos++;
861
862  if( pos == decomphorizon->nblocks )
863  {
864  pos = 0;
865  while( pos < firstpos &&
866  (! decomphorizon->suitable[decomphorizon->blockindices[pos]] || decomphorizon->blocklabels[decomphorizon->blockindices[pos]] == SCIP_DECOMP_LINKVAR ||
867  decompHorizonBlockUsedRecently(scip, decomphorizon, pos)) )
868  pos++;
869  }
870
871  assert(pos == firstpos || (0 <= pos && decomphorizon->nblocks > pos && (decomphorizon->suitable[decomphorizon->blockindices[pos]] || pos == 0)));
872
874  /* the next suitable block position has been discovered */
875  if( pos != firstpos && decomphorizon->suitable[decomphorizon->blockindices[pos]] && !decompHorizonBlockUsedRecently(scip, decomphorizon, pos) )
876  {
877  int ndiscretevars;
878  *nextblocklabel = decomphorizon->blocklabels[decomphorizon->blockindices[pos]];
879  *blockintervalstart = pos;
880  *blockintervalend = pos;
881
882  ndiscretevars = decomphorizon->ndiscretevars[decomphorizon->blockindices[pos]];
883  /* check if linking variable block exceeds maximum block size */
884  if( decomphorizon->blocklabels[0] == SCIP_DECOMP_LINKVAR )
885  {
886  *fixlinkvars = decomphorizon->ndiscretevars[0] + ndiscretevars > maxblocksize;
887  }
888
891  ndiscretevars += decomphorizon->ndiscretevars[0];
892
893  /* extend the subproblem until maximum target fixing rate is reached */
894  while( ++pos < decomphorizon->nblocks && decomphorizon->suitable[decomphorizon->blockindices[pos]] && ndiscretevars + decomphorizon->ndiscretevars[decomphorizon->blockindices[pos]] < maxblocksize )
895  {
896  *blockintervalend = pos;
897  *nextblocklabel = decomphorizon->blocklabels[decomphorizon->blockindices[pos]];
898  ndiscretevars += decomphorizon->ndiscretevars[decomphorizon->blockindices[pos]];
899  }
900
901  return TRUE;
902  }
903  else
904  {
905  /* no next, suitable block exists */
906  *blockintervalstart = *blockintervalend = -1;
907  *nextblocklabel = -100;
908
909  return FALSE;
910  }
911 }
912
913 /** get the variables of this decomposition horizon */
914 static
916  DECOMPHORIZON* decomphorizon /**< decomposition horizon data structure */
917  )
918 {
919  assert(decomphorizon != NULL);
920  assert(decomphorizon->init);
921
922  return decomphorizon->vars;
923 }
924
925 /** create a rolling horizon data structure */
926 static
928  SCIP* scip, /**< SCIP data structure */
929  ROLLINGHORIZON** rollinghorizon /**< pointer to rolling horizon data structure */
930  )
931 {
932  int size;
933  assert(scip != NULL);
934  assert(rollinghorizon != NULL);
935
936  size = SCIPgetNBinVars(scip) + SCIPgetNIntVars(scip);
937  SCIP_CALL( SCIPallocBlockMemory(scip, rollinghorizon) );
938  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(*rollinghorizon)->distances, size) );
939  SCIP_CALL( SCIPallocClearBlockMemoryArray(scip, &(*rollinghorizon)->used, size) );
940  (*rollinghorizon)->distancessize = size;
941  (*rollinghorizon)->variablegraph = NULL;
942  (*rollinghorizon)->lastdistance = -1;
943  (*rollinghorizon)->niterations = 0;
944  (*rollinghorizon)->nused = 0;
945
946  return SCIP_OKAY;
947 }
948
949
950 /** reset a taboo list */
951 static
952 void tabooListReset(
953  TABOOLIST* taboolist /**< taboo list data structure */
954  )
955 {
956  taboolist->ntaboolabels = 0;
957  taboolist->needssorting = FALSE;
958 }
959
960 /** create a taboo list data structure */
961 static
963  SCIP* scip, /**< SCIP data structure */
964  TABOOLIST** taboolist, /**< pointer to store taboo list data structure */
965  int initialsize /**< initial storage capacity of taboo list */
966  )
967 {
968  assert(scip != NULL);
969  assert(taboolist != NULL);
970
971  SCIP_CALL( SCIPallocBlockMemory(scip, taboolist) );
972
973  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(*taboolist)->taboolabels, initialsize) );
974  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(*taboolist)->sortedlabels, initialsize) );
975  (*taboolist)->memsize = initialsize;
976  tabooListReset(*taboolist);
977
978  return SCIP_OKAY;
979 }
980
981 /** free a taboo list data structure */
982 static
983 void freeTabooList(
984  SCIP* scip, /**< SCIP data structure */
985  TABOOLIST** taboolist /**< pointer to taboo list data structure that should be freed */
986  )
987 {
988  assert(scip != NULL);
989  assert(taboolist != NULL);
990
991  if( *taboolist == NULL )
992  return;
993
994  SCIPfreeBlockMemoryArray(scip, &(*taboolist)->sortedlabels, (*taboolist)->memsize);
995  SCIPfreeBlockMemoryArray(scip, &(*taboolist)->taboolabels, (*taboolist)->memsize);
996  SCIPfreeBlockMemory(scip, taboolist);
997 }
998
999 /** add an element to the taboo list */
1000 static
1002  SCIP* scip, /**< SCIP data structure */
1003  TABOOLIST* taboolist, /**< taboo list data structure */
1004  int elem /**< element that should be added to the taboo list */
1005  )
1007  assert(scip != NULL);
1008  assert(taboolist != NULL);
1009
1010  if( taboolist->memsize == taboolist->ntaboolabels )
1011  {
1012  int newsize = SCIPcalcMemGrowSize(scip, taboolist->ntaboolabels + 1);
1013  assert(newsize >= taboolist->ntaboolabels + 1);
1014
1015  SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &taboolist->taboolabels, taboolist->memsize, newsize) );
1016  SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &taboolist->sortedlabels, taboolist->memsize, newsize) );
1017
1018  taboolist->memsize = newsize;
1019  }
1020
1021  assert(taboolist->ntaboolabels < taboolist->memsize);
1022  taboolist->taboolabels[taboolist->ntaboolabels++] = elem;
1023
1024  taboolist->needssorting = TRUE;
1025
1026  return SCIP_OKAY;
1027 }
1028
1029 /** find an element in the taboo list */
1030 static
1032  TABOOLIST* taboolist, /**< taboo list data structure */
1033  int elem /**< element that should be added to the taboo list */
1034  )
1035 {
1036  SCIP_Bool found;
1037  int pos;
1038  assert(taboolist != NULL);
1039
1040  if( taboolist->ntaboolabels == 0 )
1041  return FALSE;
1042
1043  if( taboolist->needssorting )
1044  {
1045  BMScopyMemoryArray(taboolist->sortedlabels, taboolist->taboolabels, taboolist->ntaboolabels);
1046  SCIPsortInt(taboolist->sortedlabels, taboolist->ntaboolabels);
1047  }
1048
1049  found = SCIPsortedvecFindInt(taboolist->sortedlabels, elem, taboolist->ntaboolabels, &pos);
1050
1051  return found;
1052 }
1053
1054 /** get most recent k elements from taboo list */
1055 static
1056 int* tabooListGetLastK(
1057  TABOOLIST* taboolist, /**< taboo list data structure */
1058  int k /**< the number of elements that should be returned */
1059  )
1060 {
1061  assert(taboolist != NULL);
1062  assert(k <= taboolist->ntaboolabels);
1063  assert(k > 0);
1064
1065  return &taboolist->taboolabels[taboolist->ntaboolabels - k];
1066 }
1067
1068 /** get number of elements in taboo list */
1069 static
1070 int taboolistgetNElems(
1071  TABOOLIST* taboolist /**< taboo list data structure */
1072  )
1073 {
1074  return taboolist->ntaboolabels;
1076
1077 /** free a rolling horizon data structure */
1078 static
1079 void rollingHorizonFree(
1080  SCIP* scip, /**< SCIP data structure */
1081  ROLLINGHORIZON** rollinghorizon /**< pointer to rolling horizon data structure */
1082  )
1083 {
1084  assert(scip != NULL);
1085  assert(rollinghorizon != NULL);
1086
1087  /* empty rolling horizon */
1088  if( *rollinghorizon == NULL )
1089  return;
1090
1091  if( (*rollinghorizon)->variablegraph != NULL )
1092  {
1093  SCIPvariableGraphFree(scip, &(*rollinghorizon)->variablegraph);
1094  }
1095
1096  SCIPfreeBlockMemoryArray(scip, &(*rollinghorizon)->distances, (*rollinghorizon)->distancessize);
1097  SCIPfreeBlockMemoryArray(scip, &(*rollinghorizon)->used, (*rollinghorizon)->distancessize);
1098  SCIPfreeBlockMemory(scip, rollinghorizon);
1099 }
1100
1101 /** is there potential to run another iteration of the rolling horizon approach? */
1102 static
1104  SCIP* scip, /**< SCIP data structure */
1105  ROLLINGHORIZON* rollinghorizon, /**< rolling horizon data structure */
1106  SCIP_HEURDATA* heurdata /**< heuristic data */
1107  )
1109  int maxnused = (int)(heurdata->rollhorizonlimfac * (SCIPgetNBinVars(scip) + SCIPgetNIntVars(scip)
1110  - rollinghorizon->nnonreachable));
1111
1112  /* run again if a certain percentage of the reachable variables (in the same connected component)
1113  * was not used in a previous neighborhood
1114  */
1115  return (rollinghorizon->nused < maxnused);
1116 }
1117
1118 /** store the distances from the selected variable permanently for the rolling horizon approach */
1119 static
1121  ROLLINGHORIZON* rollinghorizon, /**< rolling horizon data structure */
1122  int* distances /**< breadth-first distances indexed by Probindex of variables */
1123  )
1124 {
1125  int i;
1126  BMScopyMemoryArray(rollinghorizon->distances, distances, rollinghorizon->distancessize);
1127  rollinghorizon->lastdistance = 0;
1128  rollinghorizon->nnonreachable = 0;
1129
1130  /* collect number of nonreachable variables */
1131  for( i = 0; i < rollinghorizon->distancessize; ++i )
1132  {
1133  if( distances[i] == -1 )
1134  ++rollinghorizon->nnonreachable;
1135  }
1136 }
1137
1138 /** is the variable in the current neighborhood which is given by the breadth-first distances from a central variable? */
1139 static
1141  SCIP_VAR* var, /**< problem variable */
1142  int* distances, /**< breadth-first distances indexed by Probindex of variables */
1143  int maxdistance /**< maximum distance (inclusive) to be considered for neighborhoods */
1144  )
1146  assert(var != NULL);
1147  assert(distances != NULL);
1148  assert(maxdistance >= 0);
1149  assert(SCIPvarGetProbindex(var) >= 0);
1150
1151  return (distances[SCIPvarGetProbindex(var)] != -1 && distances[SCIPvarGetProbindex(var)] <= maxdistance);
1152 }
1153
1154 /** get fixing value of variable */
1155 static
1157  SCIP* scip, /**< SCIP data structure */
1158  SCIP_SOL* sol, /**< solution in main SCIP for fixing values */
1159  SCIP_VAR* var /**< problem variable */
1160  )
1162  SCIP_Real fixval;
1163  SCIP_Real lb;
1164  SCIP_Real ub;
1165
1166  fixval = SCIPgetSolVal(scip, sol, var);
1167  lb = SCIPvarGetLbGlobal(var);
1168  ub = SCIPvarGetUbGlobal(var);
1169  assert(SCIPisLE(scip, lb, ub));
1170
1171  /* due to dual reductions, it may happen that the solution value is not in the variable's domain anymore */
1172  if( SCIPisLT(scip, fixval, lb) )
1173  fixval = lb;
1174  else if( SCIPisGT(scip, fixval, ub) )
1175  fixval = ub;
1176
1177  return fixval;
1178 }
1179
1180 /** fixes variables in subproblem based on long breadth-first distances in variable graph */
1181 static
1183  SCIP* scip, /**< SCIP data structure */
1184  SCIP_HEURDATA* heurdata, /**< heuristic data */
1185  ROLLINGHORIZON* rollinghorizon, /**< rolling horizon data structure to save relevant information, or NULL if not needed */
1186  SCIP_SOL* sol, /**< solution in main SCIP for fixing values */
1187  SCIP_VAR** vars, /**< variables in the main SCIP */
1188  SCIP_VAR** fixedvars, /**< buffer to store variables that should be fixed */
1189  SCIP_Real* fixedvals, /**< buffer to store fixing values for fixed variables */
1190  int* distances, /**< breadth-first distances indexed by Probindex of variables */
1191  int maxdistance, /**< maximum distance (inclusive) to be considered for neighborhoods */
1192  int* nfixings /**< pointer to store number of fixed variables */
1193  )
1194 {
1195  int i;
1196  int nbinvars;
1197  int nintvars;
1198  int nvars;
1199  int nvarstofix;
1200
1201  SCIP_CALL( SCIPgetVarsData(scip, NULL, &nvars, &nbinvars, &nintvars, NULL, NULL) );
1202
1203  nvarstofix = heurdata->fixcontvars ? nvars : nbinvars + nintvars;
1204  *nfixings = 0;
1205
1206  /* change bounds of variables of the subproblem */
1207  for( i = 0; i < nvarstofix; i++ )
1208  {
1209  /* fix all variables that are too far away from this variable according to maxdistance */
1210  if( distances[i] == -1 || distances[i] > maxdistance )
1211  {
1212  SCIP_Real fixval;
1213
1214  fixval = getFixVal(scip, sol, vars[i]);
1215
1216  /* store variable and value of this fixing */
1217  if( !SCIPisInfinity(scip, REALABS(fixval)) )
1218  {
1219  fixedvars[*nfixings] = vars[i];
1220  fixedvals[*nfixings] = fixval;
1221  ++(*nfixings);
1222  }
1223  }
1224  else if( rollinghorizon != NULL && i < nbinvars + nintvars && ! rollinghorizon->used[i] )
1225  {
1226  ++rollinghorizon->nused;
1227  rollinghorizon->used[i] = TRUE;
1228  }
1229  }
1230
1231  if( rollinghorizon != NULL )
1232  {
1233  rollinghorizon->lastmaxdistance = maxdistance;
1234  rollinghorizon->niterations++;
1235  }
1236
1237  return SCIP_OKAY;
1238 }
1239
1240 /** determine the maximum allowed distance to stay within the restriction to fix at least minfixingrate many non
1241  * neighborhood variables
1242  */
1243 static
1245  SCIP* scip, /**< SCIP data structure */
1246  SCIP_HEURDATA* heurdata, /**< heuristic data */
1247  int* distances, /**< breadth-first distances indexed by Probindex of variables */
1248  int* choosevardistance /**< pointer to store the computed maximum distance */
1249  )
1250 {
1251  int* distancescopy;
1252  int nrelevantdistances;
1253  int criticalidx;
1254  int zeropos;
1255  int nvars;
1256  int nbinvars;
1257  int nintvars;
1258
1259  SCIP_CALL( SCIPgetVarsData(scip, NULL, &nvars, &nbinvars, &nintvars, NULL, NULL) );
1260
1261  nrelevantdistances = (heurdata->fixcontvars ? nvars : (nbinvars + nintvars));
1262
1263  /* copy the relevant distances of either the discrete or all problem variables and sort them */
1264  SCIP_CALL( SCIPduplicateBufferArray(scip, &distancescopy, distances, nrelevantdistances) );
1265  SCIPsortInt(distancescopy, nrelevantdistances);
1266
1267  /* distances can be infinite in the case of multiple connected components; therefore, search for the index of the
1268  * zero entry, which is the unique representative of the chosen variable in the sorted distances
1269  */
1270  zeropos = -1;
1271
1272  /* TODO: use selection method instead */
1273  (void)SCIPsortedvecFindInt(distancescopy, 0, nrelevantdistances, &zeropos);
1274  assert(zeropos >= 0);
1275
1276  /* determine the critical index to look for an appropriate neighborhood distance, starting from the zero position */
1277  criticalidx = zeropos + (int)((1.0 - heurdata->minfixingrate) * nrelevantdistances);
1278  criticalidx = MIN(criticalidx, nrelevantdistances - 1);
1279
1280  /* determine the maximum breadth-first distance such that the neighborhood size stays small enough (below 1-minfixingrate)*/
1281  *choosevardistance = distancescopy[criticalidx];
1282
1283  /* we set the distance to exactly the distance at the critical index. If the distance at critical index is not the
1284  * last one before the distance increases, we decrease the choosevardistance such that the entire neighborhood
1285  * fits into the minfixingrate restriction
1286  */
1287  if( criticalidx != nrelevantdistances - 1 && distancescopy[criticalidx + 1] == *choosevardistance )
1288  (*choosevardistance)--;
1289
1290  /* update the maximum distance */
1291  heurdata->maxseendistance = MAX(heurdata->maxseendistance, distancescopy[nrelevantdistances - 1]);
1292
1293  SCIPfreeBufferArray(scip, &distancescopy);
1294
1295  return SCIP_OKAY;
1296 }
1297
1298 /** gets the average size of a discrete neighborhood over all variables tested */
1299 static
1301  SCIP_HEURDATA* heurdata /**< heuristic data */
1302  )
1303 {
1304  return heurdata->sumdiscneighborhoodvars / (MAX(1.0, (SCIP_Real)heurdata->nneighborhoods));
1306
1307 /** count occurrences of this label */
1308 static
1309 int countLabel(
1310  int* labels, /**< sorted array of labels */
1311  int start, /**< start position */
1312  int nlabels /**< length of the labels array */
1313  )
1315  int label = labels[start];
1316  int end = start;
1317
1318  assert(labels != NULL);
1319  assert(start < nlabels);
1320  assert(start >= 0);
1321
1322  do
1323  {
1324  ++end;
1325  }
1326  while( end < nlabels && labels[end] == label );
1327
1328  return end - start;
1329 }
1330
1331 /** todo select initial variable based on decomposition information, if available */
1332 static
1334  SCIP* scip, /**< SCIP data structure */
1335  SCIP_HEURDATA* heurdata, /**< heuristic data */
1336  SCIP_DECOMP* decomp, /**< decomposition data structure with variable labels */
1337  SCIP_VGRAPH* vargraph, /**< variable graph data structure to work on */
1338  int* distances, /**< breadth-first distances indexed by Probindex of variables */
1339  SCIP_VAR** selvar, /**< pointer to store the selected variable */
1340  int* selvarmaxdistance /**< maximal distance k to consider for selected variable neighborhood */
1341  )
1342 {
1343  SCIP_SOL* sol;
1344  SCIP_VAR** vars;
1345  SCIP_VAR** varscopy;
1346  int* varlabels;
1347  int* discvaridxs;
1348  SCIP_Real bestpotential;
1349  int nbinvars;
1350  int nintvars;
1351  int nvars;
1352  int currblockstart;
1353  int bestvaridx;
1354  int cntmessages;
1355  int nblocks;
1356  TABOOLIST* taboolist;
1357
1358  assert(scip != NULL);
1359  assert(heurdata != NULL);
1360  assert(decomp != NULL);
1361  assert(vargraph != NULL);
1362  assert(distances != NULL);
1363  assert(selvar != NULL);
1364  assert(selvarmaxdistance != NULL);
1365
1366  sol = SCIPgetBestSol(scip);
1367  assert(sol != NULL);
1368  nblocks = SCIPdecompGetNBlocks(decomp);
1369  /* create a taboo list for recently used block labels at the first initial variable selection */
1370  if( heurdata->taboolist == NULL )
1371  {
1372  SCIPdebugMsg(scip, "Creating taboo list\n");
1373  SCIP_CALL( createTabooList(scip, &heurdata->taboolist, nblocks) );
1374  }
1375
1376  taboolist = heurdata->taboolist;
1377  assert(taboolist != NULL);
1378
1379  /* reset taboo list if a new solution has been found since the last initialization call */
1380  if( sol != heurdata->lastinitsol )
1381  {
1382  int nblockstokeep = 3;
1383  int e;
1384  int ntaboolistelems;
1385  ntaboolistelems = taboolistgetNElems(heurdata->taboolist);
1386
1387  /* keep the last 3 blocks except for border cases of very coarse decomposition, or too few taboo elements */
1388  if( taboolistgetNElems(heurdata->taboolist) > 0 )
1389  {
1390  nblockstokeep = MIN(nblockstokeep, nblocks - 1);
1391  nblockstokeep = MIN(nblockstokeep, MAX(1, ntaboolistelems - 1));
1392  nblockstokeep = MAX(nblockstokeep, 0);
1393  }
1394  else
1395  nblockstokeep = 0;
1396
1397  SCIPdebugMsg(scip, "Resetting taboo list, keeping %d elements\n", nblockstokeep);
1398  if( nblockstokeep > 0 )
1399  {
1400  int* labelstokeep;
1401  int* taboolistlastk;
1402  taboolistlastk = tabooListGetLastK(taboolist, nblockstokeep);
1403  SCIP_CALL( SCIPduplicateBufferArray(scip, &labelstokeep, taboolistlastk, nblockstokeep) );
1404
1405  tabooListReset(taboolist);
1406
1407  /* reinstall the last 3 elements into the taboo list */
1408  for( e = 0; e < nblockstokeep; ++e )
1409  {
1410  SCIP_CALL( tabooListAdd(scip, taboolist, labelstokeep[e]) );
1411  }
1412
1413  SCIPfreeBufferArray(scip, &labelstokeep);
1414  }
1415  else if( ntaboolistelems > 0 )
1416  {
1417  tabooListReset(taboolist);
1418  }
1419
1420  heurdata->allblocksunsuitable = FALSE;
1421  }
1422
1423  *selvar = NULL;
1424  /* do not continue if, for this solution, all blocks are known to be unsuitable */
1425  if( heurdata->allblocksunsuitable )
1426  {
1427  SCIPdebugMsg(scip, "Skip initial variable selection because all blocks are unsuitable for solution %d\n",
1428  SCIPsolGetIndex(sol));
1429  return SCIP_OKAY;
1430  }
1431
1432  /* get integer and binary variables from problem and labels for all variables */
1433  SCIP_CALL( SCIPgetVarsData(scip, &vars, &nvars, &nbinvars, &nintvars, NULL, NULL) );
1434
1435  SCIP_CALL( SCIPduplicateBufferArray(scip, &varscopy, vars, nvars) );
1436  SCIP_CALL( SCIPallocBufferArray(scip, &varlabels, nvars) );
1437  SCIP_CALL( SCIPallocBufferArray(scip, &discvaridxs, nvars) );
1438
1439  SCIPdecompGetVarsLabels(decomp, vars, varlabels, nvars);
1440
1441  /* sort the variables copy by the labels */
1442  SCIPsortIntPtr(varlabels, (void **)varscopy, nvars);
1443
1444  currblockstart = 0;
1445  bestpotential = 0.0;
1446  bestvaridx = -1;
1447  cntmessages = 0;
1448  /* compute the potential for every block */
1449  while( currblockstart < nvars )
1450  {
1451  int currblockend;
1452  int v;
1453  int label = varlabels[currblockstart];
1454  int ndiscblockvars;
1455  SCIP_Real potential;
1456
1457  currblockend = currblockstart + countLabel(varlabels, currblockstart, nvars);
1458
1459  /* this block was recently used and should be skipped */
1460  if( tabooListFind(taboolist, label) )
1461  {
1462  if( cntmessages++ < 3 )
1463  SCIPdebugMsg(scip, "Skipping block <%d> from taboo list\n", label);
1464
1465  currblockstart += currblockend;
1466
1467  continue;
1468  }
1469
1470  /* author bzfhende
1471  *
1472  * TODO omit the linking variables from the computation of the potential?
1473  */
1474  /* check if block has discrete variables */
1475  ndiscblockvars = 0;
1476  for( v = currblockstart; v < currblockend; ++v )
1477  {
1478  if( SCIPvarGetType(varscopy[v]) == SCIP_VARTYPE_BINARY || SCIPvarGetType(varscopy[v]) == SCIP_VARTYPE_INTEGER )
1479  discvaridxs[ndiscblockvars++] = v;
1480  }
1481
1482  /* skip potential computation if block has no discrete variables */
1483  if( ndiscblockvars > 0 )
1484  {
1485  potential = getPotential(scip, heurdata, sol, &(varscopy[currblockstart]), currblockend - currblockstart);
1486
1487  if( potential > bestpotential )
1488  {
1489  bestpotential = potential;
1490  /* randomize the selection of the best variable */
1491  bestvaridx = discvaridxs[SCIPrandomGetInt(heurdata->randnumgen, 0, ndiscblockvars - 1)];
1492  assert(bestvaridx >= 0);
1493  }
1494  }
1495
1496  currblockstart += currblockend;
1497  }
1498
1499  /* we return the first discrete variable from the block with maximum potential */
1500  if( bestvaridx >= 0 )
1501  {
1502  *selvar = varscopy[bestvaridx];
1503
1504  /* save block label in taboo list to not use it again too soon */
1505  SCIP_CALL( tabooListAdd(scip, taboolist, varlabels[bestvaridx]) );
1506
1507  SCIPdebugMsg(scip, "Select initial variable <%s> from block <%d>\n", SCIPvarGetName(*selvar), varlabels[bestvaridx]);
1508  }
1509  else
1510  {
1511  SCIPdebugMsg(scip, "Could not find suitable block for variable selection.\n");
1512  heurdata->allblocksunsuitable = TRUE;
1513  *selvar = NULL;
1514  }
1515
1516  /* use the variable constraint graph to compute distances to all other variables, and store the selvarmaxdistance */
1517  if( *selvar != NULL )
1518  {
1519  SCIP_CALL( SCIPvariablegraphBreadthFirst(scip, vargraph, selvar, 1, distances,
1520  heurdata->maxdistance == -1 ? INT_MAX : heurdata->maxdistance, INT_MAX, INT_MAX) );
1521
1522  SCIP_CALL( determineMaxDistance(scip, heurdata, distances, selvarmaxdistance) );
1523
1524  /* maximum distance is 0, i.e., even the size of the 1-neighborhood of this variable exceeds the fixing rate */
1525  if( *selvarmaxdistance == 0 )
1526  {
1527  SCIPdebugMsg(scip, "1-Neighborhood of variable <%s> too large.\n", SCIPvarGetName(*selvar));
1528  *selvar = NULL;
1529  }
1530  }
1531
1532  /* remember this solution for the next initial selection */
1533  heurdata->lastinitsol = sol;
1534
1535  SCIPfreeBufferArray(scip, &discvaridxs);
1536  SCIPfreeBufferArray(scip, &varlabels);
1537  SCIPfreeBufferArray(scip, &varscopy);
1538
1539  return SCIP_OKAY;
1540 }
1541
1542
1543
1544 /** select a good starting variable at the first iteration of a rolling horizon approach */
1545 static
1547  SCIP* scip, /**< SCIP data structure */
1548  SCIP_HEURDATA* heurdata, /**< heuristic data */
1549  SCIP_VGRAPH* vargraph, /**< variable graph data structure to work on */
1550  int* distances, /**< breadth-first distances indexed by Probindex of variables */
1551  SCIP_VAR** selvar, /**< pointer to store the selected variable */
1552  int* selvarmaxdistance /**< maximal distance k to consider for selected variable neighborhood */
1553  )
1554 {
1555  SCIP_SOL* sol;
1556  SCIP_VAR** vars; /* original scip variables */
1557  int nbinvars;
1558  int nintvars;
1559  int nvars;
1560  int nsearched;
1561  int searchlimit;
1562  int nintegralvarsleft;
1563  int nintegralvarsbound;
1564  int v;
1565  SCIP_VAR** varscopy;
1566  int maxdistance;
1567  SCIP_Real maxpotential;
1568
1569  assert(vargraph != NULL);
1570  assert(scip != NULL);
1571  assert(heurdata != NULL);
1572  assert(selvar != NULL);
1573  sol = SCIPgetBestSol(scip);
1574  assert(sol != NULL);
1575
1576  /* get required data of the original problem */
1577  SCIP_CALL( SCIPgetVarsData(scip, &vars, &nvars, &nbinvars, &nintvars, NULL, NULL) );
1578
1579  /* copy SCIP variables */
1580  SCIP_CALL( SCIPduplicateBufferArray(scip, &varscopy, vars, nbinvars + nintvars) );
1581  nsearched = 0;
1582  maxpotential = SCIP_REAL_MIN;
1583
1584  /* determine upper bound on neighborhood size */
1585  nintegralvarsbound = (int)((1.0 - heurdata->minfixingrate) * (nbinvars + nintvars));
1586
1587  /* maximum distance from selected variable for breadth-first search (if set to -1, we compute an exhaustive breadth-first
1588  * search and sort the variables by their distance)
1589  */
1590  maxdistance = (heurdata->maxdistance == - 1 ? INT_MAX : heurdata->maxdistance);
1591
1592  nintegralvarsleft = nbinvars + nintvars;
1593  *selvar = NULL;
1594
1595  /* sort inactive variables to the end of the array */
1596  for( v = nintegralvarsleft - 1; v >= 0; --v )
1597  {
1598  if( ! SCIPvarIsActive(varscopy[v]) )
1599  {
1600  varscopy[v] = varscopy[nintegralvarsleft - 1];
1601  --nintegralvarsleft;
1602  }
1603  }
1604
1605  /* adjust the search limit */
1606  searchlimit = heurdata->nneighborhoods < 10 ? 5 : (int)(nintegralvarsleft / heurdataAvgDiscreteNeighborhoodSize(heurdata));
1607  searchlimit = MIN(searchlimit, 10);
1608
1609  /* multi variable potential: choose different disjoint neighborhoods, compare their potential */
1610  while( nsearched < searchlimit && nintegralvarsleft > 0 )
1611  {
1612  SCIP_VAR** neighborhood;
1613  SCIP_VAR* choosevar;
1614  int neighborhoodsize;
1615  int ndiscvarsneighborhood;
1616  int choosevardistance;
1617
1618  ++nsearched;
1619
1620  /* select a variable to start with randomly, but make sure it is active */
1621  do
1622  {
1623  int idx = SCIPrandomGetInt(heurdata->randnumgen, 0, nintegralvarsleft - 1);
1624  choosevar = varscopy[idx];
1625  assert(choosevar != NULL);
1626  /* sort inactive variables to the end */
1627  if( SCIPvarGetProbindex(choosevar) < 0 )
1628  {
1629  varscopy[idx] = varscopy[nintegralvarsleft - 1];
1630  --nintegralvarsleft;
1631  }
1632  }
1633  while( SCIPvarGetProbindex(choosevar) < 0 && nintegralvarsleft > 0 );
1634
1635  /* if there was no variable chosen, there are no active variables left */
1636  if( SCIPvarGetProbindex(choosevar) < 0 )
1637  {
1638  SCIPdebugMsg(scip, "No active variable left to perform breadth-first search\n");
1639  break;
1640  }
1641
1642  assert(SCIPvarIsIntegral(choosevar));
1643
1644  /* get neighborhood storage */
1645  SCIP_CALL( SCIPallocBufferArray(scip, &neighborhood, nvars) );
1646
1647  /* determine breadth-first distances from the chosen variable */
1648  SCIP_CALL( SCIPvariablegraphBreadthFirst(scip, vargraph, &choosevar, 1, distances, maxdistance, INT_MAX, INT_MAX) );
1649
1650  /* use either automatic or user-defined max-distance for neighborhood in variable constraint graph */
1651  if( heurdata->maxdistance != -1 )
1652  {
1653  choosevardistance = heurdata->maxdistance;
1654  }
1655  else
1656  {
1657  SCIP_CALL( determineMaxDistance(scip, heurdata, distances, &choosevardistance) );
1658  }
1659
1660  ndiscvarsneighborhood = 0;
1661  neighborhoodsize = 0;
1662
1663  /* loop over variables and determine neighborhood */
1664  for( v = nvars - 1; v >= 0; --v )
1665  {
1666  SCIP_VAR* currvar;
1667  currvar = vars[v];
1668
1669  /* put variable in the neighborhood */
1670  if( isVariableInNeighborhood(currvar, distances, choosevardistance) )
1671  {
1672  neighborhood[neighborhoodsize++] = currvar;
1673
1674  /* increase discrete variables counter */
1675  if( SCIPvarIsIntegral(currvar) )
1676  ++ndiscvarsneighborhood;
1677  }
1678  }
1679
1680  /* check if neighborhood contains too many integer variables in order to satisfy the minimum fixing rate */
1681  if( ndiscvarsneighborhood >= nintegralvarsbound || ndiscvarsneighborhood <= 1 )
1682  {
1683  SCIPdebugMsg(scip, "Too many or too few discrete variables in neighboorhood: %d (%d)\n",
1684  ndiscvarsneighborhood, nbinvars + nintvars);
1685  }
1686  else
1687  {
1688  /* compare the neighborhood potential to the best potential found so far */
1689  SCIP_Real potential = getPotential(scip, heurdata, sol, neighborhood, neighborhoodsize);
1690
1691  /* big potential, take this variable */
1692  if( potential > maxpotential )
1693  {
1694  maxpotential = potential;
1695  *selvar = choosevar;
1696  *selvarmaxdistance = choosevardistance;
1697  }
1698  }
1699
1700  /* sort neighborhood variables to the end so that this neighborhood is not considered in further samples */
1701  for( v = nintegralvarsleft - 1; v >= 0; --v )
1702  {
1703  SCIP_VAR* currvar;
1704  currvar = vars[v];
1705
1706  if( isVariableInNeighborhood(currvar, distances, choosevardistance) )
1707  {
1708  varscopy[v] = varscopy[nintegralvarsleft - 1];
1709  --nintegralvarsleft;
1710  }
1711  }
1712
1713  heurdata->sumdiscneighborhoodvars += ndiscvarsneighborhood;
1714  heurdata->sumneighborhoodvars += neighborhoodsize;
1715  ++heurdata->nneighborhoods;
1716
1717  /* free current neighborhood */
1718  SCIPfreeBufferArray(scip, &neighborhood);
1719  }
1720
1721  SCIPfreeBufferArray(scip, &varscopy);
1722
1723  /* maybe no variable has a positive delta */
1724  if( !SCIPisPositive(scip, maxpotential) || *selvar == NULL )
1725  {
1726  SCIPdebugMsg(scip, "Stopping with maxpotential %15.9f and selected variable %s\n",
1727  maxpotential, *selvar != NULL ? SCIPvarGetName(*selvar) : "none");
1728  *selvar = NULL;
1729  }
1730
1731  return SCIP_OKAY;
1732 }
1733
1734 /** select the next variable using the rolling horizon */
1735 static
1737  SCIP* scip, /**< SCIP data structure */
1738  SCIP_HEURDATA* heurdata, /**< heuristic data */
1739  ROLLINGHORIZON* rollinghorizon, /**< rolling horizon data structure to save relevant information, or NULL if not needed */
1740  int* distances, /**< breadth-first distances indexed by Probindex of variables */
1741  SCIP_VAR** selvar, /**< pointer to store the selected variable */
1742  int* selvarmaxdistance /**< maximal distance k to consider for selected variable neighborhood */
1743  )
1744 {
1745  SCIP_VAR** vars; /* original scip variables */
1746  int i;
1747  int nbinvars;
1748  int nintvars;
1749  int minunuseddistance;
1750
1751  assert(scip != NULL);
1752  assert(rollinghorizon != NULL);
1753  assert(distances != NULL);
1754  assert(selvar != NULL);
1755  assert(selvarmaxdistance != NULL);
1756
1757  SCIP_CALL( SCIPgetVarsData(scip, &vars, NULL, &nbinvars, &nintvars, NULL, NULL) );
1758
1759  /* loop over the variables that are left and pick the variable with
1760  * - the smallest, always nondecreasing distance
1761  * - that was not used before in a neighborhood
1762  */
1763  do
1764  {
1765  minunuseddistance = INT_MAX;
1766  *selvarmaxdistance = rollinghorizon->lastmaxdistance;
1767  *selvar = NULL;
1768  for( i = 0; i < nbinvars + nintvars && minunuseddistance > rollinghorizon->lastdistance; ++i )
1769  {
1770  if( rollinghorizon->distances[i] >= rollinghorizon->lastdistance
1771  && rollinghorizon->distances[i] < minunuseddistance && ! rollinghorizon->used[i] )
1772  {
1773  minunuseddistance = rollinghorizon->distances[i];
1774  *selvar = vars[i];
1775  }
1776  }
1777
1778  /* if no variable could be selected, we can stop */
1779  if( *selvar == NULL )
1780  {
1781  *selvarmaxdistance = 0;
1782  return SCIP_OKAY;
1783  }
1784
1785  /* determine the distances to other variables from this variable */
1786  SCIP_CALL( SCIPvariablegraphBreadthFirst(scip, rollinghorizon->variablegraph, selvar, 1, distances, *selvarmaxdistance, INT_MAX, INT_MAX) );
1787
1788  SCIP_CALL( determineMaxDistance(scip, heurdata, distances, selvarmaxdistance) );
1789
1790  /* mark this variable as used in order to not find it again */
1791  if( *selvarmaxdistance == 0 )
1792  {
1793  rollinghorizon->used[SCIPvarGetProbindex(*selvar)] = TRUE;
1794  rollinghorizon->nused++;
1795  *selvar = NULL;
1796  }
1797  }
1798  while( rollingHorizonRunAgain(scip, rollinghorizon, heurdata) && (*selvar == NULL || *selvarmaxdistance == 0) );
1799
1800  /* breadth-first search determines the distances of all variables
1801  * that are no more than maxdistance away from the start variable
1802  */
1803  assert(*selvarmaxdistance <= rollinghorizon->lastmaxdistance);
1804  *selvarmaxdistance = MIN(*selvarmaxdistance, rollinghorizon->lastmaxdistance);
1805  rollinghorizon->lastdistance = minunuseddistance;
1806  rollinghorizon->lastmaxdistance = *selvarmaxdistance;
1807
1808  return SCIP_OKAY;
1809 }
1810
1811 /** mark some of the blocks between currblockstart and currblockend as recently used, depending on overlap */
1812 static
1814  SCIP* scip, /**< SCIP data structure */
1815  DECOMPHORIZON* decomphorizon, /**< decomposition horizon data structure */
1816  SCIP_HEURDATA* heurdata, /**< heuristic data */
1817  SCIP_SOL* sol, /**< solution by which some of the blocks should be marked */
1818  int blockstartpos, /**< current start position of interval */
1819  int blockendpos /**< current end position (inclusive) of interval */
1820  )
1821 {
1822  int nvarsinterval;
1824  int solstamppos;
1825  int b;
1826  SCIP_Real overlapcomplement;
1827
1828  assert(decomphorizon != NULL);
1829  assert(heurdata != NULL);
1830
1831  /* is the next block unsuitable or have we reached the end of the blocks? In those cases,
1832  * we mark all blocks of the current interval; we hence avoid to rerun on a subset of the current subproblem
1833  * in the next iteration; we achieve this by setting the overlap to 0.0, (its complement to 1.0)
1834  * such that all blocks are marked
1835  */
1836  if( blockendpos == decomphorizon->nblocks - 1 || ! decomphorizon->suitable[decomphorizon->blockindices[blockendpos + 1]] )
1837  overlapcomplement = 1.0;
1838  else
1839  overlapcomplement = 1.0 - heurdata->overlap;
1840
1841  /* count the total number of variables in the subproblem defining blocks */
1842  nvarsinterval = 0;
1843  for( b = blockstartpos; b <= blockendpos; ++b )
1844  nvarsinterval += decomphorizon->ndiscretevars[decomphorizon->blockindices[b]];
1845
1847  /* stamp the first blocks up to the desired overlap by the current incumbent solution */
1848  for( solstamppos = blockstartpos; solstamppos <= blockendpos; ++solstamppos )
1849  {
1850  decomphorizon->lastsolblock[decomphorizon->blockindices[solstamppos]] = sol;
1852
1853  if( nvarsstartofinterval >= overlapcomplement * nvarsinterval )
1854  break;
1855  }
1856  decomphorizon->lastblockpos = solstamppos;
1857  SCIPdebugMsg(scip, "Blocks %d (label %d)-- %d (label %d) marked with incumbent solution\n",
1858  blockstartpos, decomphorizon->blocklabels[decomphorizon->blockindices[blockstartpos]],
1859  solstamppos, decomphorizon->blocklabels[decomphorizon->blockindices[solstamppos]]);
1860
1861  /* remember the blocks up to the found position as most recent overlap interval */
1862  decompHorizonSetOverlapInterval(decomphorizon, blockstartpos, solstamppos);
1863 }
1864
1865 /** determine the variable fixings based on a decomposition */
1866 static
1868  SCIP* scip, /**< SCIP data structure */
1869  DECOMPHORIZON* decomphorizon, /**< decomposition horizon data structure */
1870  SCIP_VAR** fixedvars, /**< buffer to store variables that should be fixed */
1871  SCIP_Real* fixedvals, /**< buffer to store fixing values for fixed variables */
1872  int* nfixings, /**< pointer to store the number of fixed variables */
1873  SCIP_HEURDATA* heurdata, /**< heuristic data */
1874  SCIP_Bool* success /**< used to store whether the creation of the subproblem worked */
1875  )
1876 {
1877  SCIP_SOL* sol;
1878  SCIP_Bool hasnext;
1880  int currblockstart;
1881  int currblockend;
1882  int currblocklabel;
1883  int maxblocksize;
1884
1885  assert(scip != NULL);
1886  assert(decomphorizon != NULL);
1887
1888  sol = SCIPgetBestSol(scip);
1889
1890  /* initialize the decomposition horizon first for the current variables */
1891  if( ! decompHorizonIsInitialized(decomphorizon) )
1892  {
1893  SCIP_CALL( decompHorizonInitialize(scip, decomphorizon, heurdata) );
1894  }
1895
1896  maxblocksize = (int)((1.0 - heurdata->minfixingrate) * (SCIPgetNBinVars(scip) + SCIPgetNIntVars(scip))) - 1;
1897
1898  /* query the next suitable interval of blocks */
1899  hasnext = decompHorizonNext(scip, decomphorizon, heurdata, maxblocksize,
1901
1902  if( ! hasnext )
1903  {
1904  SCIPdebugMsg(scip, "Could not find a suitable interval that follows %d\n",
1905  decomphorizon->lastblockpos);
1906
1907  *success = FALSE;
1908  }
1909  else
1910  {
1911  /* fix all discrete/continuous variables that are not part of this interval */
1912  SCIP_VAR** vars;
1913  int v;
1914  int startblockposs[] = {fixlinkvars ? 0 : 1, currblockend + 1};
1915  int endblockposs[] = {currblockstart, decomphorizon->nblocks};
1916  int p;
1917  int b;
1918
1919  SCIPdebugMsg(scip, "Fix %s variables (%scluding linking variables) except blocks %d (label %d) -- %d (label %d)\n",
1920  heurdata->fixcontvars ? "all" : "discrete",
1921  fixlinkvars ? "in" : "ex",
1922  currblockstart, decomphorizon->blocklabels[decomphorizon->blockindices[currblockstart]],
1923  currblockend, decomphorizon->blocklabels[decomphorizon->blockindices[currblockend]]);
1924
1925  vars = decomphorizonGetVars(decomphorizon);
1926
1927  /* iterate over the two blocks left and right of the selected consecutive interval and fix all variables
1928  *
1929  * 0, ... b, ... ,[currblockstart, ..., currblockend], currblockend + 1, ..., decomphorizon->nblocks - 1
1930  */
1931  for( p = 0; p < 2; ++p )
1932  {
1933  /* iterate over all blocks and fix those outside of the blocks interval that defines the current subproblem */
1934  for( b = startblockposs[p]; b < endblockposs[p]; ++b )
1935  {
1936  int blockind = decomphorizon->blockindices[b];
1937  int varstartpos = blockind == 0 ? 0 : decomphorizon->varblockend[blockind - 1];
1938  int varendpos = decomphorizon->varblockend[blockind];
1939
1940  /* fix variables inside of this block */
1941  for( v = varstartpos; v < varendpos; ++v )
1942  {
1943  SCIP_VAR* var = vars[v];
1944
1945  if( heurdata->fixcontvars || SCIPvarGetType(var) != SCIP_VARTYPE_CONTINUOUS )
1946  {
1947  SCIP_Real fixval;
1948
1949  fixval = getFixVal(scip, sol, var);
1950
1951  /* store variable and value of this fixing */
1952  if( !SCIPisInfinity(scip, REALABS(fixval)) )
1953  {
1954  fixedvars[*nfixings] = var;
1955  fixedvals[*nfixings] = fixval;
1956  ++(*nfixings);
1957  }
1958  }
1959  }
1960  }
1961  }
1962
1963  *success = checkFixingrate(scip, heurdata, *nfixings);
1964
1965  decompHorizonMarkInterval(scip, decomphorizon, heurdata, sol, currblockstart, currblockend);
1966  }
1967
1968  return SCIP_OKAY; /*lint !e438*/
1969 }
1970
1971 /** choose a decomposition from the store or return NULL if none exists/no decomposition was suitable */
1972 static
1974  SCIP* scip /**< SCIP data structure */
1975  )
1976 {
1977  SCIP_DECOMP** decomps;
1978  int ndecomps;
1979  int currdecomp;
1980
1981  /* TODO coming soon: better selection than last nontrivial decomposition that has been input */
1982  SCIPgetDecomps(scip, &decomps, &ndecomps, FALSE);
1983  currdecomp = ndecomps;
1984
1985  while( --currdecomp >= 0 )
1986  {
1987  if( SCIPdecompGetNBlocks(decomps[currdecomp]) > 0 )
1988  return decomps[currdecomp];
1989  }
1990
1991  return NULL;
1992 }
1993
1994 /** determines the graph-induced variable fixings */
1995 static
1997  SCIP* scip, /**< original SCIP data structure */
1998  SCIP_VAR** fixedvars, /**< buffer to store variables that should be fixed */
1999  SCIP_Real* fixedvals, /**< buffer to store fixing values for fixed variables */
2000  int* nfixings, /**< pointer to store the number of fixed variables */
2001  SCIP_HEURDATA* heurdata, /**< heuristic data */
2002  ROLLINGHORIZON* rollinghorizon, /**< rolling horizon data structure to save relevant information, or NULL if not needed */
2003  DECOMPHORIZON* decomphorizon, /**< decomposition horizon data structure, or NULL */
2004  SCIP_Bool* success /**< used to store whether the creation of the subproblem worked */
2005  )
2006 {
2007  SCIP_VAR** vars;
2008  SCIP_SOL* sol;
2009  int* distances;
2010  SCIP_VGRAPH* vargraph;
2011  SCIP_VAR* selvar;
2012  int nvars;
2013  int nbinvars;
2014  int nintvars;
2015
2016  int selvarmaxdistance;
2017
2018  assert(fixedvars != NULL);
2019  assert(fixedvals != NULL);
2020  assert(nfixings != NULL);
2021
2022  *success = TRUE;
2023  *nfixings = 0;
2024  selvarmaxdistance = 0;
2025  sol = SCIPgetBestSol(scip);
2026  assert(sol != NULL);
2027
2028  /* determine the variable fixings based on latest user decomposition */
2029  if( decomphorizon != NULL )
2030  {
2031  SCIP_CALL( determineVariableFixingsDecomp(scip, decomphorizon, fixedvars, fixedvals, nfixings, heurdata, success) );
2032
2033  /* do not use fallback strategy if user parameter does not allow it */
2034  if( *success || ! heurdata->useselfallback )
2035  return SCIP_OKAY;
2036  }
2037
2038  /* get required data of the source problem */
2039  SCIP_CALL( SCIPgetVarsData(scip, &vars, &nvars, &nbinvars, &nintvars, NULL, NULL) );
2040  /* get the saved variable graph, or create a new one */
2041  if( rollinghorizon != NULL )
2042  {
2043  if( rollinghorizon->niterations == 0 )
2044  {
2045  /* create variable graph */
2046  SCIPdebugMsg(scip, "Creating variable constraint graph\n");
2047  SCIP_CALL( SCIPvariableGraphCreate(scip, &rollinghorizon->variablegraph, heurdata->relaxdenseconss, 1.0 - heurdata->minfixingrate, &heurdata->nrelaxedconstraints) );
2048  }
2049  else
2050  assert(rollinghorizon->variablegraph != NULL);
2051
2052  vargraph = rollinghorizon->variablegraph;
2053  }
2054  else
2055  {
2056  /* create variable graph */
2057  SCIPdebugMsg(scip, "Creating variable constraint graph\n");
2058  SCIP_CALL( SCIPvariableGraphCreate(scip, &vargraph, heurdata->relaxdenseconss, 1.0 - heurdata->minfixingrate, &heurdata->nrelaxedconstraints) );
2059  }
2060
2061  /* allocate buffer memory to hold distances */
2062  SCIP_CALL( SCIPallocBufferArray(scip, &distances, nvars) );
2063
2064  selvar = NULL;
2065
2066  /* in the first iteration of the rolling horizon approach, we select an initial variable */
2067  if( rollinghorizon == NULL || rollinghorizon->niterations == 0 )
2068  {
2069  SCIP_Bool userandomselection = TRUE;
2070
2071  /* choose the initial variable based on a user decomposition, if available */
2072  if( heurdata->usedecomprollhorizon )
2073  {
2074  SCIP_DECOMP* decomp = chooseDecomp(scip);
2075  if( decomp != NULL )
2076  {
2077  SCIP_CALL( selectInitialVariableDecomposition(scip, heurdata, decomp, vargraph,
2078  distances, &selvar, &selvarmaxdistance) );
2079
2080  userandomselection = (selvar == NULL && heurdata->useselfallback);
2081  }
2082  }
2083
2084  assert(selvar == NULL || !userandomselection);
2085  /* use random variable selection as fallback strategy, if no user decomposition is available, or the
2086  * heuristic should not use decomposition
2087  */
2088  if( userandomselection )
2089  {
2090  SCIP_CALL( selectInitialVariableRandomly(scip, heurdata, vargraph, distances, &selvar, &selvarmaxdistance) );
2091  }
2092
2093  /* collect and save the distances in the rolling horizon data structure */
2094  if( selvar != NULL && rollinghorizon != NULL )
2095  {
2096  /* collect distances in the variable graph of all variables to the selected variable */
2097  SCIP_CALL( SCIPvariablegraphBreadthFirst(scip, vargraph, &selvar, 1, distances, INT_MAX, INT_MAX, INT_MAX) );
2098  rollingHorizonStoreDistances(rollinghorizon, distances);
2099  rollinghorizon->lastmaxdistance = selvarmaxdistance;
2100  }
2101  }
2102  else
2103  {
2104  /* select the next variable, if variables are left */
2105  SCIP_CALL( selectNextVariable(scip, heurdata, rollinghorizon, distances, &selvar, &selvarmaxdistance) );
2106  }
2107
2108  assert(selvar == NULL || selvarmaxdistance > 0);
2109  if( selvar == NULL )
2110  {
2111  *success = FALSE;
2112  }
2113  else
2114  {
2115  SCIPdebugMsg(scip, "Selected variable <%s> as central variable for a <%d>-neighborhood\n",
2116  SCIPvarGetName(selvar), selvarmaxdistance);
2117
2118  /* fix variables that are not in the neighborhood around the selected variable */
2119  SCIP_CALL( fixNonNeighborhoodVariables(scip, heurdata, rollinghorizon, sol, vars, fixedvars, fixedvals, distances,
2120  selvarmaxdistance, nfixings) );
2121
2122  *success = checkFixingrate(scip, heurdata, *nfixings);
2123  }
2124
2125  SCIPfreeBufferArray(scip, &distances);
2126  if( rollinghorizon == NULL )
2127  SCIPvariableGraphFree(scip, &vargraph);
2128
2129  return SCIP_OKAY;
2130 }
2131
2132 /** set sub-SCIP solving limits */
2133 static
2135  SCIP* sourcescip, /**< SCIP data structure */
2136  SCIP* subscip, /**< SCIP data structure */
2137  SOLVELIMITS* solvelimits /**< pointer to solving limits data structure */
2138  )
2140  assert(sourcescip != NULL);
2141  assert(subscip != NULL);
2142  assert(solvelimits != NULL);
2143
2144  SCIP_CALL( SCIPcopyLimits(sourcescip, subscip) );
2145
2146  SCIP_CALL( SCIPsetLongintParam(subscip, "limits/nodes", solvelimits->nodelimit) );
2147  SCIP_CALL( SCIPsetLongintParam(subscip, "limits/stallnodes", solvelimits->stallnodelimit) );
2148
2149  /* safe long running times caused by lack of dual convergence */
2150  SCIP_CALL( SCIPsetRealParam(subscip, "limits/gap", 0.01) );
2151
2152  return SCIP_OKAY;
2153 }
2154
2155 /** set up the sub-SCIP */
2156 static
2158  SCIP* scip, /**< SCIP data structure */
2159  SCIP* subscip, /**< sub-SCIP data structure */
2160  SOLVELIMITS* solvelimits, /**< pointer to solving limits data structure */
2161  SCIP_HEUR* heur /**< this heuristic */
2162  )
2163 {
2164  SCIP_HEURDATA* heurdata;
2165  SCIP_Real cutoff;
2166  SCIP_Real upperbound;
2167
2168  heurdata = SCIPheurGetData(heur);
2169
2170  /* do not abort subproblem on CTRL-C */
2171  SCIP_CALL( SCIPsetBoolParam(subscip, "misc/catchctrlc", FALSE) );
2172
2173  /* disable output to console */
2174  SCIP_CALL( SCIPsetIntParam(subscip, "display/verblevel", 0) );
2175
2176  /* disable statistic timing inside sub SCIP */
2177  SCIP_CALL( SCIPsetBoolParam(subscip, "timing/statistictiming", FALSE) );
2178
2179  SCIP_CALL( SCIPsetIntParam(subscip, "limits/bestsol", heurdata->bestsollimit) );
2180
2181  /* forbid recursive call of heuristics and separators solving subMIPs */
2182  SCIP_CALL( SCIPsetSubscipsOff(subscip, TRUE) );
2183
2184  /* disable cutting plane separation */
2186
2187  /* disable expensive presolving */
2189
2190  /* use best estimate node selection */
2191  if( SCIPfindNodesel(subscip, "estimate") != NULL && !SCIPisParamFixed(subscip, "nodeselection/estimate/stdpriority") )
2192  {
2193  SCIP_CALL( SCIPsetIntParam(subscip, "nodeselection/estimate/stdpriority", INT_MAX/4) );
2194  }
2195
2196  /* use inference branching */
2197  if( SCIPfindBranchrule(subscip, "inference") != NULL && !SCIPisParamFixed(subscip, "branching/inference/priority") )
2198  {
2199  SCIP_CALL( SCIPsetIntParam(subscip, "branching/inference/priority", INT_MAX/4) );
2200  }
2201
2202  /* enable conflict analysis, disable analysis of boundexceeding LPs, and restrict conflict pool */
2203  if( !SCIPisParamFixed(subscip, "conflict/enable") )
2204  {
2205  SCIP_CALL( SCIPsetBoolParam(subscip, "conflict/enable", TRUE) );
2206  }
2207  if( !SCIPisParamFixed(subscip, "conflict/useboundlp") )
2208  {
2209  SCIP_CALL( SCIPsetCharParam(subscip, "conflict/useboundlp", 'o') );
2210  }
2211  if( !SCIPisParamFixed(subscip, "conflict/maxstoresize") )
2212  {
2213  SCIP_CALL( SCIPsetIntParam(subscip, "conflict/maxstoresize", 100) );
2214  }
2215
2216  /* speed up sub-SCIP by not checking dual LP feasibility */
2217  SCIP_CALL( SCIPsetBoolParam(subscip, "lp/checkdualfeas", FALSE) );
2218
2219  /* employ a limit on the number of enforcement rounds in the quadratic constraint handlers; this fixes the issue that
2220  * sometimes the quadratic constraint handler needs hundreds or thousands of enforcement rounds to determine the
2221  * feasibility status of a single node without fractional branching candidates by separation (namely for uflquad
2222  * instances); however, the solution status of the sub-SCIP might get corrupted by this; hence no decutions shall be
2223  * made for the original SCIP
2224  */
2226  {
2227  SCIP_CALL( SCIPsetIntParam(subscip, "constraints/quadratic/enfolplimit", 10) );
2228  }
2229
2230  /* add an objective cutoff */
2231  assert( !SCIPisInfinity(scip, SCIPgetUpperbound(scip)) );
2232
2233  upperbound = SCIPgetUpperbound(scip) - SCIPsumepsilon(scip);
2234  if( !SCIPisInfinity(scip, -1.0 * SCIPgetLowerbound(scip)) )
2235  {
2236  cutoff = (1 - heurdata->minimprove) * SCIPgetUpperbound(scip)
2237  + heurdata->minimprove * SCIPgetLowerbound(scip);
2238  }
2239  else
2240  {
2241  if( SCIPgetUpperbound(scip) >= 0 )
2242  cutoff = (1 - heurdata->minimprove) * SCIPgetUpperbound(scip);
2243  else
2244  cutoff = (1 + heurdata->minimprove) * SCIPgetUpperbound(scip);
2245  }
2246  cutoff = MIN(upperbound, cutoff);
2247  SCIP_CALL(SCIPsetObjlimit(subscip, cutoff));
2248
2249  /* set solve limits for sub-SCIP */
2250  SCIP_CALL( setLimits(scip, subscip, solvelimits) );
2251
2252  return SCIP_OKAY;
2253 }
2254
2255 /** determine limits for a sub-SCIP */
2256 static
2258  SCIP* scip, /**< SCIP data structure */
2259  SCIP_HEUR* heur, /**< this heuristic */
2260  SOLVELIMITS* solvelimits, /**< pointer to solving limits data structure */
2261  SCIP_Bool* runagain /**< can we solve another sub-SCIP with these limits */
2262  )
2263 {
2264  SCIP_HEURDATA* heurdata;
2265  SCIP_Real maxnnodesr;
2266  SCIP_Real confidence;
2267  SCIP_Longint maxnnodes;
2268  SCIP_Bool copylimits;
2269
2270  assert(scip != NULL);
2271  assert(heur != NULL);
2272  assert(solvelimits != NULL);
2273  assert(runagain != NULL);
2274
2275  heurdata = SCIPheurGetData(heur);
2276
2277  /* check whether there is enough time and memory left */
2278  SCIP_CALL( SCIPcheckCopyLimits(scip, &copylimits) );
2279
2280  if( ! copylimits )
2281  *runagain = FALSE;
2282
2283  /* calculate the maximal number of branching nodes until heuristic is aborted */
2284  maxnnodesr = heurdata->nodesquot * SCIPgetNNodes(scip);
2285
2286  /* reward gins if it succeeded often, count the setup costs for the sub-MIP as 100 nodes */
2287  confidence = (SCIP_Real)SCIPheurGetNCalls(heur);
2288  confidence = confidence / (confidence + 5.0);
2289  maxnnodesr *= 1.0 + confidence * 2.0 * (SCIPheurGetNBestSolsFound(heur)+1.0)/(heurdata->nsubmips + 1.0);
2290  maxnnodes = (SCIP_Longint)(maxnnodesr - 100.0 * heurdata->nsubmips);
2291  maxnnodes += heurdata->nodesofs;
2292
2293  /* determine the node limit for the current process */
2294  solvelimits->nodelimit = maxnnodes - heurdata->usednodes;
2295  solvelimits->nodelimit = MIN(solvelimits->nodelimit, heurdata->maxnodes);
2296
2297  /* check whether we have enough nodes left to call subproblem solving */
2298  if( solvelimits->nodelimit < heurdata->targetnodes )
2299  *runagain = FALSE;
2300
2301  solvelimits->stallnodelimit = heurdata->targetnodes;
2302
2303  return SCIP_OKAY;
2304 }
2305
2306 /** updates heurdata after a run of GINS */
2307 static
2309  SCIP* scip, /**< original SCIP data structure */
2310  SCIP_HEURDATA* heurdata /**< primal heuristic data */
2311  )
2312 {
2313  /* increase number of failures, calculate next node at which GINS should be called and update actual solutions */
2314  heurdata->nfailures++;
2315  heurdata->nextnodenumber = (heurdata->nfailures <= 25
2316  ? SCIPgetNNodes(scip) + 100*(2LL << heurdata->nfailures) /*lint !e703*/
2317  : SCIP_LONGINT_MAX);
2318 }
2319
2320 #ifdef SCIP_STATISTIC
2321 /** gets the average neighborhood size of all selected variables */
2322 static
2323 SCIP_Real heurdataAvgNeighborhoodSize(
2324  SCIP_HEURDATA* heurdata /**< heuristic data */
2325  )
2326 {
2327  return heurdata->sumneighborhoodvars / (MAX(1.0, (SCIP_Real)heurdata->nneighborhoods));
2328 }
2329
2330 /** prints a histogram */
2331 static
2332 void printHistogram(
2333  SCIP* scip, /**< SCIP data structure */
2334  int* histogram, /**< histogram values */
2335  const char* name /**< display name of this histogram */
2336  )
2337 {
2338  int i;
2339
2340  SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL, "Gins: %s", name);
2341
2342  /* write out entries of this histogram */
2343  for( i = 0; i < NHISTOGRAMBINS; ++i )
2344  SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL, " %d", histogram[i]);
2346 }
2347 #endif
2348
2349 /*
2350  * Callback methods of primal heuristic
2351  */
2352
2353 /** copy method for primal heuristic plugins (called when SCIP copies plugins) */
2354 static
2355 SCIP_DECL_HEURCOPY(heurCopyGins)
2356 { /*lint --e{715}*/
2357  assert(scip != NULL);
2358  assert(heur != NULL);
2359  assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0);
2361  /* call inclusion method of primal heuristic */
2362  SCIP_CALL( SCIPincludeHeurGins(scip) );
2363
2364  return SCIP_OKAY;
2365 }
2366
2367 /** destructor of primal heuristic to free user data (called when SCIP is exiting) */
2368 static
2369 SCIP_DECL_HEURFREE(heurFreeGins)
2370 { /*lint --e{715}*/
2371  SCIP_HEURDATA* heurdata;
2372
2373  assert(heur != NULL);
2374  assert(scip != NULL);
2375
2376  /* get heuristic data */
2377  heurdata = SCIPheurGetData(heur);
2378  assert(heurdata != NULL);
2379
2380  /* free heuristic data */
2381  SCIPfreeBlockMemory(scip, &heurdata);
2382  SCIPheurSetData(heur, NULL);
2383
2384  return SCIP_OKAY;
2385 }
2386
2387 /** initialization method of primal heuristic (called after problem was transformed) */
2388 static
2389 SCIP_DECL_HEURINIT(heurInitGins)
2390 { /*lint --e{715}*/
2391  SCIP_HEURDATA* heurdata;
2392
2393  assert(heur != NULL);
2394  assert(scip != NULL);
2395
2396  /* get heuristic's data */
2397  heurdata = SCIPheurGetData(heur);
2398  assert(heurdata != NULL);
2399  assert(heurdata->randnumgen == NULL);
2400
2401  /* initialize data */
2402  heurdata->usednodes = 0;
2403  SCIP_CALL( SCIPcreateRandom(scip, &heurdata->randnumgen, DEFAULT_RANDSEED, TRUE) );
2404  heurdata->sumdiscneighborhoodvars = heurdata->sumneighborhoodvars = 0;
2405  heurdata->nneighborhoods = 0;
2406  heurdata->maxseendistance = 0;
2407  heurdata->nsubmips = 0;
2408  heurdata->nfailures = 0;
2409  heurdata->nextnodenumber = 0;
2410  heurdata->lastinitsol = NULL;
2411  heurdata->allblocksunsuitable = FALSE;
2412  heurdata->taboolist = NULL;
2413  heurdata->targetnodes = heurdata->minnodes;
2414
2415 #ifdef SCIP_STATISTIC
2416  resetHistogram(heurdata->conscontvarshist);
2417  resetHistogram(heurdata->consdiscvarshist);
2418  resetHistogram(heurdata->conscontvarshist);
2419 #endif
2420
2421  return SCIP_OKAY;
2422 }
2423
2424 /** solving process deinitialization method of primal heuristic (called before branch and bound process data is freed) */
2425 static
2426 SCIP_DECL_HEUREXITSOL(heurExitsolGins)
2427 { /*lint --e{715}*/
2428  SCIP_HEURDATA* heurdata;
2429
2430  assert(heur != NULL);
2431  assert(scip != NULL);
2432
2433  /* get heuristic data */
2434  heurdata = SCIPheurGetData(heur);
2435  assert(heurdata != NULL);
2436
2437  /* it is likely that the decomposition information changes between runs, we recreate the decomposition horizon */
2438  decompHorizonFree(scip, &heurdata->decomphorizon);
2439  assert(heurdata->decomphorizon == NULL);
2440
2441  return SCIP_OKAY;
2442 }
2443
2444 /** initialization method of primal heuristic (called after problem was transformed) */
2445 static
2446 SCIP_DECL_HEUREXIT(heurExitGins)
2447 { /*lint --e{715}*/
2448  SCIP_HEURDATA* heurdata;
2449
2450  assert(heur != NULL);
2451  assert(scip != NULL);
2452
2453  /* get heuristic's data */
2454  heurdata = SCIPheurGetData(heur);
2455  assert(heurdata != NULL);
2456
2457  SCIPstatistic(
2458  SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL, "Gins: Avg Neighborhood size: %.1f Avg. discrete neighboorhood vars: %.1f\n",
2459  heurdataAvgNeighborhoodSize(heurdata), heurdataAvgDiscreteNeighborhoodSize(heurdata));
2460  SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL, "Gins: Max seen distance %d\n", heurdata->maxseendistance);
2461  printHistogram(scip, heurdata->consvarshist, "Constraint density histogram");
2462  printHistogram(scip, heurdata->conscontvarshist, "Constraint continuous density histogram");
2463  printHistogram(scip, heurdata->consdiscvarshist, "Constraint discrete density histogram");
2464  )
2465
2466  /* free some data structures that must be reset for a new problem */
2467  freeTabooList(scip, &heurdata->taboolist);
2468  SCIPfreeRandom(scip, &heurdata->randnumgen);
2469
2470  heurdata->taboolist = NULL;
2471  heurdata->randnumgen = NULL;
2472
2473  return SCIP_OKAY;
2474 }
2475
2476 /** execution method of primal heuristic */
2477 static
2478 SCIP_DECL_HEUREXEC(heurExecGins)
2479 { /*lint --e{715}*/
2480  SCIP_HEURDATA* heurdata; /* heuristic's data */
2481  SCIP* subscip; /* the subproblem created by gins */
2482  SCIP_VAR** vars; /* original problem's variables */
2483  SCIP_VAR** subvars; /* subproblem's variables */
2484  SCIP_VAR** fixedvars;
2485  SCIP_Real* fixedvals;
2486  ROLLINGHORIZON* rollinghorizon; /* data structure for rolling horizon approach */
2487  DECOMPHORIZON* decomphorizon; /* data structure for processing multiple blocks of a decomposition */
2488  SCIP_DECOMP* decomp;
2489  SCIP_HASHMAP* varmapfw; /* mapping of SCIP variables to sub-SCIP variables */
2490
2491  int nvars; /* number of original problem's variables */
2492  int i;
2493  int nfixedvars;
2494  SOLVELIMITS solvelimits;
2495  SCIP_Bool runagain;
2496
2497  SCIP_Bool success;
2498
2499  assert(heur != NULL);
2500  assert(scip != NULL);
2501  assert(result != NULL);
2502
2503  /* get heuristic's data */
2504  heurdata = SCIPheurGetData(heur);
2505  assert(heurdata != NULL);
2506
2507  *result = SCIP_DELAYED;
2508
2509  /* only call heuristic, if feasible solution is available */
2510  if( SCIPgetNSols(scip) <= 0 )
2511  return SCIP_OKAY;
2512
2513  /* in case of many unsuccessful calls, the nextnodenumber is increased to prevent us from running too often */
2514  if( SCIPgetNNodes(scip) < heurdata->nextnodenumber )
2515  return SCIP_OKAY;
2516
2517  /* only call heuristic, if the best solution comes from transformed problem */
2518  assert(SCIPgetBestSol(scip) != NULL);
2519  if( SCIPsolIsOriginal(SCIPgetBestSol(scip)) )
2520  return SCIP_OKAY;
2521
2522  /* only call heuristic, if enough nodes were processed since last incumbent */
2523  if( SCIPgetNNodes(scip) - SCIPgetSolNodenum(scip,SCIPgetBestSol(scip)) < heurdata->nwaitingnodes )
2524  return SCIP_OKAY;
2525
2526  *result = SCIP_DIDNOTRUN;
2527
2528  /* only call heuristic, if discrete variables are present */
2529  if( SCIPgetNBinVars(scip) == 0 && SCIPgetNIntVars(scip) == 0 )
2530  return SCIP_OKAY;
2531
2532  if( SCIPisStopped(scip) )
2533  return SCIP_OKAY;
2534
2535  runagain = TRUE;
2536
2537  /* determine solving limits for the sub-SCIP for the first time */
2538  SCIP_CALL( determineLimits(scip, heur, &solvelimits, &runagain) );
2539
2540  if( ! runagain )
2541  return SCIP_OKAY;
2542
2543  *result = SCIP_DIDNOTFIND;
2544
2545  SCIP_CALL( SCIPgetVarsData(scip, &vars, &nvars, NULL, NULL, NULL, NULL) );
2546  SCIP_CALL( SCIPallocBufferArray(scip, &fixedvars, nvars) );
2547  SCIP_CALL( SCIPallocBufferArray(scip, &fixedvals, nvars) );
2548
2549  rollinghorizon = NULL;
2550  decomp = chooseDecomp(scip);
2551  if( decomp != NULL && heurdata->usedecomp && heurdata->decomphorizon == NULL )
2552  {
2553  SCIP_CALL( decompHorizonCreate(scip, &heurdata->decomphorizon, decomp) );
2554  }
2555  decomphorizon = heurdata->decomphorizon;
2556  /* only create a rolling horizon data structure if we need it */
2557  if( decomphorizon == NULL && heurdata->userollinghorizon )
2558  {
2559  SCIP_CALL( rollingHorizonCreate(scip, &rollinghorizon) );
2560  }
2561
2562  do
2563  {
2564  SCIP_SOL* oldincumbent;
2565  SCIP_SOL* newincumbent;
2566
2567  /* create a new problem, by fixing all variables except for a small neighborhood */
2568  SCIP_CALL( determineVariableFixings(scip, fixedvars, fixedvals, &nfixedvars, heurdata, rollinghorizon, decomphorizon, &success) );
2569
2570  /* terminate if it was not possible to create the subproblem */
2571  if( !success )
2572  {
2573  SCIPdebugMsg(scip, "Could not create the subproblem -> skip call\n");
2574
2575  /* do not count this as a call to the heuristic */
2576  *result = SCIP_DIDNOTRUN;
2577
2578  /* count this as a failure and increase the number of waiting nodes until the next call */
2579  updateFailureStatistic(scip, heurdata);
2580  goto TERMINATE;
2581  }
2582
2583  /* initializing the subproblem */
2584  SCIP_CALL( SCIPallocBufferArray(scip, &subvars, nvars) );
2585  SCIP_CALL( SCIPcreate(&subscip) );
2586  ++heurdata->nsubmips;
2587
2588  /* create the variable mapping hash map */
2589  SCIP_CALL( SCIPhashmapCreate(&varmapfw, SCIPblkmem(subscip), nvars) );
2590
2591  /* create a problem copy as sub SCIP */
2592  SCIP_CALL( SCIPcopyLargeNeighborhoodSearch(scip, subscip, varmapfw, "gins", fixedvars, fixedvals, nfixedvars,
2593  heurdata->uselprows, heurdata->copycuts, &success, NULL) );
2594
2595  for( i = 0; i < nvars; i++ )
2596  subvars[i] = (SCIP_VAR*) SCIPhashmapGetImage(varmapfw, vars[i]);
2597
2598  /* free hash map */
2599  SCIPhashmapFree(&varmapfw);
2600
2601  /* set up limits for the subproblem */
2602  SCIP_CALL( setupSubScip(scip, subscip, &solvelimits, heur) );
2603
2604  /* solve the subproblem */
2605  SCIPdebugMsg(scip, "Solve Gins subMIP\n");
2606
2607  /* Errors in solving the subproblem should not kill the overall solving process
2608  * Hence, the return code is caught and a warning is printed, only in debug mode, SCIP will stop.
2609  */
2610  SCIP_CALL_ABORT( SCIPsolve(subscip) );
2611
2612  SCIPdebugMsg(scip, "GINS subscip stats: %.2f sec., %" SCIP_LONGINT_FORMAT " nodes, status:%d\n",
2613  SCIPgetSolvingTime(subscip), SCIPgetNTotalNodes(subscip), SCIPgetStatus(subscip));
2614
2615  /* increase target nodes if a (stall) node limit was reached; this will immediately affect the next run */
2617  {
2618  heurdata->targetnodes = (SCIP_Longint)(1.05 * heurdata->targetnodes) + 5L;
2619
2620  /* but not too far */
2621  heurdata->targetnodes = MIN(heurdata->targetnodes, heurdata->maxnodes / 2);
2622
2623  SCIPdebugMsg(scip, "New target nodes after stalling: %" SCIP_LONGINT_FORMAT "\n", heurdata->targetnodes);
2624  }
2625
2626  /* transfer variable statistics from sub-SCIP */
2627  SCIP_CALL( SCIPmergeVariableStatistics(subscip, scip, subvars, vars, nvars) );
2628
2629  heurdata->usednodes += SCIPgetNNodes(subscip);
2630
2631  success = FALSE;
2632  /* check, whether a solution was found;
2633  * due to numerics, it might happen that not all solutions are feasible -> try all solutions until one was accepted
2634  */
2635  oldincumbent = SCIPgetBestSol(scip);
2636
2637  SCIP_CALL( SCIPtranslateSubSols(scip, subscip, heur, subvars, &success, NULL) );
2638  if( success )
2639  *result = SCIP_FOUNDSOL;
2640
2641  newincumbent = SCIPgetBestSol(scip);
2642
2643  /* free subproblem */
2644  SCIPfreeBufferArray(scip, &subvars);
2645  SCIP_CALL( SCIPfree(&subscip) );
2646
2647  /* check if we want to run another rolling horizon iteration */
2648  runagain = success && (newincumbent != oldincumbent) && heurdata->userollinghorizon;
2649  if( runagain )
2650  {
2651  assert(rollinghorizon != NULL || decomphorizon != NULL);
2652  SCIP_CALL( determineLimits(scip, heur, &solvelimits, &runagain ) );
2653
2654  if( rollinghorizon != NULL )
2655  runagain = runagain && rollingHorizonRunAgain(scip, rollinghorizon, heurdata) && (success);
2656  else if( decomphorizon != NULL )
2657  runagain = runagain && decompHorizonRunAgain(scip, decomphorizon);
2658  }
2659  }
2660  while( runagain );
2661
2662  /* delay the heuristic in case it was not successful */
2663  if( *result != SCIP_FOUNDSOL )
2664  updateFailureStatistic(scip, heurdata);
2665
2666 TERMINATE:
2667
2668  /* only free the rolling horizon data structure if we need to keep it */
2669  if( heurdata->userollinghorizon )
2670  {
2671  rollingHorizonFree(scip, &rollinghorizon);
2672  }
2673
2674  SCIPfreeBufferArray(scip, &fixedvals);
2675  SCIPfreeBufferArray(scip, &fixedvars);
2676
2677  return SCIP_OKAY;
2678 }
2679
2680 /*
2681  * primal heuristic specific interface methods
2682  */
2683
2684 /** creates the gins primal heuristic and includes it in SCIP */
2686  SCIP* scip /**< SCIP data structure */
2687  )
2688 {
2689  SCIP_HEURDATA* heurdata;
2690  SCIP_HEUR* heur;
2691
2692  /* create Gins primal heuristic data */
2693  SCIP_CALL( SCIPallocBlockMemory(scip, &heurdata) );
2694  heurdata->randnumgen = NULL;
2695  heurdata->decomphorizon = NULL;
2696
2697  /* include primal heuristic */
2698  SCIP_CALL( SCIPincludeHeurBasic(scip, &heur,
2700  HEUR_MAXDEPTH, HEUR_TIMING, HEUR_USESSUBSCIP, heurExecGins, heurdata) );
2701
2702  assert(heur != NULL);
2703
2704  /* set non-NULL pointers to callback methods */
2705  SCIP_CALL( SCIPsetHeurCopy(scip, heur, heurCopyGins) );
2706  SCIP_CALL( SCIPsetHeurFree(scip, heur, heurFreeGins) );
2707  SCIP_CALL( SCIPsetHeurInit(scip, heur, heurInitGins) );
2708  SCIP_CALL( SCIPsetHeurExit(scip, heur, heurExitGins) );
2709  SCIP_CALL( SCIPsetHeurExitsol(scip, heur, heurExitsolGins) );
2710
2711  /* add gins primal heuristic parameters */
2712  SCIP_CALL( SCIPaddIntParam(scip, "heuristics/" HEUR_NAME "/nodesofs",
2713  "number of nodes added to the contingent of the total nodes",
2714  &heurdata->nodesofs, FALSE, DEFAULT_NODESOFS, 0, INT_MAX, NULL, NULL) );
2715
2716  SCIP_CALL( SCIPaddIntParam(scip, "heuristics/" HEUR_NAME "/maxnodes",
2717  "maximum number of nodes to regard in the subproblem",
2718  &heurdata->maxnodes, TRUE, DEFAULT_MAXNODES, 0, INT_MAX, NULL, NULL) );
2719
2720  SCIP_CALL( SCIPaddIntParam(scip, "heuristics/" HEUR_NAME "/minnodes",
2721  "minimum number of nodes required to start the subproblem",
2722  &heurdata->minnodes, TRUE, DEFAULT_MINNODES, 0, INT_MAX, NULL, NULL) );
2723
2724  SCIP_CALL( SCIPaddIntParam(scip, "heuristics/" HEUR_NAME "/nwaitingnodes",
2725  "number of nodes without incumbent change that heuristic should wait",
2726  &heurdata->nwaitingnodes, TRUE, DEFAULT_NWAITINGNODES, 0, INT_MAX, NULL, NULL) );
2727
2728  SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/nodesquot",
2729  "contingent of sub problem nodes in relation to the number of nodes of the original problem",
2730  &heurdata->nodesquot, FALSE, DEFAULT_NODESQUOT, 0.0, 1.0, NULL, NULL) );
2731
2732  SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/minfixingrate",
2733  "percentage of integer variables that have to be fixed",
2734  &heurdata->minfixingrate, FALSE, DEFAULT_MINFIXINGRATE, SCIPsumepsilon(scip), 1.0-SCIPsumepsilon(scip), NULL, NULL) );
2735
2736  SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/minimprove",
2737  "factor by which " HEUR_NAME " should at least improve the incumbent",
2738  &heurdata->minimprove, TRUE, DEFAULT_MINIMPROVE, 0.0, 1.0, NULL, NULL) );
2739
2740  SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/uselprows",
2741  "should subproblem be created out of the rows in the LP rows?",
2742  &heurdata->uselprows, TRUE, DEFAULT_USELPROWS, NULL, NULL) );
2743
2744  SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/copycuts",
2745  "if uselprows == FALSE, should all active cuts from cutpool be copied to constraints in subproblem?",
2746  &heurdata->copycuts, TRUE, DEFAULT_COPYCUTS, NULL, NULL) );
2747
2748  SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/fixcontvars",
2749  "should continuous variables outside the neighborhoods be fixed?",
2750  &heurdata->fixcontvars, TRUE, DEFAULT_FIXCONTVARS, NULL, NULL) );
2751
2752  SCIP_CALL( SCIPaddIntParam(scip, "heuristics/" HEUR_NAME "/bestsollimit",
2753  "limit on number of improving incumbent solutions in sub-CIP",
2754  &heurdata->bestsollimit, FALSE, DEFAULT_BESTSOLLIMIT, -1, INT_MAX, NULL, NULL) );
2755
2756  SCIP_CALL( SCIPaddIntParam(scip, "heuristics/" HEUR_NAME "/maxdistance",
2757  "maximum distance to selected variable to enter the subproblem, or -1 to select the distance "
2758  "that best approximates the minimum fixing rate from below",
2759  &heurdata->maxdistance, FALSE, DEFAULT_MAXDISTANCE, -1, INT_MAX, NULL, NULL) );
2760
2761  SCIP_CALL( SCIPaddCharParam(scip, "heuristics/" HEUR_NAME "/potential",
2762  "the reference point to compute the neighborhood potential: (r)oot, (l)ocal lp, or (p)seudo solution",
2763  &heurdata->potential, TRUE, DEFAULT_POTENTIAL, "lpr", NULL, NULL) );
2764
2765  SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/userollinghorizon",
2766  "should the heuristic solve a sequence of sub-MIP's around the first selected variable",
2767  &heurdata->userollinghorizon, TRUE, DEFAULT_USEROLLINGHORIZON, NULL, NULL) );
2768
2769  SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/relaxdenseconss",
2770  "should dense constraints (at least as dense as 1 - minfixingrate) be ignored by connectivity graph?",
2771  &heurdata->relaxdenseconss, TRUE, DEFAULT_RELAXDENSECONSS, NULL, NULL) );
2772
2773  SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/rollhorizonlimfac",
2774  "limiting percentage for variables already used in sub-SCIPs to terminate rolling horizon approach",
2775  &heurdata->rollhorizonlimfac, TRUE, DEFAULT_ROLLHORIZONLIMFAC, 0.0, 1.0, NULL, NULL) );
2776
2777  SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/overlap",
2778  "overlap of blocks between runs - 0.0: no overlap, 1.0: shift by only 1 block",
2779  &heurdata->overlap, TRUE, DEFAULT_OVERLAP, 0.0, 1.0, NULL, NULL) );
2780
2781  SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/usedecomp",
2782  "should user decompositions be considered, if available?",
2783  &heurdata->usedecomp, TRUE, DEFAULT_USEDECOMP, NULL, NULL) );
2784
2785  SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/usedecomprollhorizon",
2786  "should user decompositions be considered for initial selection in rolling horizon, if available?",
2787  &heurdata->usedecomprollhorizon, TRUE, DEFAULT_USEDECOMPROLLHORIZON, NULL, NULL) );
2788
2789  SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/useselfallback",
2790  "should random initial variable selection be used if decomposition was not successful?",
2791  &heurdata->useselfallback, TRUE, DEFAULT_USESELFALLBACK, NULL, NULL) );
2792
2793  SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/consecutiveblocks",
2794  "should blocks be treated consecutively (sorted by ascending label?)",
2795  &heurdata->consecutiveblocks, TRUE, DEFAULT_CONSECUTIVEBLOCKS, NULL, NULL) );
2796
2797  return SCIP_OKAY;
2798 }
static SCIP_Real heurdataAvgDiscreteNeighborhoodSize(SCIP_HEURDATA *heurdata)
Definition: heur_gins.c:1305
#define SCIPfreeBlockMemoryArray(scip, ptr, num)
Definition: scip_mem.h:97
static SCIP_RETCODE tabooListAdd(SCIP *scip, TABOOLIST *taboolist, int elem)
Definition: heur_gins.c:1006
int ntaboolabels
Definition: heur_gins.c:172
static SCIP_RETCODE rollingHorizonCreate(SCIP *scip, ROLLINGHORIZON **rollinghorizon)
Definition: heur_gins.c:932
SCIP_Bool * suitable
Definition: heur_gins.c:155
SCIP_Longint SCIPheurGetNCalls(SCIP_HEUR *heur)
Definition: heur.c:1555
#define SCIPreallocBlockMemoryArray(scip, ptr, oldnum, newnum)
Definition: scip_mem.h:86
int SCIPgetNContVars(SCIP *scip)
Definition: scip_prob.c:2166
SCIP_Bool SCIPisPositive(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisStopped(SCIP *scip)
Definition: scip_general.c:687
SCIP_Real SCIPsumepsilon(SCIP *scip)
int * sortedlabels
Definition: heur_gins.c:170
#define SCIPallocBlockMemoryArray(scip, ptr, num)
Definition: scip_mem.h:80
SCIP_CONSHDLR * SCIPfindConshdlr(SCIP *scip, const char *name)
Definition: scip_cons.c:877
const char * SCIPheurGetName(SCIP_HEUR *heur)
Definition: heur.c:1429
public methods for SCIP parameter handling
void SCIPfreeRandom(SCIP *scip, SCIP_RANDNUMGEN **randnumgen)
static SCIP_DECL_HEURCOPY(heurCopyGins)
Definition: heur_gins.c:2360
static SCIP_Bool decompHorizonNext(SCIP *scip, DECOMPHORIZON *decomphorizon, SCIP_HEURDATA *heurdata, int maxblocksize, int *blockintervalstart, int *blockintervalend, int *nextblocklabel, SCIP_Bool *fixlinkvars)
Definition: heur_gins.c:820
public methods for node selector plugins
SCIP_RETCODE SCIPsetHeurExitsol(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEUREXITSOL((*heurexitsol)))
Definition: scip_heur.c:233
public methods for memory management
#define DEFAULT_MAXDISTANCE
Definition: heur_gins.c:98
SCIP_HEURDATA * SCIPheurGetData(SCIP_HEUR *heur)
Definition: heur.c:1340
SCIP_STATUS SCIPgetStatus(SCIP *scip)
Definition: scip_general.c:467
#define HEUR_FREQ
Definition: heur_gins.c:76
#define DEFAULT_NODESOFS
Definition: heur_gins.c:82
static void freeTabooList(SCIP *scip, TABOOLIST **taboolist)
Definition: heur_gins.c:988
SCIP_EXPORT SCIP_Bool SCIPsolIsOriginal(SCIP_SOL *sol)
Definition: sol.c:2521
#define SCIPallocClearBlockMemoryArray(scip, ptr, num)
Definition: scip_mem.h:84
SCIP_Real * potential
Definition: heur_gins.c:149
#define DEFAULT_USEDECOMP
Definition: heur_gins.c:109
SCIP_Real SCIPgetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var)
Definition: scip_sol.c:1353
static SCIP_RETCODE createTabooList(SCIP *scip, TABOOLIST **taboolist, int initialsize)
Definition: heur_gins.c:967
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:1741
SCIP_RETCODE SCIPtranslateSubSols(SCIP *scip, SCIP *subscip, SCIP_HEUR *heur, SCIP_VAR **subvars, SCIP_Bool *success, int *solindex)
Definition: scip_copy.c:1396
SCIP_RETCODE SCIPvariableGraphCreate(SCIP *scip, SCIP_VGRAPH **vargraph, SCIP_Bool relaxdenseconss, SCIP_Real relaxdensity, int *nrelaxedconstraints)
Definition: heur.c:1967
SCIP_RETCODE SCIPvariablegraphBreadthFirst(SCIP *scip, SCIP_VGRAPH *vargraph, SCIP_VAR **startvars, int nstartvars, int *distances, int maxdistance, int maxvars, int maxbinintvars)
Definition: heur.c:1666
int SCIPgetNVars(SCIP *scip)
Definition: scip_prob.c:1986
SCIP_Real SCIPgetSolvingTime(SCIP *scip)
Definition: scip_timing.c:360
void SCIPverbMessage(SCIP *scip, SCIP_VERBLEVEL msgverblevel, FILE *file, const char *formatstr,...)
Definition: scip_message.c:216
#define FALSE
Definition: def.h:73
int * blocklabels
Definition: heur_gins.c:150
SCIP_EXPORT SCIP_Real SCIPvarGetObj(SCIP_VAR *var)
Definition: var.c:17510
SCIP_EXPORT SCIP_VARTYPE SCIPvarGetType(SCIP_VAR *var)
Definition: var.c:17177
#define TRUE
Definition: def.h:72
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:54
methods commonly used by primal heuristics
#define DEFAULT_MAXNODES
Definition: heur_gins.c:83
static void decompHorizonSetOverlapInterval(DECOMPHORIZON *decomphorizon, int leftborder, int rightborder)
Definition: heur_gins.c:377
#define DEFAULT_MINFIXINGRATE
Definition: heur_gins.c:86
SCIP_RETCODE SCIPsolve(SCIP *scip)
Definition: scip_solve.c:2527
void * SCIPhashmapGetImage(SCIP_HASHMAP *hashmap, void *origin)
Definition: misc.c:3200
struct SCIP_HeurData SCIP_HEURDATA
Definition: type_heur.h:67
int SCIPgetNImplVars(SCIP *scip)
Definition: scip_prob.c:2121
SCIP_EXPORT SCIP_Bool SCIPvarIsActive(SCIP_VAR *var)
Definition: var.c:17335
public methods for problem variables
#define HEUR_DISPCHAR
Definition: heur_gins.c:74
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:48
#define SCIPfreeBlockMemory(scip, ptr)
Definition: scip_mem.h:95
SCIP_DECOMP * decomp
Definition: heur_gins.c:146
static SCIP_Bool decompHorizonRunAgain(SCIP *scip, DECOMPHORIZON *decomphorizon)
Definition: heur_gins.c:471
SCIP_RETCODE SCIPsetSubscipsOff(SCIP *scip, SCIP_Bool quiet)
Definition: scip_param.c:893
#define SCIPduplicateBufferArray(scip, ptr, source, num)
Definition: scip_mem.h:119
SCIP_Real SCIPgetUpperbound(SCIP *scip)
int * varblockend
Definition: heur_gins.c:151
static SCIP_RETCODE determineVariableFixingsDecomp(SCIP *scip, DECOMPHORIZON *decomphorizon, SCIP_VAR **fixedvars, SCIP_Real *fixedvals, int *nfixings, SCIP_HEURDATA *heurdata, SCIP_Bool *success)
Definition: heur_gins.c:1872
#define SCIP_LONGINT_MAX
Definition: def.h:149
static SCIP_RETCODE determineVariableFixings(SCIP *scip, SCIP_VAR **fixedvars, SCIP_Real *fixedvals, int *nfixings, SCIP_HEURDATA *heurdata, ROLLINGHORIZON *rollinghorizon, DECOMPHORIZON *decomphorizon, SCIP_Bool *success)
Definition: heur_gins.c:2001
SCIP_Bool SCIPdecompIsOriginal(SCIP_DECOMP *decomp)
Definition: dcmp.c:236
#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:1249
static SCIP_RETCODE selectInitialVariableDecomposition(SCIP *scip, SCIP_HEURDATA *heurdata, SCIP_DECOMP *decomp, SCIP_VGRAPH *vargraph, int *distances, SCIP_VAR **selvar, int *selvarmaxdistance)
Definition: heur_gins.c:1338
SCIP_RETCODE SCIPsetHeurInit(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURINIT((*heurinit)))
Definition: scip_heur.c:185
#define SCIPdebugMsg
Definition: scip_message.h:69
int nsuitableblocks
Definition: heur_gins.c:156
#define DEFAULT_ROLLHORIZONLIMFAC
Definition: heur_gins.c:106
SCIP_EXPORT void SCIPsortInt(int *intarray, int len)
SCIP_RETCODE SCIPcheckCopyLimits(SCIP *sourcescip, SCIP_Bool *success)
Definition: scip_copy.c:3192
SCIP_Longint SCIPheurGetNBestSolsFound(SCIP_HEUR *heur)
Definition: heur.c:1575
int lastmaxdistance
Definition: heur_gins.c:131
SCIP_Bool SCIPisInfinity(SCIP *scip, SCIP_Real val)
static SCIP_DECOMP * chooseDecomp(SCIP *scip)
Definition: heur_gins.c:1978
int SCIPgetNIntVars(SCIP *scip)
Definition: scip_prob.c:2076
public methods for numerical tolerances
static void decompHorizonFree(SCIP *scip, DECOMPHORIZON **decomphorizon)
Definition: heur_gins.c:438
SCIP_RETCODE SCIPcreateRandom(SCIP *scip, SCIP_RANDNUMGEN **randnumgen, unsigned int initialseed, SCIP_Bool useglobalseed)
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:916
SCIP_RETCODE SCIPsetObjlimit(SCIP *scip, SCIP_Real objlimit)
Definition: scip_prob.c:1420
public methods for querying solving statistics
int SCIPgetNSols(SCIP *scip)
Definition: scip_sol.c:2206
SCIP_EXPORT SCIP_Real SCIPvarGetRootSol(SCIP_VAR *var)
Definition: var.c:13114
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:613
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:108
public methods for decompositions
SCIP_Longint SCIPgetNNodes(SCIP *scip)
#define SCIPduplicateBlockMemoryArray(scip, ptr, source, num)
Definition: scip_mem.h:92
SCIP_RETCODE SCIPcreate(SCIP **scip)
Definition: scip_general.c:283
int memsize
Definition: heur_gins.c:171
SCIP_EXPORT const char * SCIPvarGetName(SCIP_VAR *var)
Definition: var.c:17012
static void rollingHorizonStoreDistances(ROLLINGHORIZON *rollinghorizon, int *distances)
Definition: heur_gins.c:1125
#define HEUR_NAME
Definition: heur_gins.c:72
#define DEFAULT_FIXCONTVARS
Definition: heur_gins.c:96
SCIP_EXPORT SCIP_Bool SCIPvarIsIntegral(SCIP_VAR *var)
Definition: var.c:17203
#define DEFAULT_USEROLLINGHORIZON
Definition: heur_gins.c:105
#define SCIPerrorMessage
Definition: pub_message.h:55
#define DEFAULT_USEDECOMPROLLHORIZON
Definition: heur_gins.c:110
SCIP_Longint SCIPgetNTotalNodes(SCIP *scip)
SCIP_BRANCHRULE * SCIPfindBranchrule(SCIP *scip, const char *name)
Definition: scip_branch.c:288
#define DEFAULT_CONSECUTIVEBLOCKS
Definition: heur_gins.c:113
SCIP_VAR ** SCIPgetVars(SCIP *scip)
Definition: scip_prob.c:1941
static void updateFailureStatistic(SCIP *scip, SCIP_HEURDATA *heurdata)
Definition: heur_gins.c:2313
SCIP_VGRAPH * variablegraph
Definition: heur_gins.c:126
static int decompHorizonGetFirstPosBestPotential(SCIP *scip, DECOMPHORIZON *decomphorizon, SCIP_HEURDATA *heurdata, int maxblocksize)
Definition: heur_gins.c:661
#define DEFAULT_OVERLAP
Definition: heur_gins.c:112
BMS_BLKMEM * SCIPblkmem(SCIP *scip)
Definition: scip_mem.c:48
SCIP_Bool SCIPisZero(SCIP *scip, SCIP_Real val)
int * taboolabels
Definition: heur_gins.c:169
static int countLabel(int *labels, int start, int nlabels)
Definition: heur_gins.c:1314
int lastblockpos
Definition: heur_gins.c:157
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:1350
#define NULL
Definition: lpi_spx1.cpp:155
static SCIP_RETCODE setupSubScip(SCIP *scip, SCIP *subscip, SOLVELIMITS *solvelimits, SCIP_HEUR *heur)
Definition: heur_gins.c:2162
#define DEFAULT_RELAXDENSECONSS
Definition: heur_gins.c:102
#define REALABS(x)
Definition: def.h:187
static int * tabooListGetLastK(TABOOLIST *taboolist, int k)
Definition: heur_gins.c:1061
SCIP_RETCODE SCIPmergeVariableStatistics(SCIP *sourcescip, SCIP *targetscip, SCIP_VAR **sourcevars, SCIP_VAR **targetvars, int nvars)
Definition: scip_copy.c:1251
void SCIPdecompGetVarsLabels(SCIP_DECOMP *decomp, SCIP_VAR **vars, int *labels, int nvars)
Definition: dcmp.c:139
public methods for problem copies
public methods for primal CIP solutions
SCIP_NODESEL * SCIPfindNodesel(SCIP *scip, const char *name)
Definition: scip_nodesel.c:225
#define SCIP_CALL(x)
Definition: def.h:364
#define HEUR_FREQOFS
Definition: heur_gins.c:77
#define DEFAULT_POTENTIAL
Definition: heur_gins.c:97
SCIP_RETCODE SCIPsetPresolving(SCIP *scip, SCIP_PARAMSETTING paramsetting, SCIP_Bool quiet)
Definition: scip_param.c:942
static SCIP_DECL_HEURFREE(heurFreeGins)
Definition: heur_gins.c:2374
#define DEFAULT_NODESQUOT
Definition: heur_gins.c:87
SCIP_RETCODE SCIPsetCharParam(SCIP *scip, const char *name, char value)
Definition: scip_param.c:671
SCIP_Longint nodelimit
Definition: heur_alns.c:462
static SCIP_RETCODE decompHorizonInitialize(SCIP *scip, DECOMPHORIZON *decomphorizon, SCIP_HEURDATA *heurdata)
Definition: heur_gins.c:553
static SCIP_DECL_HEUREXEC(heurExecGins)
Definition: heur_gins.c:2483
SCIP_Bool needssorting
Definition: heur_gins.c:173
public methods for primal heuristic plugins and divesets
public methods for constraint handler plugins and constraints
#define DEFAULT_BESTSOLLIMIT
Definition: heur_gins.c:95
void SCIPvariableGraphFree(SCIP *scip, SCIP_VGRAPH **vargraph)
Definition: heur.c:2005
SCIP_Longint SCIPgetSolNodenum(SCIP *scip, SCIP_SOL *sol)
Definition: scip_sol.c:1649
Definition: type_dcmp.h:35
static int taboolistgetNElems(TABOOLIST *taboolist)
Definition: heur_gins.c:1075
#define DEFAULT_MINNODES
Definition: heur_gins.c:85
#define SCIPallocBufferArray(scip, ptr, num)
Definition: scip_mem.h:111
int SCIPcalcMemGrowSize(SCIP *scip, int num)
Definition: scip_mem.c:130
#define DEFAULT_USELPROWS
Definition: heur_gins.c:89
public data structures and miscellaneous methods
int SCIPrandomGetInt(SCIP_RANDNUMGEN *randnumgen, int minrandval, int maxrandval)
Definition: misc.c:9945
static SCIP_Bool tabooListFind(TABOOLIST *taboolist, int elem)
Definition: heur_gins.c:1036
#define SCIP_Bool
Definition: def.h:70
int SCIPdecompGetNBlocks(SCIP_DECOMP *decomp)
Definition: dcmp.c:269
static SCIP_RETCODE decompHorizonCreate(SCIP *scip, DECOMPHORIZON **decomphorizon, SCIP_DECOMP *decomp)
Definition: heur_gins.c:392
SCIP_RETCODE SCIPhashmapCreate(SCIP_HASHMAP **hashmap, BMS_BLKMEM *blkmem, int mapsize)
Definition: misc.c:3013
SCIP_RETCODE SCIPsetHeurExit(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEUREXIT((*heurexit)))
Definition: scip_heur.c:201
static SCIP_DECL_SORTINDCOMP(sortIndCompDecompHorizon)
Definition: heur_gins.c:503
void SCIPgetDecomps(SCIP *scip, SCIP_DECOMP ***decomps, int *ndecomps, SCIP_Bool original)
Definition: scip_dcmp.c:253
SCIP_EXPORT SCIP_Real SCIPvarGetUbGlobal(SCIP_VAR *var)
Definition: var.c:17672
static SCIP_Bool checkFixingrate(SCIP *scip, SCIP_HEURDATA *heurdata, int nfixings)
Definition: heur_gins.c:274
#define DEFAULT_COPYCUTS
Definition: heur_gins.c:92
SCIP_RETCODE SCIPincludeHeurGins(SCIP *scip)
Definition: heur_gins.c:2690
SCIP_Bool SCIPisParamFixed(SCIP *scip, const char *name)
Definition: scip_param.c:210
#define MAX(x, y)
Definition: tclique_def.h:83
static SCIP_Bool rollingHorizonRunAgain(SCIP *scip, ROLLINGHORIZON *rollinghorizon, SCIP_HEURDATA *heurdata)
Definition: heur_gins.c:1108
static SCIP_Bool decompHorizonBlockUsedRecently(SCIP *scip, DECOMPHORIZON *decomphorizon, int blockpos)
Definition: heur_gins.c:800
SCIP_EXPORT int SCIPsolGetIndex(SCIP_SOL *sol)
Definition: sol.c:2635
#define BMScopyMemoryArray(ptr, source, num)
Definition: memory.h:126
#define HEUR_PRIORITY
Definition: heur_gins.c:75
SCIP_SOL ** lastsolblock
Definition: heur_gins.c:148
SCIP_RETCODE SCIPcopyLimits(SCIP *sourcescip, SCIP *targetscip)
Definition: scip_copy.c:3228
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:130
static SCIP_VAR ** decomphorizonGetVars(DECOMPHORIZON *decomphorizon)
Definition: heur_gins.c:920
#define DEFAULT_USESELFALLBACK
Definition: heur_gins.c:111
#define HEUR_TIMING
Definition: heur_gins.c:79
#define SCIP_REAL_MIN
Definition: def.h:165
static SCIP_DECL_HEURINIT(heurInitGins)
Definition: heur_gins.c:2394
SCIP_RETCODE SCIPsetLongintParam(SCIP *scip, const char *name, SCIP_Longint value)
Definition: scip_param.c:555
methods for sorting joint arrays of various types
static SCIP_RETCODE determineLimits(SCIP *scip, SCIP_HEUR *heur, SOLVELIMITS *solvelimits, SCIP_Bool *runagain)
Definition: heur_gins.c:2262
public methods for branching rule plugins and branching
SCIP_VAR ** b
Definition: circlepacking.c:56
general public methods
public methods for solutions
public methods for random numbers
static void rollingHorizonFree(SCIP *scip, ROLLINGHORIZON **rollinghorizon)
Definition: heur_gins.c:1084
#define DEFAULT_MINIMPROVE
Definition: heur_gins.c:84
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:1187
SCIP_EXPORT SCIP_Real SCIPvarGetLbGlobal(SCIP_VAR *var)
Definition: var.c:17662
SCIP_RETCODE SCIPsetHeurCopy(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURCOPY((*heurcopy)))
Definition: scip_heur.c:153
static SCIP_Bool decompHorizonIsInitialized(DECOMPHORIZON *decomphorizon)
Definition: heur_gins.c:487
SCIP_EXPORT void SCIPsortInd(int *indarray, SCIP_DECL_SORTINDCOMP((*indcomp)), void *dataptr, int len)
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:1860
int * distances
Definition: heur_gins.c:127
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:74
void SCIPhashmapFree(SCIP_HASHMAP **hashmap)
Definition: misc.c:3047
#define SCIPstatistic(x)
Definition: pub_message.h:111
#define SCIP_Real
Definition: def.h:163
static void decompHorizonMarkInterval(SCIP *scip, DECOMPHORIZON *decomphorizon, SCIP_HEURDATA *heurdata, SCIP_SOL *sol, int blockstartpos, int blockendpos)
Definition: heur_gins.c:1818
static SCIP_Real getFixVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var)
Definition: heur_gins.c:1161
int * ndiscretevars
Definition: heur_gins.c:152
static SCIP_RETCODE setLimits(SCIP *sourcescip, SCIP *subscip, SOLVELIMITS *solvelimits)
Definition: heur_gins.c:2139
int overlapinterval[2]
Definition: heur_gins.c:161
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)
SCIP_Bool init
Definition: heur_gins.c:162
static SCIP_DECL_HEUREXIT(heurExitGins)
Definition: heur_gins.c:2451
#define SCIP_Longint
Definition: def.h:148
static SCIP_Real getPotential(SCIP *scip, SCIP_HEURDATA *heurdata, SCIP_SOL *sol, SCIP_VAR **vars, int nvars)
Definition: heur_gins.c:307
SCIP_RETCODE SCIPsetBoolParam(SCIP *scip, const char *name, SCIP_Bool value)
Definition: scip_param.c:439
int SCIPgetNBinVars(SCIP *scip)
Definition: scip_prob.c:2031
SCIP_RETCODE SCIPsetHeurFree(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURFREE((*heurfree)))
Definition: scip_heur.c:169
SCIP_EXPORT int SCIPvarGetProbindex(SCIP_VAR *var)
Definition: var.c:17355
#define HEUR_MAXDEPTH
Definition: heur_gins.c:78
int * blockindices
Definition: heur_gins.c:153
static void tabooListReset(TABOOLIST *taboolist)
Definition: heur_gins.c:957
#define SCIPfreeBlockMemoryArrayNull(scip, ptr, num)
Definition: scip_mem.h:98
#define BMSclearMemoryArray(ptr, num)
Definition: memory.h:122
public methods for primal heuristics
SCIP_RETCODE SCIPfree(SCIP **scip)
Definition: scip_general.c:315
#define DEFAULT_NWAITINGNODES
Definition: heur_gins.c:88
#define SCIP_CALL_ABORT(x)
Definition: def.h:343
public methods for decompositions
SCIP_Bool * used
Definition: heur_gins.c:129
SCIP_VAR ** vars
Definition: heur_gins.c:147
#define HEUR_DESC
Definition: heur_gins.c:73
public methods for global and local (sub)problems
static SCIP_Bool isVariableInNeighborhood(SCIP_VAR *var, int *distances, int maxdistance)
Definition: heur_gins.c:1145
#define HEUR_USESSUBSCIP
Definition: heur_gins.c:80
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:158
SCIP_SOL * SCIPgetBestSol(SCIP *scip)
Definition: scip_sol.c:2305
SCIP_Longint stallnodelimit
Definition: heur_gins.c:234
SCIP_RETCODE SCIPsetIntParam(SCIP *scip, const char *name, int value)
Definition: scip_param.c:497
static SCIP_DECL_HEUREXITSOL(heurExitsolGins)
Definition: heur_gins.c:2431
SCIP_RETCODE SCIPsetSeparating(SCIP *scip, SCIP_PARAMSETTING paramsetting, SCIP_Bool quiet)
Definition: scip_param.c:968
SCIP_EXPORT void SCIPsortIntPtr(int *intarray, void **ptrarray, int len)
#define DEFAULT_RANDSEED
Definition: heur_gins.c:101
static SCIP_RETCODE selectInitialVariableRandomly(SCIP *scip, SCIP_HEURDATA *heurdata, SCIP_VGRAPH *vargraph, int *distances, SCIP_VAR **selvar, int *selvarmaxdistance)
Definition: heur_gins.c:1551
memory allocation routines