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