1 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
2 /* */
3 /* This file is part of the program and library */
4 /* SCIP --- Solving Constraint Integer Programs */
5 /* */
6 /* Copyright (C) 2002-2021 Konrad-Zuse-Zentrum */
7 /* fuer Informationstechnik Berlin */
8 /* */
9 /* SCIP is distributed under the terms of the ZIB Academic License. */
10 /* */
11 /* You should have received a copy of the ZIB Academic License */
12 /* along with SCIP; see the file COPYING. If not email to scip@zib.de. */
13 /* */
14 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
15
16 /**@file heur_crossover.c
17 * @ingroup DEFPLUGINS_HEUR
18 * @brief crossover primal heuristic
19 * @author Timo Berthold
20 */
21
22 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
23
24 #include "blockmemshell/memory.h"
25 #include "scip/heur_crossover.h"
26 #include "scip/heuristics.h"
27 #include "scip/pub_event.h"
28 #include "scip/pub_heur.h"
29 #include "scip/pub_message.h"
30 #include "scip/pub_misc.h"
31 #include "scip/pub_sol.h"
32 #include "scip/pub_var.h"
33 #include "scip/scip_branch.h"
34 #include "scip/scip_cons.h"
35 #include "scip/scip_copy.h"
36 #include "scip/scip_event.h"
37 #include "scip/scip_general.h"
38 #include "scip/scip_heur.h"
39 #include "scip/scip_mem.h"
40 #include "scip/scip_message.h"
41 #include "scip/scip_nodesel.h"
42 #include "scip/scip_numerics.h"
43 #include "scip/scip_param.h"
44 #include "scip/scip_prob.h"
45 #include "scip/scip_randnumgen.h"
46 #include "scip/scip_sol.h"
47 #include "scip/scip_solve.h"
48 #include "scip/scip_solvingstats.h"
49 #include "scip/scip_tree.h"
50 #include "scip/scip_var.h"
51 #include <string.h>
52
53 #define HEUR_NAME "crossover"
54 #define HEUR_DESC "LNS heuristic that fixes all variables that are identic in a couple of solutions"
55 #define HEUR_DISPCHAR SCIP_HEURDISPCHAR_LNS
56 #define HEUR_PRIORITY -1104000
57 #define HEUR_FREQ 30
58 #define HEUR_FREQOFS 0
59 #define HEUR_MAXDEPTH -1
60 #define HEUR_TIMING SCIP_HEURTIMING_AFTERNODE
61 #define HEUR_USESSUBSCIP TRUE /**< does the heuristic use a secondary SCIP instance? */
62
63 #define DEFAULT_MAXNODES 5000LL /* maximum number of nodes to regard in the subproblem */
64 #define DEFAULT_MINIMPROVE 0.01 /* factor by which Crossover should at least improve the incumbent */
65 #define DEFAULT_MINNODES 50LL /* minimum number of nodes to regard in the subproblem */
66 #define DEFAULT_MINFIXINGRATE 0.666 /* minimum percentage of integer variables that have to be fixed */
67 #define DEFAULT_NODESOFS 500LL /* number of nodes added to the contingent of the total nodes */
68 #define DEFAULT_NODESQUOT 0.1 /* subproblem nodes in relation to nodes of the original problem */
69 #define DEFAULT_LPLIMFAC 2.0 /* factor by which the limit on the number of LP depends on the node limit */
70 #define DEFAULT_NUSEDSOLS 3 /* number of solutions that will be taken into account */
71 #define DEFAULT_NWAITINGNODES 200LL /* number of nodes without incumbent change heuristic should wait */
72 #define DEFAULT_RANDOMIZATION TRUE /* should the choice which sols to take be randomized? */
73 #define DEFAULT_DONTWAITATROOT FALSE /* should the nwaitingnodes parameter be ignored at the root node? */
74 #define DEFAULT_USELPROWS FALSE /* should subproblem be created out of the rows in the LP rows,
75 * otherwise, the copy constructors of the constraints handlers are used */
76 #define DEFAULT_COPYCUTS TRUE /* if DEFAULT_USELPROWS is FALSE, then should all active cuts from the
77 * cutpool of the original scip be copied to constraints of the subscip
78 */
79 #define DEFAULT_PERMUTE FALSE /* should the subproblem be permuted to increase diversification? */
80 #define HASHSIZE_SOLS 500 /* size of hash table for solution tuples in crossover heuristic */
81 #define DEFAULT_BESTSOLLIMIT -1 /* limit on number of improving incumbent solutions in sub-CIP */
82 #define DEFAULT_USEUCT FALSE /* should uct node selection be used at the beginning of the search? */
83 #define DEFAULT_RANDSEED 7 /* initial random seed */
84
85 /* event handler properties */
86 #define EVENTHDLR_NAME "Crossover"
87 #define EVENTHDLR_DESC "LP event handler for " HEUR_NAME " heuristic"
88
89 /*
90 * Data structures
91 */
92
93 typedef struct SolTuple SOLTUPLE;
94
95 /** primal heuristic data */
96 struct SCIP_HeurData
97 {
98 SCIP_SOL* prevlastsol; /**< worst solution taken into account during the previous run */
99 SCIP_SOL* prevbestsol; /**< best solution during the previous run */
100 int prevnsols; /**< number of all solutions during the previous run */
101
102 SCIP_Longint maxnodes; /**< maximum number of nodes to regard in the subproblem */
103 SCIP_Longint minnodes; /**< minimum number of nodes to regard in the subproblem */
104 SCIP_Longint nodesofs; /**< number of nodes added to the contingent of the total nodes */
105 SCIP_Longint usednodes; /**< nodes already used by crossover in earlier calls */
106 SCIP_Real nodesquot; /**< subproblem nodes in relation to nodes of the original problem */
107
108 int nusedsols; /**< number of solutions that will be taken into account */
109 SCIP_Longint nwaitingnodes; /**< number of nodes without incumbent change heuristic should wait */
110 unsigned int nfailures; /**< number of failures since last successful call */
111 SCIP_Longint nextnodenumber; /**< number of nodes at which crossover should be called the next time */
112 SCIP_Real minfixingrate; /**< minimum percentage of integer variables that have to be fixed */
113 SCIP_Real minimprove; /**< factor by which Crossover should at least improve the incumbent */
114 SCIP_Real nodelimit; /**< the nodelimit employed in the current sub-SCIP, for the event handler*/
115 SCIP_Real lplimfac; /**< factor by which the limit on the number of LP depends on the node limit */
116 SCIP_Bool randomization; /**< should the choice which sols to take be randomized? */
117 SCIP_Bool dontwaitatroot; /**< should the nwaitingnodes parameter be ignored at the root node? */
118 SCIP_RANDNUMGEN* randnumgen; /**< random number generator */
119 SCIP_HASHTABLE* hashtable; /**< hashtable used to store the solution tuples already used */
120 SOLTUPLE* lasttuple; /**< last tuple of solutions created by crossover */
121 SCIP_Bool uselprows; /**< should subproblem be created out of the rows in the LP rows? */
122 SCIP_Bool copycuts; /**< if uselprows == FALSE, should all active cuts from cutpool be copied
123 * to constraints in subproblem? */
124 SCIP_Bool permute; /**< should the subproblem be permuted to increase diversification? */
125 int bestsollimit; /**< limit on number of improving incumbent solutions in sub-CIP */
126 SCIP_Bool useuct; /**< should uct node selection be used at the beginning of the search? */
127 };
128
129 /** n-tuple of solutions and their hashkey */
130 struct SolTuple
131 {
132 int* indices; /**< sorted array of solution indices */
133 int size; /**< size of the array (should be heurdata->nusedsols) */
134 unsigned int key; /**< hashkey of the tuple */
135 SOLTUPLE* prev; /**< previous solution tuple created */
136 };
137
138
139 /*
140 * Local methods
141 */
142
143 /** gets the hash key of a solution tuple */
144 static
SCIP_DECL_HASHGETKEY(hashGetKeySols)145 SCIP_DECL_HASHGETKEY(hashGetKeySols)
146 { /*lint --e{715}*/
147 return elem;
148 }
149
150
151 /** returns TRUE iff both solution tuples are identical */
152 static
SCIP_DECL_HASHKEYEQ(hashKeyEqSols)153 SCIP_DECL_HASHKEYEQ(hashKeyEqSols)
154 { /*lint --e{715}*/
155 int i;
156 int size;
157
158 int* indices1;
159 int* indices2;
160
161 indices1 = ((SOLTUPLE*)key1)->indices;
162 indices2 = ((SOLTUPLE*)key2)->indices;
163
164 /* there should be two nonempty arrays of the same size */
165 assert(indices1 != NULL);
166 assert(indices2 != NULL);
167 assert(((SOLTUPLE*)key1)->size == ((SOLTUPLE*)key2)->size);
168
169 size = ((SOLTUPLE*)key1)->size;
170
171 /* compare arrays by components, return TRUE, iff equal */
172 for( i = 0; i < size; i++ )
173 {
174 if( indices1[i] != indices2[i] )
175 return FALSE;
176 }
177
178 return TRUE;
179 }
180
181
182 /** returns hashkey of a solution tuple */
183 static
SCIP_DECL_HASHKEYVAL(hashKeyValSols)184 SCIP_DECL_HASHKEYVAL(hashKeyValSols)
185 { /*lint --e{715}*/
186 return ((SOLTUPLE*)key)->key;
187 }
188
189
190 /** calculates a hash key for a given tuple of solution indices */
191 static
calculateHashKey(int * indices,int size)192 unsigned int calculateHashKey(
193 int* indices, /**< indices of solutions */
194 int size /**< number of solutions */
195 )
196 {
197 int i;
198 unsigned int hashkey;
199
200 /* hashkey should be (x1+1) * (x2+1) * ... * (xn+1) + x1 + x2 + ... + xn */
201 hashkey = 1;
202 for( i = 0; i < size; i++ )
203 hashkey *= (unsigned) indices[i] + 1;
204 for( i = 0; i < size; i++ )
205 hashkey += (unsigned) indices[i];
206
207 return hashkey;
208 }
209
210
211 /** insertion sort for a small int array */
sortArray(int * a,int size)212 static void sortArray(
213 int* a, /**< array to be sorted */
214 int size /**< size of array */
215 )
216 {
217 int i;
218 int j;
219 int tmp;
220
221 /* simple insertion sort algorithm */
222 for( i = 1; i < size; i++ )
223 {
224 tmp = a[i];
225 j = i-1;
226 while( j >= 0 && a[j] > tmp )
227 {
228 a[j+1] = a[j]; /*lint !e679*/
229 j = j-1;
230 }
231 a[j+1] = tmp; /*lint !e679*/
232 }
233 }
234
235
236 /** creates a new tuple of solutions */
237 static
createSolTuple(SCIP * scip,SOLTUPLE ** elem,int * indices,int size,SCIP_HEURDATA * heurdata)238 SCIP_RETCODE createSolTuple(
239 SCIP* scip, /**< original SCIP data structure */
240 SOLTUPLE** elem, /**< tuple of solutions which should be created */
241 int* indices, /**< indices of solutions */
242 int size, /**< number of solutions */
243 SCIP_HEURDATA* heurdata /**< primal heuristic data */
244 )
245 {
246 /* memory allocation */
247 SCIP_CALL( SCIPallocBlockMemory(scip, elem) );
248 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(*elem)->indices, size) );
249 BMScopyMemoryArray((*elem)->indices, indices, size);
250
251 /* data input */
252 sortArray(indices,size);
253 (*elem)->size = size;
254 (*elem)->key = calculateHashKey((*elem)->indices, (*elem)->size);
255 (*elem)->prev = heurdata->lasttuple;
256
257 /* update heurdata */
258 heurdata->lasttuple = *elem;
259 return SCIP_OKAY;
260 }
261
262
263 /** checks whether the new solution was found at the same node by the same heuristic as an already selected one */
264 static
solHasNewSource(SCIP_SOL ** sols,int * selection,int selectionsize,int newsol)265 SCIP_Bool solHasNewSource(
266 SCIP_SOL** sols, /**< feasible SCIP solutions */
267 int* selection, /**< pool of solutions crossover uses */
268 int selectionsize, /**< size of solution pool */
269 int newsol /**< candidate solution */
270 )
271 {
272 int i;
273
274 for( i = 0; i < selectionsize; i++ )
275 {
276 if( SCIPsolGetHeur(sols[selection[i]]) == SCIPsolGetHeur(sols[newsol])
277 && SCIPsolGetNodenum(sols[selection[i]]) == SCIPsolGetNodenum(sols[newsol]) )
278 return FALSE;
279 }
280
281 return TRUE;
282 }
283
284 /** randomly selects the solutions crossover will use from the pool of all solutions found so far */
285 static
selectSolsRandomized(SCIP * scip,int * selection,SCIP_HEURDATA * heurdata,SCIP_Bool * success)286 SCIP_RETCODE selectSolsRandomized(
287 SCIP* scip, /**< original SCIP data structure */
288 int* selection, /**< pool of solutions crossover uses */
289 SCIP_HEURDATA* heurdata, /**< primal heuristic data */
290 SCIP_Bool* success /**< pointer to store whether the process was successful */
291 )
292 {
293 int i;
294 int j;
295 int lastsol; /* the worst solution possible to choose */
296 int nusedsols; /* number of solutions which will be chosen */
297
298 SOLTUPLE* elem;
299 SCIP_SOL** sols;
300
301 assert( success != NULL );
302
303 /* initialization */
304 nusedsols = heurdata->nusedsols;
305 lastsol = SCIPgetNSols(scip);
306 sols = SCIPgetSols(scip);
307 assert(nusedsols < lastsol);
308
309 i = 0;
310 *success = FALSE;
311
312 /* perform at maximum 10 restarts and stop as soon as a new set of solutions is found */
313 while( !*success && i < 10 )
314 {
315 SCIP_Bool validtuple;
316
317 validtuple = TRUE;
318 for( j = 0; j < nusedsols && validtuple; j++ )
319 {
320 int k;
321 k = SCIPrandomGetInt(heurdata->randnumgen, nusedsols-j-1, lastsol-1);
322
323 /* ensure that the solution does not have a similar source as the others */
324 while( k >= nusedsols-j-1 && !solHasNewSource(sols, selection, j, k) )
325 k--;
326
327 validtuple = (k >= nusedsols-j-1);
328 selection[j] = k;
329 lastsol = k;
330 }
331
332 if( validtuple )
333 {
334 /* creates an object ready to be inserted into the hashtable */
335 SCIP_CALL( createSolTuple(scip, &elem, selection, nusedsols, heurdata) );
336
337 /* check whether the randomized set is already in the hashtable, if not, insert it */
338 if( !SCIPhashtableExists(heurdata->hashtable, elem) )
339 {
340 SCIP_CALL( SCIPhashtableInsert(heurdata->hashtable, elem) );
341 *success = TRUE;
342 }
343 }
344 i++;
345 }
346
347 return SCIP_OKAY;
348 }
349
350
351 /** determines the fixings for the CROSSOVER subproblem and checks whether enough fixings were found */
352 static
fixVariables(SCIP * scip,SCIP_VAR ** fixedvars,SCIP_Real * fixedvals,int * nfixedvars,int fixedvarssize,int * selection,SCIP_HEURDATA * heurdata,SCIP_Bool * success)353 SCIP_RETCODE fixVariables(
354 SCIP* scip, /**< original SCIP data structure */
355 SCIP_VAR** fixedvars, /**< array to store source SCIP variables whose copies should be fixed in the sub-SCIP */
356 SCIP_Real* fixedvals, /**< array to store solution values for variable fixing */
357 int* nfixedvars, /**< pointer to store the number of fixed variables */
358 int fixedvarssize, /**< size of the arrays to store fixing variables */
359 int* selection, /**< pool of solutions crossover will use */
360 SCIP_HEURDATA* heurdata, /**< primal heuristic data */
361 SCIP_Bool* success /**< pointer to store whether the problem was created successfully */
362 )
363 {
364 SCIP_VAR** vars; /* original scip variables */
365 SCIP_SOL** sols; /* pool of solutions */
366 SCIP_Real fixingrate; /* percentage of variables that are fixed */
367
368 int nvars;
369 int nbinvars;
370 int nintvars;
371
372 int i;
373 int j;
374
375 sols = SCIPgetSols(scip);
376 assert(sols != NULL);
377 assert(fixedvars != NULL);
378 assert(fixedvals != NULL);
379
380 /* get required data of the original problem */
381 SCIP_CALL( SCIPgetVarsData(scip, &vars, &nvars, &nbinvars, &nintvars, NULL, NULL) );
382 assert(fixedvarssize >= nbinvars + nintvars);
383
384 *nfixedvars = 0;
385
386 /* go through discrete variables and collect potential fixings */
387 for( i = 0; i < nbinvars + nintvars; i++ )
388 {
389 SCIP_Real solval;
390 SCIP_Bool fixable;
391
392 fixable = TRUE;
393 solval = SCIPgetSolVal(scip, sols[selection[0]], vars[i]);
394
395 /* check, whether variable's value is identical for each selected solution */
396 for( j = 1; j < heurdata->nusedsols; j++ )
397 {
398 SCIP_Real varsolval;
399 varsolval = SCIPgetSolVal(scip, sols[selection[j]], vars[i]);
400 if( REALABS(solval - varsolval) > 0.5 )
401 {
402 fixable = FALSE;
403 break;
404 }
405 }
406
407 /* original solval can be outside transformed global bounds */
408 fixable = fixable && SCIPvarGetLbGlobal(vars[i]) <= solval && solval <= SCIPvarGetUbGlobal(vars[i]);
409
410 /* if solutions' values are equal, variable should be fixed in the subproblem */
411 if( fixable )
412 {
413 fixedvars[(*nfixedvars)] = vars[i];
414 fixedvals[(*nfixedvars)] = solval;
415 (*nfixedvars)++;
416 }
417 }
418
419 fixingrate = (SCIP_Real)(*nfixedvars) / (SCIP_Real)(MAX(nbinvars + nintvars, 1));
420
421 /* if all variables would be fixed or amount of fixed variables is insufficient,
422 * skip subproblem creation and abort immediately
423 */
424 *success = (*nfixedvars) < nbinvars + nintvars && fixingrate >= heurdata->minfixingrate;
425
426 return SCIP_OKAY;
427 }
428
429 /** creates a subproblem for subscip by fixing a number of variables */
430 static
determineVariableFixings(SCIP * scip,SCIP_VAR ** fixedvars,SCIP_Real * fixedvals,int * nfixedvars,int fixedvarssize,int * selection,SCIP_HEURDATA * heurdata,SCIP_Bool * success)431 SCIP_RETCODE determineVariableFixings(
432 SCIP* scip, /**< original SCIP data structure */
433 SCIP_VAR** fixedvars, /**< array to store source SCIP variables whose copies should be fixed in the sub-SCIP */
434 SCIP_Real* fixedvals, /**< array to store solution values for variable fixing */
435 int* nfixedvars, /**< pointer to store the number of fixed variables */
436 int fixedvarssize, /**< size of the arrays to store fixing variables */
437 int* selection, /**< pool of solutions crossover will use */
438 SCIP_HEURDATA* heurdata, /**< primal heuristic data */
439 SCIP_Bool* success /**< pointer to store whether the problem was created successfully */
440 )
441 {
442 SCIP_SOL** sols; /* array of all solutions found so far */
443 int nsols; /* number of all solutions found so far */
444 int nusedsols; /* number of solutions to use in crossover */
445 int i;
446
447 /* get solutions' data */
448 nsols = SCIPgetNSols(scip);
449 sols = SCIPgetSols(scip);
450 nusedsols = heurdata->nusedsols;
451
452 assert(nusedsols > 1);
453 assert(nsols >= nusedsols);
454
455 /* use nusedsols best solutions if randomization is deactivated or there are only nusedsols solutions at hand
456 * or a good new solution was found since last call */
457 if( !heurdata->randomization || nsols == nusedsols || heurdata->prevlastsol != sols[nusedsols-1] )
458 {
459 SOLTUPLE* elem;
460 SCIP_HEUR* solheur;
461 SCIP_Longint solnodenum;
462 SCIP_Bool allsame;
463
464 for( i = 0; i < nusedsols; i++ )
465 selection[i] = i;
466 SCIP_CALL( createSolTuple(scip, &elem, selection, nusedsols, heurdata) );
467
468 solheur = SCIPsolGetHeur(sols[0]);
469 solnodenum = SCIPsolGetNodenum(sols[0]);
470 allsame = TRUE;
471
472 /* check, whether all solutions have been found by the same heuristic at the same node; in this case we do not run
473 * crossover, since it would probably just optimize over the same space as the other heuristic
474 */
475 for( i = 1; i < nusedsols; i++ )
476 {
477 if( SCIPsolGetHeur(sols[i]) != solheur || SCIPsolGetNodenum(sols[i]) != solnodenum )
478 allsame = FALSE;
479 }
480 *success = !allsame && !SCIPhashtableExists(heurdata->hashtable, elem);
481
482 /* check, whether solution tuple has already been tried */
483 if( !SCIPhashtableExists(heurdata->hashtable, elem) )
484 {
485 SCIP_CALL( SCIPhashtableInsert(heurdata->hashtable, elem) );
486 }
487
488 /* if solution tuple has already been tried, randomization is allowed and enough solutions are at hand, try
489 * to randomize another tuple. E.g., this can happen if the last crossover solution was among the best ones */
490 if( !(*success) && heurdata->randomization && nsols > nusedsols )
491 {
492 SCIP_CALL( selectSolsRandomized(scip, selection, heurdata, success) );
493 }
494 }
495 /* otherwise randomize the set of solutions */
496 else
497 {
498 SCIP_CALL( selectSolsRandomized(scip, selection, heurdata, success) );
499 }
500
501 /* no acceptable solution tuple could be created */
502 if( !(*success) )
503 return SCIP_OKAY;
504
505 /* set up the variables of the subproblem */
506 SCIP_CALL( fixVariables(scip, fixedvars, fixedvals, nfixedvars, fixedvarssize, selection, heurdata, success) );
507
508 return SCIP_OKAY;
509 }
510
511 /** updates heurdata after a run of crossover */
512 static
updateFailureStatistic(SCIP * scip,SCIP_HEURDATA * heurdata)513 void updateFailureStatistic(
514 SCIP* scip, /**< original SCIP data structure */
515 SCIP_HEURDATA* heurdata /**< primal heuristic data */
516 )
517 {
518 /* increase number of failures, calculate next node at which crossover should be called and update actual solutions */
519 heurdata->nfailures++;
520 heurdata->nextnodenumber = (heurdata->nfailures <= 25
521 ? SCIPgetNNodes(scip) + 100*(2LL << heurdata->nfailures) /*lint !e703*/
522 : SCIP_LONGINT_MAX);
523 }
524
525 /* ---------------- Callback methods of event handler ---------------- */
526
527 /* exec the event handler
528 *
529 * we interrupt the solution process
530 */
531 static
SCIP_DECL_EVENTEXEC(eventExecCrossover)532 SCIP_DECL_EVENTEXEC(eventExecCrossover)
533 {
534 SCIP_HEURDATA* heurdata;
535
536 assert(eventhdlr != NULL);
537 assert(eventdata != NULL);
538 assert(strcmp(SCIPeventhdlrGetName(eventhdlr), EVENTHDLR_NAME) == 0);
539 assert(event != NULL);
540 assert(SCIPeventGetType(event) & SCIP_EVENTTYPE_LPSOLVED);
541
542 heurdata = (SCIP_HEURDATA*)eventdata;
543 assert(heurdata != NULL);
544
545 /* interrupt solution process of sub-SCIP */
546 if( SCIPgetNLPs(scip) > heurdata->lplimfac * heurdata->nodelimit )
547 {
548 SCIPdebugMsg(scip, "interrupt after %" SCIP_LONGINT_FORMAT " LPs\n", SCIPgetNLPs(scip));
549 SCIP_CALL( SCIPinterruptSolve(scip) );
550 }
551
552 return SCIP_OKAY;
553 }
554
555 /*
556 * Callback methods of primal heuristic
557 */
558
559 /** copy method for primal heuristic plugins (called when SCIP copies plugins) */
560 static
SCIP_DECL_HEURCOPY(heurCopyCrossover)561 SCIP_DECL_HEURCOPY(heurCopyCrossover)
562 { /*lint --e{715}*/
563 assert(scip != NULL);
564 assert(heur != NULL);
565 assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0);
566
567 /* call inclusion method of primal heuristic */
568 SCIP_CALL( SCIPincludeHeurCrossover(scip) );
569
570 return SCIP_OKAY;
571 }
572
573 /** setup and solve the subproblem and catch the return code */
574 static
setupAndSolveSubscipCrossover(SCIP * scip,SCIP * subscip,SCIP_HEUR * heur,SCIP_HEURDATA * heurdata,SCIP_VAR ** vars,SCIP_VAR ** fixedvars,SCIP_Real * fixedvals,SCIP_Longint nstallnodes,SCIP_RESULT * result,int * selection,int nvars,int nfixedvars,int nusedsols)575 SCIP_RETCODE setupAndSolveSubscipCrossover(
576 SCIP* scip, /**< SCIP data structure */
577 SCIP* subscip, /**< sub-SCIP data structure */
578 SCIP_HEUR* heur, /**< mutation heuristic */
579 SCIP_HEURDATA* heurdata, /**< heuristics data */
580 SCIP_VAR** vars, /**< SCIP variables */
581 SCIP_VAR** fixedvars, /**< array to store the variables that should be fixed in the subproblem */
582 SCIP_Real* fixedvals, /**< array to store the fixing values to fix variables in the subproblem */
583 SCIP_Longint nstallnodes, /**< node limit for the subproblem */
584 SCIP_RESULT* result, /**< pointer to store the result */
585 int* selection, /**< pool of solutions crossover uses */
586 int nvars, /**< number of original problem's variables */
587 int nfixedvars, /**< the number of variables that should be fixed */
588 int nusedsols /**< number of solutions which will be chosen */
589 )
590 {
591 SCIP_EVENTHDLR* eventhdlr; /* event handler for LP events */
592 SCIP_HASHMAP* varmapfw; /* mapping of SCIP variables to sub-SCIP variables */
593 SCIP_VAR** subvars; /* subproblem's variables */
594 SCIP_Real cutoff; /* objective cutoff for the subproblem */
595 SCIP_Real upperbound;
596 SCIP_Bool success;
597 int i;
598
599 assert(scip != NULL);
600 assert(subscip != NULL);
601 assert(heur != NULL);
602 assert(heurdata != NULL);
603
604 /* create the variable mapping hash map */
605 SCIP_CALL( SCIPhashmapCreate(&varmapfw, SCIPblkmem(subscip), nvars) );
606 success = FALSE;
607
608 /* create a copy of the transformed problem to be used by the heuristic */
609 SCIP_CALL( SCIPcopyLargeNeighborhoodSearch(scip, subscip, varmapfw, "crossover", fixedvars, fixedvals, nfixedvars,
610 heurdata->uselprows, heurdata->copycuts, &success, NULL) );
611
612 eventhdlr = NULL;
613 /* create event handler for LP events */
614 SCIP_CALL( SCIPincludeEventhdlrBasic(subscip, &eventhdlr, EVENTHDLR_NAME, EVENTHDLR_DESC, eventExecCrossover, NULL) );
615 if( eventhdlr == NULL )
616 {
617 SCIPerrorMessage("event handler for " HEUR_NAME " heuristic not found.\n");
618 return SCIP_PLUGINNOTFOUND;
619 }
620
621 /* store copied variables in the order in which they appear in the main SCIP */
622 SCIP_CALL( SCIPallocBufferArray(scip, &subvars, nvars) );
623 for( i = 0; i < nvars; i++ )
624 subvars[i] = (SCIP_VAR*) SCIPhashmapGetImage(varmapfw, vars[i]);
625
626 /* free hash map */
627 SCIPhashmapFree(&varmapfw);
628
629 /* do not abort subproblem on CTRL-C */
630 SCIP_CALL( SCIPsetBoolParam(subscip, "misc/catchctrlc", FALSE) );
631
632 #ifdef SCIP_DEBUG
633 /* for debugging, enable full output */
634 SCIP_CALL( SCIPsetIntParam(subscip, "display/verblevel", 5) );
635 SCIP_CALL( SCIPsetIntParam(subscip, "display/freq", 100000000) );
636 #else
637 /* disable statistic timing inside sub SCIP and output to console */
638 SCIP_CALL( SCIPsetIntParam(subscip, "display/verblevel", 0) );
639 SCIP_CALL( SCIPsetBoolParam(subscip, "timing/statistictiming", FALSE) );
640 #endif
641
642 /* check whether there is enough time and memory left */
643 SCIP_CALL( SCIPsetIntParam(subscip, "limits/bestsol", heurdata->bestsollimit) );
644
645 /* set limits for the subproblem */
646 SCIP_CALL( SCIPcopyLimits(scip, subscip) );
647 heurdata->nodelimit = nstallnodes;
648 SCIP_CALL( SCIPsetLongintParam(subscip, "limits/nodes", nstallnodes) );
649
650 /* forbid recursive call of heuristics and separators solving subMIPs */
651 SCIP_CALL( SCIPsetSubscipsOff(subscip, TRUE) );
652
653 /* disable cutting plane separation */
654 SCIP_CALL( SCIPsetSeparating(subscip, SCIP_PARAMSETTING_OFF, TRUE) );
655
656 /* disable expensive presolving */
657 SCIP_CALL( SCIPsetPresolving(subscip, SCIP_PARAMSETTING_FAST, TRUE) );
658
659 /* use best estimate node selection */
660 if( SCIPfindNodesel(subscip, "estimate") != NULL && !SCIPisParamFixed(subscip, "nodeselection/estimate/stdpriority") )
661 {
662 SCIP_CALL( SCIPsetIntParam(subscip, "nodeselection/estimate/stdpriority", INT_MAX/4) );
663 }
664
665 /* activate uct node selection at the top of the tree */
666 if( heurdata->useuct && SCIPfindNodesel(subscip, "uct") != NULL && !SCIPisParamFixed(subscip, "nodeselection/uct/stdpriority") )
667 {
668 SCIP_CALL( SCIPsetIntParam(subscip, "nodeselection/uct/stdpriority", INT_MAX/2) );
669 }
670
671 /* use inference branching */
672 if( SCIPfindBranchrule(subscip, "inference") != NULL && !SCIPisParamFixed(subscip, "branching/inference/priority") )
673 {
674 SCIP_CALL( SCIPsetIntParam(subscip, "branching/inference/priority", INT_MAX/4) );
675 }
676
677 /* enable conflict analysis, disable analysis of boundexceeding LPs, and restrict conflict pool */
678 if( !SCIPisParamFixed(subscip, "conflict/enable") )
679 {
680 SCIP_CALL( SCIPsetBoolParam(subscip, "conflict/enable", TRUE) );
681 }
682 if( !SCIPisParamFixed(subscip, "conflict/useboundlp") )
683 {
684 SCIP_CALL( SCIPsetCharParam(subscip, "conflict/useboundlp", 'o') );
685 }
686 if( !SCIPisParamFixed(subscip, "conflict/maxstoresize") )
687 {
688 SCIP_CALL( SCIPsetIntParam(subscip, "conflict/maxstoresize", 100) );
689 }
690
691 /* speed up sub-SCIP by not checking dual LP feasibility */
692 SCIP_CALL( SCIPsetBoolParam(subscip, "lp/checkdualfeas", FALSE) );
693
694 /* employ a limit on the number of enforcement rounds in the quadratic constraint handler; this fixes the issue that
695 * sometimes the quadratic constraint handler needs hundreds or thousands of enforcement rounds to determine the
696 * feasibility status of a single node without fractional branching candidates by separation (namely for uflquad
697 * instances); however, the solution status of the sub-SCIP might get corrupted by this; hence no deductions shall be
698 * made for the original SCIP
699 */
700 if( SCIPfindConshdlr(subscip, "quadratic") != NULL && !SCIPisParamFixed(subscip, "constraints/quadratic/enfolplimit") )
701 {
702 SCIP_CALL( SCIPsetIntParam(subscip, "constraints/quadratic/enfolplimit", 500) );
703 }
704
705 /* add an objective cutoff */
706 assert(!SCIPisInfinity(scip, SCIPgetUpperbound(scip)));
707
708 upperbound = SCIPgetUpperbound(scip) - SCIPsumepsilon(scip);
709 if( !SCIPisInfinity(scip,-1.0*SCIPgetLowerbound(scip)) )
710 {
711 cutoff = (1-heurdata->minimprove)*SCIPgetUpperbound(scip) + heurdata->minimprove*SCIPgetLowerbound(scip);
712 }
713 else
714 {
715 if( SCIPgetUpperbound ( scip ) >= 0 )
716 cutoff = ( 1 - heurdata->minimprove ) * SCIPgetUpperbound ( scip );
717 else
718 cutoff = ( 1 + heurdata->minimprove ) * SCIPgetUpperbound ( scip );
719 }
720 cutoff = MIN(upperbound, cutoff );
721 SCIP_CALL( SCIPsetObjlimit(subscip, cutoff) );
722
723 /* permute the subproblem to increase diversification */
724 if( heurdata->permute )
725 {
726 SCIP_CALL( SCIPpermuteProb(subscip, SCIPinitializeRandomSeed(scip, (unsigned) SCIPheurGetNCalls(heur)), TRUE, TRUE, TRUE, TRUE, TRUE) );
727 }
728
729 /* catch LP events of sub-SCIP */
730 SCIP_CALL( SCIPtransformProb(subscip) );
731 SCIP_CALL( SCIPcatchEvent(subscip, SCIP_EVENTTYPE_LPSOLVED, eventhdlr, (SCIP_EVENTDATA*) heurdata, NULL) );
732
733 /* this code can be enabled whenever the subproblem should be written out */
734 #ifdef SCIP_DISABLED_CODE
735 SCIPdebug( SCIP_CALL( SCIPwriteOrigProblem(subscip, "crossoverprob.cip", "cip", FALSE) ) );
736 #endif
737 /* solve the subproblem */
738 SCIPdebugMsg(scip, "Solve Crossover subMIP\n");
739
740 /* Errors in solving the subproblem should not kill the overall solving process.
741 * Hence, the return code is caught and a warning is printed, only in debug mode, SCIP will stop. */
742 SCIP_CALL_ABORT( SCIPsolve(subscip) );
743
744 /* drop LP events of sub-SCIP */
745 SCIP_CALL( SCIPdropEvent(subscip, SCIP_EVENTTYPE_LPSOLVED, eventhdlr, (SCIP_EVENTDATA*) heurdata, -1) );
746
747 /* print solving statistics of subproblem if we are in SCIP's debug mode */
748 SCIPdebug( SCIP_CALL( SCIPprintStatistics(subscip, NULL) ) );
749
750 heurdata->usednodes += SCIPgetNNodes(subscip);
751
752 /* merge histories of the subscip-variables to the SCIP variables. */
753 SCIP_CALL( SCIPmergeVariableStatistics(subscip, scip, subvars, vars, nvars) );
754 SCIPdebugMsg(scip, "Transferring variable histories complete\n");
755
756 /* check, whether a solution was found */
757 if( SCIPgetNSols(subscip) > 0 )
758 {
759 int solindex; /* index of the solution created by crossover */
760
761 /* check, whether a solution was found;
762 * due to numerics, it might happen that not all solutions are feasible -> try all solutions until one was accepted */
763 success = FALSE;
764 solindex = -1;
765 SCIP_CALL( SCIPtranslateSubSols(scip, subscip, heur, subvars, &success, &solindex) );
766
767 if( success )
768 {
769 int tmp;
770
771 assert(solindex != -1);
772
773 *result = SCIP_FOUNDSOL;
774
775 /* insert all crossings of the new solution and (nusedsols-1) of its parents into the hashtable
776 * in order to avoid incest ;)
777 */
778 for( i = 0; i < nusedsols; i++ )
779 {
780 SOLTUPLE* elem;
781 tmp = selection[i];
782 selection[i] = solindex;
783
784 SCIP_CALL( createSolTuple(scip, &elem, selection, nusedsols, heurdata) );
785 SCIP_CALL( SCIPhashtableInsert(heurdata->hashtable, elem) );
786 selection[i] = tmp;
787 }
788
789 /* if solution was among the best ones, crossover should not be called until another good solution was found */
790 if( !heurdata->randomization )
791 {
792 heurdata->prevbestsol = SCIPgetBestSol(scip);
793 heurdata->prevlastsol = SCIPgetSols(scip)[heurdata->nusedsols-1];
794 }
795 }
796
797 /* if solution is not better than incumbent or could not be added to problem => run is counted as a failure */
798 if( !success || solindex != SCIPsolGetIndex(SCIPgetBestSol(scip)) )
799 updateFailureStatistic(scip, heurdata);
800 }
801 else
802 {
803 /* if no new solution was found, run was a failure */
804 updateFailureStatistic(scip, heurdata);
805 }
806
807 SCIPfreeBufferArray(scip, &subvars);
808
809 return SCIP_OKAY;
810 }
811
812 /** destructor of primal heuristic to free user data (called when SCIP is exiting) */
813 static
SCIP_DECL_HEURFREE(heurFreeCrossover)814 SCIP_DECL_HEURFREE(heurFreeCrossover)
815 { /*lint --e{715}*/
816 SCIP_HEURDATA* heurdata;
817
818 assert(heur != NULL);
819 assert(scip != NULL);
820
821 /* get heuristic data */
822 heurdata = SCIPheurGetData(heur);
823 assert(heurdata != NULL);
824
825 /* free heuristic data */
826 SCIPfreeBlockMemory(scip, &heurdata);
827 SCIPheurSetData(heur, NULL);
828
829 return SCIP_OKAY;
830 }
831
832 /** initialization method of primal heuristic (called after problem was transformed) */
833 static
SCIP_DECL_HEURINIT(heurInitCrossover)834 SCIP_DECL_HEURINIT(heurInitCrossover)
835 { /*lint --e{715}*/
836 SCIP_HEURDATA* heurdata;
837
838 assert(heur != NULL);
839 assert(scip != NULL);
840
841 /* get heuristic's data */
842 heurdata = SCIPheurGetData(heur);
843 assert(heurdata != NULL);
844
845 /* initialize data */
846 heurdata->usednodes = 0;
847 heurdata->prevlastsol = NULL;
848 heurdata->prevbestsol = NULL;
849 heurdata->lasttuple = NULL;
850 heurdata->nfailures = 0;
851 heurdata->prevnsols = 0;
852 heurdata->nextnodenumber = 0;
853
854 /* create random number generator */
855 SCIP_CALL( SCIPcreateRandom(scip, &heurdata->randnumgen, DEFAULT_RANDSEED, TRUE) );
856
857 /* initialize hash table */
858 SCIP_CALL( SCIPhashtableCreate(&heurdata->hashtable, SCIPblkmem(scip), HASHSIZE_SOLS,
859 hashGetKeySols, hashKeyEqSols, hashKeyValSols, NULL) );
860 assert(heurdata->hashtable != NULL);
861
862 return SCIP_OKAY;
863 }
864
865 /** deinitialization method of primal heuristic (called before transformed problem is freed) */
866 static
SCIP_DECL_HEUREXIT(heurExitCrossover)867 SCIP_DECL_HEUREXIT(heurExitCrossover)
868 { /*lint --e{715}*/
869 SCIP_HEURDATA* heurdata;
870 SOLTUPLE* soltuple;
871
872 assert(heur != NULL);
873 assert(scip != NULL);
874
875 /* get heuristic data */
876 heurdata = SCIPheurGetData(heur);
877 assert(heurdata != NULL);
878 soltuple = heurdata->lasttuple;
879
880 /* free all soltuples iteratively */
881 while( soltuple != NULL )
882 {
883 SOLTUPLE* tmp;
884 tmp = soltuple->prev;
885 SCIPfreeBlockMemoryArray(scip, &soltuple->indices, soltuple->size);
886 SCIPfreeBlockMemory(scip, &soltuple);
887 soltuple = tmp;
888 }
889
890 /* free random number generator */
891 SCIPfreeRandom(scip, &heurdata->randnumgen);
892
893 /* free hash table */
894 assert(heurdata->hashtable != NULL);
895 SCIPhashtableFree(&heurdata->hashtable);
896
897 return SCIP_OKAY;
898 }
899
900 /** execution method of primal heuristic */
901 static
SCIP_DECL_HEUREXEC(heurExecCrossover)902 SCIP_DECL_HEUREXEC(heurExecCrossover)
903 { /*lint --e{715}*/
904 SCIP* subscip; /* the subproblem created by crossover */
905 SCIP_HEURDATA* heurdata; /* primal heuristic data */
906 SCIP_VAR** vars; /* original problem's variables */
907 SCIP_VAR** fixedvars;
908 SCIP_SOL** sols;
909 SCIP_RETCODE retcode;
910 SCIP_Longint nstallnodes; /* node limit for the subproblem */
911 SCIP_Bool success;
912 SCIP_Real* fixedvals;
913 int* selection; /* pool of solutions crossover uses */
914 int nvars; /* number of original problem's variables */
915 int nbinvars;
916 int nintvars;
917 int nusedsols;
918 int nfixedvars;
919
920 assert(heur != NULL);
921 assert(scip != NULL);
922 assert(result != NULL);
923
924 /* get heuristic's data */
925 heurdata = SCIPheurGetData(heur);
926 assert(heurdata != NULL);
927 nusedsols = heurdata->nusedsols;
928
929 *result = SCIP_DELAYED;
930
931 /* only call heuristic, if enough solutions are at hand */
932 if( SCIPgetNSols(scip) < nusedsols )
933 return SCIP_OKAY;
934
935 sols = SCIPgetSols(scip);
936 assert(sols != NULL);
937
938 /* if one good solution was found, heuristic should not be delayed any longer */
939 if( sols[nusedsols-1] != heurdata->prevlastsol )
940 {
941 heurdata->nextnodenumber = SCIPgetNNodes(scip);
942 if( sols[0] != heurdata->prevbestsol )
943 heurdata->nfailures = 0;
944 }
945 /* in nonrandomized mode: only recall heuristic, if at least one new good solution was found in the meantime */
946 else if( !heurdata->randomization )
947 return SCIP_OKAY;
948
949 /* if heuristic should be delayed, wait until certain number of nodes is reached */
950 if( SCIPgetNNodes(scip) < heurdata->nextnodenumber )
951 return SCIP_OKAY;
952
953 /* only call heuristic, if enough nodes were processed since last incumbent */
954 if( SCIPgetNNodes(scip) - SCIPgetSolNodenum(scip, SCIPgetBestSol(scip)) < heurdata->nwaitingnodes
955 && (SCIPgetDepth(scip) > 0 || !heurdata->dontwaitatroot) )
956 return SCIP_OKAY;
957
958 *result = SCIP_DIDNOTRUN;
959
960 /* calculate the maximal number of branching nodes until heuristic is aborted */
961 nstallnodes = (SCIP_Longint)(heurdata->nodesquot * SCIPgetNNodes(scip));
962
963 /* reward Crossover if it succeeded often */
964 nstallnodes = (SCIP_Longint)
965 (nstallnodes * (1.0 + 2.0*(SCIPheurGetNBestSolsFound(heur)+1.0)/(SCIPheurGetNCalls(heur)+1.0)));
966
967 /* count the setup costs for the sub-MIP as 100 nodes */
968 nstallnodes -= 100 * SCIPheurGetNCalls(heur);
969 nstallnodes += heurdata->nodesofs;
970
971 /* determine the node limit for the current process */
972 nstallnodes -= heurdata->usednodes;
973 nstallnodes = MIN(nstallnodes, heurdata->maxnodes);
974
975 /* check whether we have enough nodes left to call subproblem solving */
976 if( nstallnodes < heurdata->minnodes )
977 return SCIP_OKAY;
978
979 /* consider time and memory limits of the main SCIP */
980 SCIP_CALL( SCIPcheckCopyLimits(scip, &success) );
981
982 if( !success )
983 return SCIP_OKAY;
984
985 if( SCIPisStopped(scip) )
986 return SCIP_OKAY;
987
988 /* get variable information */
989 SCIP_CALL( SCIPgetVarsData(scip, &vars, &nvars, &nbinvars, &nintvars, NULL, NULL) );
990 assert(nvars > 0);
991
992 /* check whether discrete variables are available */
993 if( nbinvars == 0 && nintvars == 0 )
994 return SCIP_OKAY;
995
996 /* allocate necessary buffer storage for selection of variable fixings */
997 SCIP_CALL( SCIPallocBufferArray(scip, &selection, nusedsols) );
998 SCIP_CALL( SCIPallocBufferArray(scip, &fixedvars, nbinvars + nintvars) );
999 SCIP_CALL( SCIPallocBufferArray(scip, &fixedvals, nbinvars + nintvars) );
1000
1001 success = FALSE;
1002 nfixedvars = 0;
1003 /* determine fixings of variables with same value in a certain set of solutions */
1004 SCIP_CALL( determineVariableFixings(scip, fixedvars, fixedvals, &nfixedvars, nbinvars + nintvars, selection, heurdata, &success) );
1005
1006 heurdata->prevbestsol = SCIPgetBestSol(scip);
1007 heurdata->prevlastsol = sols[heurdata->nusedsols-1];
1008
1009 /* if creation of sub-SCIP was aborted (e.g. due to number of fixings), free sub-SCIP and abort */
1010 if( !success )
1011 {
1012 /* this run will be counted as a failure since no new solution tuple could be generated or the neighborhood of the
1013 * solution was not fruitful in the sense that it was too big
1014 */
1015 updateFailureStatistic(scip, heurdata);
1016
1017 goto TERMINATE;
1018 }
1019
1020 *result = SCIP_DIDNOTFIND;
1021 /* initializing the subproblem */
1022 SCIP_CALL( SCIPcreate(&subscip) );
1023
1024 /* setup and solve the subproblem and catch the return code */
1025 retcode = setupAndSolveSubscipCrossover(scip, subscip, heur, heurdata, vars,
1026 fixedvars, fixedvals, nstallnodes, result, selection, nvars, nfixedvars, nusedsols);
1027
1028 /* free the subscip in any case */
1029 SCIP_CALL( SCIPfree(&subscip) );
1030 SCIP_CALL( retcode );
1031
1032 TERMINATE:
1033 /* free buffer storage for variable fixings */
1034 SCIPfreeBufferArray(scip, &fixedvals);
1035 SCIPfreeBufferArray(scip, &fixedvars);
1036 SCIPfreeBufferArray(scip, &selection);
1037
1038 return SCIP_OKAY;
1039 }
1040
1041 /*
1042 * primal heuristic specific interface methods
1043 */
1044
1045 /** creates the crossover primal heuristic and includes it in SCIP */
SCIPincludeHeurCrossover(SCIP * scip)1046 SCIP_RETCODE SCIPincludeHeurCrossover(
1047 SCIP* scip /**< SCIP data structure */
1048 )
1049 {
1050 SCIP_HEURDATA* heurdata;
1051 SCIP_HEUR* heur;
1052
1053 /* create Crossover primal heuristic data */
1054 SCIP_CALL( SCIPallocBlockMemory(scip, &heurdata) );
1055
1056 /* include primal heuristic */
1057 SCIP_CALL( SCIPincludeHeurBasic(scip, &heur,
1058 HEUR_NAME, HEUR_DESC, HEUR_DISPCHAR, HEUR_PRIORITY, HEUR_FREQ, HEUR_FREQOFS,
1059 HEUR_MAXDEPTH, HEUR_TIMING, HEUR_USESSUBSCIP, heurExecCrossover, heurdata) );
1060
1061 assert(heur != NULL);
1062
1063 /* set non-NULL pointers to callback methods */
1064 SCIP_CALL( SCIPsetHeurCopy(scip, heur, heurCopyCrossover) );
1065 SCIP_CALL( SCIPsetHeurFree(scip, heur, heurFreeCrossover) );
1066 SCIP_CALL( SCIPsetHeurInit(scip, heur, heurInitCrossover) );
1067 SCIP_CALL( SCIPsetHeurExit(scip, heur, heurExitCrossover) );
1068
1069 /* add crossover primal heuristic parameters */
1070
1071 SCIP_CALL( SCIPaddLongintParam(scip, "heuristics/" HEUR_NAME "/nodesofs",
1072 "number of nodes added to the contingent of the total nodes",
1073 &heurdata->nodesofs, FALSE, DEFAULT_NODESOFS, 0LL, SCIP_LONGINT_MAX, NULL, NULL) );
1074
1075 SCIP_CALL( SCIPaddLongintParam(scip, "heuristics/" HEUR_NAME "/maxnodes",
1076 "maximum number of nodes to regard in the subproblem",
1077 &heurdata->maxnodes, TRUE, DEFAULT_MAXNODES, 0LL, SCIP_LONGINT_MAX, NULL, NULL) );
1078
1079 SCIP_CALL( SCIPaddLongintParam(scip, "heuristics/" HEUR_NAME "/minnodes",
1080 "minimum number of nodes required to start the subproblem",
1081 &heurdata->minnodes, TRUE, DEFAULT_MINNODES, 0LL, SCIP_LONGINT_MAX, NULL, NULL) );
1082
1083 SCIP_CALL( SCIPaddIntParam(scip, "heuristics/" HEUR_NAME "/nusedsols",
1084 "number of solutions to be taken into account",
1085 &heurdata->nusedsols, FALSE, DEFAULT_NUSEDSOLS, 2, INT_MAX, NULL, NULL) );
1086
1087 SCIP_CALL( SCIPaddLongintParam(scip, "heuristics/" HEUR_NAME "/nwaitingnodes",
1088 "number of nodes without incumbent change that heuristic should wait",
1089 &heurdata->nwaitingnodes, TRUE, DEFAULT_NWAITINGNODES, 0LL, SCIP_LONGINT_MAX, NULL, NULL) );
1090
1091 SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/nodesquot",
1092 "contingent of sub problem nodes in relation to the number of nodes of the original problem",
1093 &heurdata->nodesquot, FALSE, DEFAULT_NODESQUOT, 0.0, 1.0, NULL, NULL) );
1094
1095 SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/minfixingrate",
1096 "minimum percentage of integer variables that have to be fixed",
1097 &heurdata->minfixingrate, FALSE, DEFAULT_MINFIXINGRATE, 0.0, 1.0, NULL, NULL) );
1098
1099 SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/minimprove",
1100 "factor by which Crossover should at least improve the incumbent",
1101 &heurdata->minimprove, TRUE, DEFAULT_MINIMPROVE, 0.0, 1.0, NULL, NULL) );
1102
1103 SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/lplimfac",
1104 "factor by which the limit on the number of LP depends on the node limit",
1105 &heurdata->lplimfac, TRUE, DEFAULT_LPLIMFAC, 1.0, SCIP_REAL_MAX, NULL, NULL) );
1106
1107 SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/randomization",
1108 "should the choice which sols to take be randomized?",
1109 &heurdata->randomization, TRUE, DEFAULT_RANDOMIZATION, NULL, NULL) );
1110
1111 SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/dontwaitatroot",
1112 "should the nwaitingnodes parameter be ignored at the root node?",
1113 &heurdata->dontwaitatroot, TRUE, DEFAULT_DONTWAITATROOT, NULL, NULL) );
1114
1115 SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/uselprows",
1116 "should subproblem be created out of the rows in the LP rows?",
1117 &heurdata->uselprows, TRUE, DEFAULT_USELPROWS, NULL, NULL) );
1118
1119 SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/copycuts",
1120 "if uselprows == FALSE, should all active cuts from cutpool be copied to constraints in subproblem?",
1121 &heurdata->copycuts, TRUE, DEFAULT_COPYCUTS, NULL, NULL) );
1122
1123 SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/permute",
1124 "should the subproblem be permuted to increase diversification?",
1125 &heurdata->permute, TRUE, DEFAULT_PERMUTE, NULL, NULL) );
1126
1127 SCIP_CALL( SCIPaddIntParam(scip, "heuristics/" HEUR_NAME "/bestsollimit",
1128 "limit on number of improving incumbent solutions in sub-CIP",
1129 &heurdata->bestsollimit, FALSE, DEFAULT_BESTSOLLIMIT, -1, INT_MAX, NULL, NULL) );
1130
1131 SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/useuct",
1132 "should uct node selection be used at the beginning of the search?",
1133 &heurdata->useuct, TRUE, DEFAULT_USEUCT, NULL, NULL) );
1134 return SCIP_OKAY;
1135 }
1136