Scippy

SCIP

Solving Constraint Integer Programs

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