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 visit scipopt.org. */
13 /* */
14 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
15
16 /**@file heur_clique.c
17 * @ingroup DEFPLUGINS_HEUR
18 * @brief LNS heuristic using a clique partition to restrict the search neighborhood
19 * @brief clique primal heuristic
20 * @author Stefan Heinz
21 * @author Michael Winkler
22 * @author Gerald Gamrath
23 *
24 * @todo allow smaller fixing rate for probing LP?
25 * @todo allow smaller fixing rate after presolve if total number of variables is small (<= 1000)?
26 *
27 * More details about the heuristic can be found in@n
28 * Structure-Based Primal Heuristics for Mixed Integer Programming@n
29 * Gerald Gamrath, Timo Berthold, Stefan Heinz, and Michael Winkler@n
30 * Optimization in the Real World, Volume 13 of the series Mathematics for Industry, pp 37-53@n
31 * Preliminary version available as <a href="https://opus4.kobv.de/opus4-zib/frontdoor/index/index/docId/5551">ZIB-Report 15-26</a>.
32 */
33
34 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
35
36 #include "blockmemshell/memory.h"
37 #include "scip/cons_logicor.h"
38 #include "scip/heur_clique.h"
39 #include "scip/heur_locks.h"
40 #include "scip/pub_heur.h"
41 #include "scip/pub_implics.h"
42 #include "scip/pub_message.h"
43 #include "scip/pub_misc.h"
44 #include "scip/pub_misc_sort.h"
45 #include "scip/pub_var.h"
46 #include "scip/scip_branch.h"
47 #include "scip/scip_cons.h"
48 #include "scip/scip_copy.h"
49 #include "scip/scip_general.h"
50 #include "scip/scip_heur.h"
51 #include "scip/scip_lp.h"
52 #include "scip/scip_mem.h"
53 #include "scip/scip_message.h"
54 #include "scip/scip_numerics.h"
55 #include "scip/scip_param.h"
56 #include "scip/scip_prob.h"
57 #include "scip/scip_probing.h"
58 #include "scip/scip_sol.h"
59 #include "scip/scip_solve.h"
60 #include "scip/scip_solvingstats.h"
61 #include "scip/scip_timing.h"
62 #include "scip/scip_tree.h"
63 #include "scip/scip_var.h"
64 #include <string.h>
65
66
67 #define HEUR_NAME "clique"
68 #define HEUR_DESC "LNS heuristic using a clique partition to restrict the search neighborhood"
69 #define HEUR_DISPCHAR SCIP_HEURDISPCHAR_PROP
70 #define HEUR_PRIORITY 5000
71 #define HEUR_FREQ 0
72 #define HEUR_FREQOFS 0
73 #define HEUR_MAXDEPTH -1
74 #define HEUR_TIMING SCIP_HEURTIMING_BEFORENODE
75 #define HEUR_USESSUBSCIP TRUE /**< does the heuristic use a secondary SCIP instance? */
76
77 #define DEFAULT_MAXNODES 5000LL /**< maximum number of nodes to regard in the subproblem */
78 #define DEFAULT_MININTFIXINGRATE 0.65 /**< minimum percentage of integer variables that have to be fixed */
79 #define DEFAULT_MINMIPFIXINGRATE 0.65 /**< minimum percentage of variables that have to be fixed within sub-SCIP
80 * (integer and continuous) */
81 #define DEFAULT_MINIMPROVE 0.01 /**< factor by which clique heuristic should at least improve the
82 * incumbent */
83 #define DEFAULT_MINNODES 500LL /**< minimum number of nodes to regard in the subproblem */
84 #define DEFAULT_NODESOFS 500LL /**< number of nodes added to the contingent of the total nodes */
85 #define DEFAULT_NODESQUOT 0.1 /**< subproblem nodes in relation to nodes of the original problem */
86 #define DEFAULT_MAXPROPROUNDS 2 /**< maximum number of propagation rounds during probing */
87 #define DEFAULT_MAXBACKTRACKS 10 /**< maximum number of backtracks during the fixing process */
88 #define DEFAULT_COPYCUTS TRUE /**< should all active cuts from the cutpool of the
89 * original scip be copied to constraints of the subscip */
90 #define DEFAULT_USELOCKFIXINGS FALSE /**< should more variables be fixed based on variable locks if
91 * the fixing rate was not reached? */
92
93
94 /*
95 * Data structures
96 */
97
98 /** primal heuristic data */
99 struct SCIP_HeurData
100 {
101 SCIP_Longint maxnodes; /**< maximum number of nodes to regard in the subproblem */
102 SCIP_Longint minnodes; /**< minimum number of nodes to regard in the subproblem */
103 SCIP_Longint nodesofs; /**< number of nodes added to the contingent of the total nodes */
104 SCIP_Longint usednodes; /**< nodes already used by clique heuristic in earlier calls */
105 SCIP_Real minintfixingrate; /**< minimum percentage of integer variables that have to be fixed */
106 SCIP_Real minmipfixingrate; /**< minimum percentage of variables that have to be fixed within sub-SCIP
107 * (integer and continuous) */
108 SCIP_Real minimprove; /**< factor by which clique heuristic should at least improve the incumbent */
109 SCIP_Real nodesquot; /**< subproblem nodes in relation to nodes of the original problem */
110 int maxproprounds; /**< maximum number of propagation rounds during probing */
111 int maxbacktracks; /**< maximum number of backtracks during the fixing process */
112 SCIP_Bool copycuts; /**< should all active cuts from cutpool be copied to constraints in
113 * subproblem?
114 */
115 SCIP_Bool uselockfixings; /**< should more variables be fixed based on variable locks if
116 * the fixing rate was not reached?
117 */
118 };
119
120 /*
121 * Local methods
122 */
123
124 /** comparison method for sorting cliques by their size */
125 static
126 SCIP_DECL_SORTINDCOMP(compCliquesSize)
127 {
128 int* cliquesizes = (int*)dataptr;
129
130 return cliquesizes[ind2] - cliquesizes[ind1];
131 }
132
133 static
134 int getCliqueUnfixedVars(
135 SCIP_CLIQUE* clique
136 )
137 {
138 SCIP_VAR** cliquevars;
139 SCIP_VAR* var;
140 int ncliquevars;
141 int nunfixed = 0;
142 int v;
143
144 ncliquevars = SCIPcliqueGetNVars(clique);
145 cliquevars = SCIPcliqueGetVars(clique);
146
147 for( v = 0; v < ncliquevars; ++v )
148 {
149 var = cliquevars[v];
150
151 /* is variable unfixed? */
152 if( SCIPvarGetUbLocal(var) > SCIPvarGetLbLocal(var) + 0.5 )
153 ++nunfixed;
154 }
155
156 return nunfixed;
157 }
158
159 /** apply clique fixing using probing */
160 static
161 SCIP_RETCODE applyCliqueFixings(
162 SCIP* scip, /**< original SCIP data structure */
163 SCIP_HEURDATA* heurdata, /**< structure containing heurdata */
164 SCIP_Bool enabledconflicts, /**< was conflict analysis enabled before the heuristic call? */
165 SCIP_VAR** onefixvars, /**< array to store all variables which are fixed to one in the cliques */
166 SCIP_Shortbool* onefixvals, /**< array to store the values of all variables fixed to one in the cliques */
167 int* nonefixvars, /**< pointer to store the number of variables fixed to one */
168 SCIP_Bool* cutoff /**< pointer to store whether the propagation stopped with infeasibility */
169 )
170 {
171 SCIP_CLIQUE** cliques;
172 SCIP_CLIQUE* clique;
173 SCIP_VAR** cliquevars;
174 SCIP_VAR* var;
175 SCIP_Bool* cliquevals;
176 SCIP_Bool* propagated;
177 int* cliquesizes;
178 int* permutation;
179 SCIP_Real bestobj;
180 SCIP_Real obj;
181 SCIP_Bool alreadyone;
182 SCIP_Bool newnode;
183 int probingdepthofonefix;
184 int ncliquevars;
185 int ncliques;
186 int bestpos;
187 int firstclique;
188 int bestclique;
189 int cliquesize;
190 int bestcliquesize;
191 int nbacktracks = 0;
192 int v = 0;
193 int c;
194 int i;
195
196 assert(scip != NULL);
197 assert(heurdata != NULL);
198 assert(onefixvars != NULL);
199 assert(nonefixvars != NULL);
200 assert(cutoff != NULL);
201
202 cliques = SCIPgetCliques(scip);
203 ncliques = SCIPgetNCliques(scip);
204
205 /* allocate memory */
206 SCIP_CALL( SCIPallocBufferArray(scip, &cliquesizes, ncliques) );
207 SCIP_CALL( SCIPallocBufferArray(scip, &permutation, ncliques) );
208 SCIP_CALL( SCIPallocClearBufferArray(scip, &propagated, ncliques) );
209
210 for( c = ncliques - 1; c >= 0; --c )
211 {
212 cliquesizes[c] = SCIPcliqueGetNVars(cliques[c]);
213 }
214
215 SCIPsort(permutation, compCliquesSize, (void*)cliquesizes, ncliques);
216
217 #ifndef NDEBUG
218 for( c = ncliques - 1; c >= 1; --c )
219 {
220 assert(cliquesizes[permutation[c]] <= cliquesizes[permutation[c-1]]);
221 }
222 #endif
223
224 *cutoff = FALSE;
225 probingdepthofonefix = 0;
226 firstclique = 0;
227
228 SCIP_CALL( SCIPnewProbingNode(scip) );
229
230 /* @todo maybe try to fix more than one variable to one in each probing node, to gain faster results */
231 for( c = 0; c < ncliques; ++c )
232 {
233 bestpos = -1;
234 bestobj = SCIPinfinity(scip);
235 alreadyone = FALSE;
236 newnode = FALSE;
237
238 bestclique = firstclique;
239
240 if( bestclique >= ncliques )
241 break;
242
243 bestcliquesize = getCliqueUnfixedVars(cliques[permutation[bestclique]]);
244 assert(!propagated[permutation[bestclique]]);
245
246 for( i = firstclique + 1; i < ncliques; ++i)
247 {
248 if( cliquesizes[permutation[i]] < bestcliquesize )
249 break;
250
251 if( propagated[permutation[i]] )
252 continue;
253
254 cliquesize = getCliqueUnfixedVars(cliques[permutation[i]]);
255
256 if( cliquesize > bestcliquesize )
257 {
258 bestclique = i;
259 bestcliquesize = cliquesize;
260 }
261 else if( cliquesize == 0 )
262 {
263 propagated[permutation[i]] = TRUE;
264 }
265 }
266 clique = cliques[permutation[bestclique]];
267 propagated[permutation[bestclique]] = TRUE;
268
269 while( firstclique < ncliques && propagated[permutation[firstclique]] )
270 ++firstclique;
271
272 ncliquevars = SCIPcliqueGetNVars(clique);
273 cliquevars = SCIPcliqueGetVars(clique);
274 cliquevals = SCIPcliqueGetValues(clique);
275
276 for( v = 0; v < ncliquevars; ++v )
277 {
278 var = cliquevars[v];
279
280 /* variable is already fixed */
281 if( SCIPvarGetUbLocal(var) < SCIPvarGetLbLocal(var) + 0.5 )
282 {
283 SCIPdebugMsg(scip, "<%s> is already fixed to %g\n", SCIPvarGetName(var), SCIPvarGetUbLocal(var));
284
285 /* clique variable is fixed to 1 */
286 if( cliquevals[v] == (SCIPvarGetLbLocal(var) > 0.5) )
287 {
288 assert(!alreadyone);
289 alreadyone = TRUE;
290 break;
291 }
292 continue;
293 }
294
295 obj = cliquevals[v] ? SCIPvarGetObj(var) : -SCIPvarGetObj(var);
296
297 /* @todo use a tiebreaker (locks?) */
298 if( obj < bestobj )
299 {
300 /* variable is not the best one in the clique anymore, fix it to 0 */
301 if( bestpos >= 0 )
302 {
303 if( cliquevals[bestpos] )
304 {
305 SCIP_CALL( SCIPfixVarProbing(scip, cliquevars[bestpos], 0.0) );
306 }
307 else
308 {
309 SCIP_CALL( SCIPfixVarProbing(scip, cliquevars[bestpos], 1.0) );
310 }
311 SCIPdebugMsg(scip, "fixed <%s> to %g\n", SCIPvarGetName(cliquevars[bestpos]), SCIPvarGetUbLocal(cliquevars[bestpos]));
312 newnode = TRUE;
313 }
314
315 bestobj = obj;
316 bestpos = v;
317 }
318 /* variable is not the best one in the clique, fix it to 0 */
319 else
320 {
321 assert(bestpos >= 0);
322
323 if( cliquevals[v] )
324 {
325 SCIP_CALL( SCIPfixVarProbing(scip, var, 0.0) );
326 }
327 else
328 {
329 SCIP_CALL( SCIPfixVarProbing(scip, var, 1.0) );
330 }
331 SCIPdebugMsg(scip, "fixed <%s> to %g\n", SCIPvarGetName(var), SCIPvarGetUbLocal(var));
332 newnode = TRUE;
333 }
334 }
335 /* we found a variable in the clique which is already fixed to 1 */
336 if( alreadyone )
337 {
338 /* fix (so far) best candidate to 0 */
339 if( bestpos >= 0 )
340 {
341 if( cliquevals[bestpos] )
342 {
343 SCIP_CALL( SCIPfixVarProbing(scip, cliquevars[bestpos], 0.0) );
344 }
345 else
346 {
347 SCIP_CALL( SCIPfixVarProbing(scip, cliquevars[bestpos], 1.0) );
348 }
349 SCIPdebugMsg(scip, "fixed <%s> to %g\n", SCIPvarGetName(cliquevars[bestpos]), SCIPvarGetUbLocal(cliquevars[bestpos]));
350 newnode = TRUE;
351 }
352
353 /* fix all variables not yet processed to 0 */
354 for( ; v < ncliquevars; ++v )
355 {
356 var = cliquevars[v];
357
358 if( SCIPvarGetUbLocal(var) < SCIPvarGetLbLocal(var) + 0.5 )
359 continue;
360
361 if( cliquevals[v] )
362 {
363 SCIP_CALL( SCIPfixVarProbing(scip, var, 0.0) );
364 }
365 else
366 {
367 SCIP_CALL( SCIPfixVarProbing(scip, var, 1.0) );
368 }
369 SCIPdebugMsg(scip, "fixed <%s> to %g\n", SCIPvarGetName(var), SCIPvarGetUbLocal(var));
370 newnode = TRUE;
371 }
372 }
373 /* fix the best variable to 1 */
374 else if( bestpos >= 0 )
375 {
376 assert(bestpos <= ncliquevars);
377
378 probingdepthofonefix = SCIPgetProbingDepth(scip);
379 onefixvars[(*nonefixvars)] = cliquevars[bestpos];
380
381 /* @todo should we even fix the best candidate to 1? */
382 if( cliquevals[bestpos] )
383 {
384 SCIP_CALL( SCIPfixVarProbing(scip, cliquevars[bestpos], 1.0) );
385 onefixvals[(*nonefixvars)] = 1;
386 }
387 else
388 {
389 SCIP_CALL( SCIPfixVarProbing(scip, cliquevars[bestpos], 0.0) );
390 onefixvals[(*nonefixvars)] = 0;
391 }
392 SCIPdebugMsg(scip, "fixed <%s> to %g*\n", SCIPvarGetName(cliquevars[bestpos]), SCIPvarGetUbLocal(cliquevars[bestpos]));
393 ++(*nonefixvars);
394 newnode = TRUE;
395 }
396
397 if( newnode )
398 {
399 /* propagate fixings */
400 SCIP_CALL( SCIPpropagateProbing(scip, heurdata->maxproprounds, cutoff, NULL) );
401
402 SCIPdebugMsg(scip, "propagate fixings of clique %d: cutoff=%u\n", c, *cutoff);
403
404 if( SCIPisStopped(scip) )
405 break;
406
407 /* stop if we reached the depth limit */
408 if( SCIP_MAXTREEDEPTH <= SCIPgetDepth(scip) )
409 break;
410
411 /* probing detected infeasibility: backtrack */
412 if( *cutoff )
413 {
414 if( *nonefixvars > 0 )
415 {
416 if( probingdepthofonefix > 0 )
417 {
418 SCIP_CALL( SCIPbacktrackProbing(scip, probingdepthofonefix - 1) );
419 probingdepthofonefix = 0;
420 ++nbacktracks;
421
422 /* because of the limited number of propagation rounds, it may happen that conflict analysis finds a
423 * valid global fixing for the last fixed variable that conflicts with applying the reverse fixing
424 * after backtracking; in that case, we ran into a deadend and stop
425 */
426 if( SCIPvarGetLbLocal(onefixvars[*nonefixvars - 1]) < 1.5 - onefixvals[*nonefixvars - 1]
427 && SCIPvarGetUbLocal(onefixvars[*nonefixvars - 1]) > 0.5 - onefixvals[*nonefixvars - 1] )
428 {
429 /* fix the last variable, which was fixed to 1 and led to the cutoff, to 0 */
430 SCIP_CALL( SCIPfixVarProbing(scip, onefixvars[*nonefixvars - 1], 1.0 - onefixvals[*nonefixvars - 1]) );
431 --(*nonefixvars);
432
433 /* propagate fixings */
434 SCIP_CALL( SCIPpropagateProbing(scip, heurdata->maxproprounds, cutoff, NULL) );
435
436 SCIPdebugMsg(scip, "backtrack %d was %sfeasible\n", nbacktracks, (*cutoff ? "in" : ""));
437 }
438 #ifndef NDEBUG
439 else
440 assert(*cutoff == TRUE);
441 #endif
442 }
443 if( *cutoff )
444 {
445 SCIPdebugMsg(scip, "probing was infeasible after %d backtracks\n", nbacktracks);
446 #ifndef NOCONFLICT
447 if( enabledconflicts )
448 {
449 SCIP_CONS* conflictcons;
450 char consname[SCIP_MAXSTRLEN];
451
452 /* create own conflict */
453 (void) SCIPsnprintf(consname, SCIP_MAXSTRLEN, "conf%" SCIP_LONGINT_FORMAT "", SCIPgetNNodes(scip));
454
455 /* get variables for the conflict */
456 for( i = 0; i < *nonefixvars; ++i )
457 {
458 /* if the variable was fixed to 1 by the heuristic, get its negated variable */
459 if( onefixvals[i] )
460 {
461 SCIP_CALL( SCIPgetNegatedVar(scip, onefixvars[i], &onefixvars[i]) );
462 }
463 }
464
465 /* create conflict constraint */
466 SCIP_CALL( SCIPcreateConsLogicor(scip, &conflictcons, consname, *nonefixvars, onefixvars,
467 FALSE, TRUE, FALSE, FALSE, TRUE, TRUE, FALSE, TRUE, TRUE, FALSE) );
468 SCIP_CALL( SCIPaddConflict(scip, SCIPgetFocusNode(scip), conflictcons, NULL, SCIP_CONFTYPE_PROPAGATION, FALSE) );
469 SCIPdebugPrintCons(scip, conflictcons, NULL);
470 }
471 #endif
472 break;
473 }
474 else if( nbacktracks > heurdata->maxbacktracks )
475 {
476 SCIPdebugMsg(scip, "interrupt probing after %d backtracks\n", nbacktracks);
477 break;
478 }
479 }
480 /* we had a cutoff without a single one-fixing, so the current problem seems to be infeasible already */
481 else
482 break;
483 }
484
485 SCIP_CALL( SCIPnewProbingNode(scip) );
486 }
487 }
488 assert((*nonefixvars > 0) || probingdepthofonefix == 0 );
489
490 SCIPfreeBufferArray(scip, &propagated);
491 SCIPfreeBufferArray(scip, &permutation);
492 SCIPfreeBufferArray(scip, &cliquesizes);
493
494 SCIPdebugMsg(scip, "fixed %d of %d variables in probing\n", v, SCIPgetNBinVars(scip));
495 SCIPdebugMsg(scip, "applied %d of %d cliques in probing\n", c, ncliques);
496 SCIPdebugMsg(scip, "probing was %sfeasible\n", (*cutoff) ? "in" : "");
497
498 return SCIP_OKAY;
499 }
500
501 /*
502 * Callback methods of primal heuristic
503 */
504
505 /** copy method for primal heuristic plugins (called when SCIP copies plugins) */
506 static
507 SCIP_DECL_HEURCOPY(heurCopyClique)
508 { /*lint --e{715}*/
509 assert(scip != NULL);
510 assert(heur != NULL);
511 assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0);
512
513 /* call inclusion method of primal heuristic */
514 SCIP_CALL( SCIPincludeHeurClique(scip) );
515
516 return SCIP_OKAY;
517 }
518
519 /** destructor of primal heuristic to free user data (called when SCIP is exiting) */
520 static
521 SCIP_DECL_HEURFREE(heurFreeClique)
522 { /*lint --e{715}*/
523 SCIP_HEURDATA* heurdata;
524
525 assert(heur != NULL);
526 assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0);
527 assert(scip != NULL);
528
529 /* free heuristic data */
530 heurdata = SCIPheurGetData(heur);
531 assert(heurdata != NULL);
532
533 SCIPfreeBlockMemory(scip, &heurdata);
534 SCIPheurSetData(heur, NULL);
535
536 return SCIP_OKAY;
537 }
538
539
540 /** initialization method of primal heuristic (called after problem was transformed) */
541 static
542 SCIP_DECL_HEURINIT(heurInitClique)
543 { /*lint --e{715}*/
544 SCIP_HEURDATA* heurdata;
545
546 assert(heur != NULL);
547 assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0);
548 assert(scip != NULL);
549
550 /* reset heuristic data */
551 heurdata = SCIPheurGetData(heur);
552 assert(heurdata != NULL);
553
554 heurdata->usednodes = 0;
555
556 return SCIP_OKAY;
557 }
558
559 /** execution method of primal heuristic */
560 static
561 SCIP_DECL_HEUREXEC(heurExecClique)
562 { /*lint --e{715}*/
563 SCIP_HEURDATA* heurdata;
564 SCIP_VAR** vars;
565 SCIP_Real lowerbound;
566 int nvars;
567 int nbinvars;
568 int oldnpscands;
569 int npscands;
570 int i;
571 SCIP_Bool cutoff;
572 SCIP_Bool lperror;
573
574 SCIP_VAR** onefixvars;
575 SCIP_Shortbool* onefixvals;
576 int nonefixvars;
577 SCIP_Bool enabledconflicts;
578 SCIP_LPSOLSTAT lpstatus;
579 SCIP_CONS* conflictcons;
580 SCIP_Bool solvelp;
581 char consname[SCIP_MAXSTRLEN];
582
583 SCIP_Longint nstallnodes;
584
585 assert(heur != NULL);
586 assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0);
587 assert(scip != NULL);
588 assert(result != NULL);
589
590 *result = SCIP_DIDNOTRUN;
591
592 /* get heuristic's data */
593 heurdata = SCIPheurGetData(heur);
594 assert(heurdata != NULL);
595
596 nbinvars = SCIPgetNBinVars(scip);
597
598 if( nbinvars < 2 )
599 return SCIP_OKAY;
600
601 /* check for necessary information to apply this heuristic */
602 if( SCIPgetNCliques(scip) == 0 )
603 return SCIP_OKAY;
604
605 lowerbound = SCIPgetLowerbound(scip);
606
607 /* calculate the maximal number of branching nodes until heuristic is aborted */
608 nstallnodes = (SCIP_Longint)(heurdata->nodesquot * SCIPgetNNodes(scip));
609
610 /* reward clique heuristic if it succeeded often */
611 nstallnodes = (SCIP_Longint)(nstallnodes * 3.0 * (SCIPheurGetNBestSolsFound(heur)+1.0)/(SCIPheurGetNCalls(heur) + 1.0));
612 nstallnodes -= 100 * SCIPheurGetNCalls(heur); /* count the setup costs for the sub-MIP as 100 nodes */
613 nstallnodes += heurdata->nodesofs;
614
615 /* determine the node limit for the current process */
616 nstallnodes -= heurdata->usednodes;
617 nstallnodes = MIN(nstallnodes, heurdata->maxnodes);
618
619 /* check whether we have enough nodes left to call subproblem solving */
620 if( nstallnodes < heurdata->minnodes )
621 {
622 SCIPdebugMsg(scip, "skipping " HEUR_NAME ": nstallnodes=%" SCIP_LONGINT_FORMAT ", minnodes=%" SCIP_LONGINT_FORMAT "\n", nstallnodes, heurdata->minnodes);
623 return SCIP_OKAY;
624 }
625
626 oldnpscands = SCIPgetNPseudoBranchCands(scip);
627 onefixvars = NULL;
628 onefixvals = NULL;
629
630 /* disable conflict analysis, because we can it better than SCIP itself, cause we have more information */
631 SCIP_CALL( SCIPgetBoolParam(scip, "conflict/enable", &enabledconflicts) );
632
633 if( !SCIPisParamFixed(scip, "conflict/enable") )
634 {
635 SCIP_CALL( SCIPsetBoolParam(scip, "conflict/enable", FALSE) );
636 }
637
638 solvelp = SCIPhasCurrentNodeLP(scip);
639
640 if( !SCIPisLPConstructed(scip) && solvelp )
641 {
642 SCIP_CALL( SCIPconstructLP(scip, &cutoff) );
643
644 /* manually cut off the node if the LP construction detected infeasibility (heuristics cannot return such a result) */
645 if( cutoff )
646 {
647 SCIP_CALL( SCIPcutoffNode(scip, SCIPgetCurrentNode(scip)) );
648 goto TERMINATE;
649 }
650
651 SCIP_CALL( SCIPflushLP(scip) );
652 }
653
654 /* refresh nbinvars in case constructLP suddenly added new ones */
655 nbinvars = SCIPgetNBinVars(scip);
656 assert(nbinvars >= 2);
657
658 *result = SCIP_DIDNOTFIND;
659
660 /* start probing */
661 SCIP_CALL( SCIPstartProbing(scip) );
662
663 #ifdef COLLECTSTATISTICS
664 SCIPenableVarHistory(scip);
665 #endif
666
667 /* allocate memory for all variables which will be fixed to one during probing */
668 SCIP_CALL(SCIPallocBufferArray(scip, &onefixvars, nbinvars) );
669 SCIP_CALL(SCIPallocBufferArray(scip, &onefixvals, nbinvars) );
670 nonefixvars = 0;
671
672 /* apply fixings due to clique information */
673 SCIP_CALL( applyCliqueFixings(scip, heurdata, enabledconflicts, onefixvars, onefixvals, &nonefixvars, &cutoff) );
674
675 if( cutoff || SCIPisStopped(scip) )
676 goto TERMINATE;
677
678 /* check that we had enough fixings */
679 npscands = SCIPgetNPseudoBranchCands(scip);
680
681 SCIPdebugMsg(scip, "npscands=%d, oldnpscands=%d, heurdata->minintfixingrate=%g\n", npscands, oldnpscands, heurdata->minintfixingrate);
682
683 if( npscands > oldnpscands * (1.0 - heurdata->minintfixingrate) )
684 {
685 if( heurdata->uselockfixings && npscands <= 2.0 * oldnpscands * (1.0 - heurdata->minintfixingrate) )
686 {
687 SCIP_Bool allrowsfulfilled = FALSE;
688
689 SCIP_CALL( SCIPapplyLockFixings(scip, NULL, &cutoff, &allrowsfulfilled) );
690
691 if( cutoff || SCIPisStopped(scip) )
692 {
693 SCIPdebugMsg(scip, "cutoff or timeout in locks fixing\n");
694 goto TERMINATE;
695 }
696
697 npscands = SCIPgetNPseudoBranchCands(scip);
698
699 SCIPdebugMsg(scip, "after lockfixings: npscands=%d, oldnpscands=%d, allrowsfulfilled=%u, heurdata->minintfixingrate=%g\n",
700 npscands, oldnpscands, allrowsfulfilled, heurdata->minintfixingrate);
701
702 if( !allrowsfulfilled && npscands > oldnpscands * (1 - heurdata->minintfixingrate) )
703 {
704 SCIPdebugMsg(scip, "--> too few fixings\n");
705
706 goto TERMINATE;
707 }
708 }
709 else
710 {
711 SCIPdebugMsg(scip, "--> too few fixings\n");
712
713 goto TERMINATE;
714 }
715 }
716
717 /*************************** Probing LP Solving ***************************/
718
719 lpstatus = SCIP_LPSOLSTAT_ERROR;
720 lperror = FALSE;
721
722 /* solve lp only if the problem is still feasible */
723 if( solvelp )
724 {
725 char strbuf[SCIP_MAXSTRLEN];
726 int ncols;
727
728 /* print message if relatively large LP is solved from scratch, since this could lead to a longer period during
729 * which the user sees no output; more detailed probing stats only in debug mode */
730 ncols = SCIPgetNLPCols(scip);
731 if( !SCIPisLPSolBasic(scip) && ncols > 1000 )
732 {
733 int nunfixedcols = SCIPgetNUnfixedLPCols(scip);
734
735 if( nunfixedcols > 0.5 * ncols )
736 {
737 SCIPverbMessage(scip, SCIP_VERBLEVEL_FULL, NULL,
738 "Heuristic " HEUR_NAME " solving LP from scratch with %.1f %% unfixed columns (%d of %d) ...\n",
739 100.0 * (nunfixedcols / (SCIP_Real)ncols), nunfixedcols, ncols);
740 }
741 }
742 SCIPdebugMsg(scip, "Heuristic " HEUR_NAME " probing LP: %s\n",
743 SCIPsnprintfProbingStats(scip, strbuf, SCIP_MAXSTRLEN));
744
745 /* solve LP; errors in the LP solver should not kill the overall solving process, if the LP is just needed for a
746 * heuristic. hence in optimized mode, the return code is caught and a warning is printed, only in debug mode,
747 * SCIP will stop.
748 */
749 SCIPdebugMsg(scip, "starting solving clique-lp at time %g\n", SCIPgetSolvingTime(scip));
750 #ifdef NDEBUG
751 {
752 SCIP_Bool retstat;
753 retstat = SCIPsolveProbingLP(scip, -1, &lperror, NULL);
754 if( retstat != SCIP_OKAY )
755 {
756 SCIPwarningMessage(scip, "Error while solving LP in clique heuristic; LP solve terminated with code <%d>\n",
757 retstat);
758 }
759 }
760 #else
761 SCIP_CALL( SCIPsolveProbingLP(scip, -1, &lperror, NULL) );
762 #endif
763 SCIPdebugMsg(scip, "ending solving clique-lp at time %g\n", SCIPgetSolvingTime(scip));
764
765 lpstatus = SCIPgetLPSolstat(scip);
766
767 SCIPdebugMsg(scip, " -> new LP iterations: %" SCIP_LONGINT_FORMAT "\n", SCIPgetNLPIterations(scip));
768 SCIPdebugMsg(scip, " -> error=%u, status=%d\n", lperror, lpstatus);
769 }
770
771 /* check if this is a feasible solution */
772 if( lpstatus == SCIP_LPSOLSTAT_OPTIMAL && !lperror )
773 {
774 SCIP_SOL* sol;
775 SCIP_Bool stored;
776 SCIP_Bool success;
777
778 assert(!cutoff);
779
780 lowerbound = SCIPgetLPObjval(scip);
781
782 /* create a solution from the current LP solution */
783 SCIP_CALL( SCIPcreateSol(scip, &sol, heur) );
784 SCIP_CALL( SCIPlinkLPSol(scip, sol) );
785
786 SCIP_CALL( SCIProundSol(scip, sol, &success) );
787
788 if( success )
789 {
790 SCIPdebugMsg(scip, "clique heuristic found roundable primal solution: obj=%g\n",
791 SCIPgetSolOrigObj(scip, sol));
792
793 /* check solution for feasibility, and add it to solution store if possible.
794 * Neither integrality nor feasibility of LP rows have to be checked, because they
795 * are guaranteed by the heuristic at this stage.
796 */
797 #ifdef SCIP_DEBUG
798 SCIP_CALL( SCIPtrySol(scip, sol, TRUE, TRUE, TRUE, TRUE, TRUE, &stored) );
799 #else
800 SCIP_CALL( SCIPtrySol(scip, sol, FALSE, FALSE, TRUE, FALSE, FALSE, &stored) );
801 #endif
802
803 if( stored )
804 {
805 SCIPdebugMsg(scip, "found feasible solution:\n");
806 SCIPdebug( SCIP_CALL( SCIPprintSol(scip, sol, NULL, FALSE) ) );
807 *result = SCIP_FOUNDSOL;
808 }
809
810 SCIP_CALL( SCIPfreeSol(scip, &sol) );
811
812 /* we found a solution, so we are done */
813 goto TERMINATE;
814 }
815
816 SCIP_CALL( SCIPfreeSol(scip, &sol) );
817 }
818 /*************************** END Probing LP Solving ***************************/
819
820 /*************************** Create Conflict ***************************/
821 if( enabledconflicts && SCIPallColsInLP(scip) &&
822 (lpstatus == SCIP_LPSOLSTAT_INFEASIBLE || lpstatus == SCIP_LPSOLSTAT_OBJLIMIT) )
823 {
824 #ifndef NOCONFLICT
825 /* create own conflict */
826 (void) SCIPsnprintf(consname, SCIP_MAXSTRLEN, "conf%" SCIP_LONGINT_FORMAT "", SCIPgetNNodes(scip));
827
828 /* get variables for the conflict */
829 for( i = 0; i < nonefixvars; ++i )
830 {
831 /* if the variable was fixed to 1 by the heuristic, get its negated variable */
832 if( onefixvals[i] )
833 {
834 SCIP_CALL( SCIPgetNegatedVar(scip, onefixvars[i], &onefixvars[i]) );
835 }
836 }
837
838 /* create conflict constraint */
839 SCIP_CALL( SCIPcreateConsLogicor(scip, &conflictcons, consname, nonefixvars, onefixvars,
840 FALSE, TRUE, FALSE, FALSE, TRUE, TRUE, FALSE, TRUE, TRUE, FALSE) );
841 SCIP_CALL( SCIPaddConflict(scip, SCIPgetFocusNode(scip), conflictcons, NULL, SCIP_CONFTYPE_INFEASLP, FALSE) );
842 SCIPdebugPrintCons(scip, conflictcons, NULL);
843 #endif
844 goto TERMINATE;
845 }
846 /*************************** End Conflict ***************************/
847
848 /*************************** Start Subscip Solving ***************************/
849 /* no solution has been found yet and the subproblem is still feasible --> fix all other variables by subscip if
850 * necessary
851 */
852 if( !lperror )
853 {
854 SCIP* subscip;
855 SCIP_VAR** subvars;
856 SCIP_HASHMAP* varmap;
857 SCIP_Bool valid;
858
859 /* check whether there is enough time and memory left */
860 SCIP_CALL( SCIPcheckCopyLimits(scip, &valid) );
861
862 if( !valid )
863 goto TERMINATE;
864
865 /* get all variables */
866 SCIP_CALL( SCIPgetVarsData(scip, &vars, &nvars, NULL, NULL, NULL, NULL) );
867
868 /* create subproblem */
869 SCIP_CALL( SCIPcreate(&subscip) );
870
871 /* allocate temporary memory for subscip variables */
872 SCIP_CALL( SCIPallocBufferArray(scip, &subvars, nvars) );
873
874 /* create the variable mapping hash map */
875 SCIP_CALL( SCIPhashmapCreate(&varmap, SCIPblkmem(subscip), nvars) );
876
877 SCIP_CALL( SCIPcopyConsCompression(scip, subscip, varmap, NULL, "_clique", NULL, NULL, 0, FALSE, FALSE, FALSE,
878 TRUE, &valid) );
879
880 if( heurdata->copycuts )
881 {
882 /* copies all active cuts from cutpool of sourcescip to linear constraints in targetscip */
883 SCIP_CALL( SCIPcopyCuts(scip, subscip, varmap, NULL, FALSE, NULL) );
884 }
885
886 for( i = 0; i < nvars; i++ )
887 subvars[i] = (SCIP_VAR*) SCIPhashmapGetImage(varmap, vars[i]);
888
889 /* free hash map */
890 SCIPhashmapFree(&varmap);
891
892 /* do not abort subproblem on CTRL-C */
893 SCIP_CALL( SCIPsetBoolParam(subscip, "misc/catchctrlc", FALSE) );
894
895 #ifdef SCIP_DEBUG
896 /* for debugging, enable full output */
897 SCIP_CALL( SCIPsetIntParam(subscip, "display/verblevel", 5) );
898 SCIP_CALL( SCIPsetIntParam(subscip, "display/freq", 100000000) );
899 #else
900 /* disable statistic timing inside sub SCIP and output to console */
901 SCIP_CALL( SCIPsetIntParam(subscip, "display/verblevel", 0) );
902 SCIP_CALL( SCIPsetBoolParam(subscip, "timing/statistictiming", FALSE) );
903 #endif
904
905 /* set limits for the subproblem */
906 SCIP_CALL( SCIPcopyLimits(scip, subscip) );
907 SCIP_CALL( SCIPsetLongintParam(subscip, "limits/stallnodes", nstallnodes) );
908 SCIP_CALL( SCIPsetLongintParam(subscip, "limits/nodes", heurdata->maxnodes) );
909
910 /* speed up sub-SCIP by not checking dual LP feasibility */
911 SCIP_CALL( SCIPsetBoolParam(subscip, "lp/checkdualfeas", FALSE) );
912
913 /* forbid call of heuristics and separators solving sub-CIPs */
914 SCIP_CALL( SCIPsetSubscipsOff(subscip, TRUE) );
915
916 /* disable cutting plane separation */
917 SCIP_CALL( SCIPsetSeparating(subscip, SCIP_PARAMSETTING_OFF, TRUE) );
918
919 /* disable expensive presolving */
920 SCIP_CALL( SCIPsetPresolving(subscip, SCIP_PARAMSETTING_FAST, TRUE) );
921
922 /* use inference branching */
923 if( SCIPfindBranchrule(subscip, "inference") != NULL && !SCIPisParamFixed(subscip, "branching/inference/priority") )
924 {
925 SCIP_CALL( SCIPsetIntParam(subscip, "branching/inference/priority", INT_MAX/4) );
926 }
927
928 /* if there is already a solution, add an objective cutoff */
929 if( SCIPgetNSols(scip) > 0 )
930 {
931 SCIP_Real upperbound;
932 SCIP_Real minimprove;
933 SCIP_Real cutoffbound;
934
935 minimprove = heurdata->minimprove;
936 assert( !SCIPisInfinity(scip,SCIPgetUpperbound(scip)) );
937
938 upperbound = SCIPgetUpperbound(scip) - SCIPsumepsilon(scip);
939
940 if( !SCIPisInfinity(scip, -1.0 * lowerbound) )
941 {
942 cutoffbound = (1-minimprove) * SCIPgetUpperbound(scip) + minimprove * lowerbound;
943 }
944 else
945 {
946 if( SCIPgetUpperbound ( scip ) >= 0 )
947 cutoffbound = (1 - minimprove) * SCIPgetUpperbound(scip);
948 else
949 cutoffbound = (1 + minimprove) * SCIPgetUpperbound(scip);
950 }
951 cutoffbound = MIN(upperbound, cutoffbound);
952 SCIP_CALL( SCIPsetObjlimit(subscip, cutoffbound) );
953 SCIPdebugMsg(scip, "setting objlimit for subscip to %g\n", cutoffbound);
954 }
955
956 SCIPdebugMsg(scip, "starting solving clique-submip at time %g\n", SCIPgetSolvingTime(scip));
957
958 /* solve the subproblem */
959 /* Errors in the LP solver should not kill the overall solving process, if the LP is just needed for a heuristic.
960 * Hence in optimized mode, the return code is caught and a warning is printed, only in debug mode, SCIP will stop.
961 */
962 SCIP_CALL_ABORT( SCIPpresolve(subscip) );
963
964 SCIPdebugMsg(scip, "clique heuristic presolved subproblem at time %g : %d vars, %d cons; fixing value = %g\n", SCIPgetSolvingTime(scip), SCIPgetNVars(subscip), SCIPgetNConss(subscip), ((nvars - SCIPgetNVars(subscip)) / (SCIP_Real)nvars));
965
966 /* after presolving, we should have at least reached a certain fixing rate over ALL variables (including continuous)
967 * to ensure that not only the MIP but also the LP relaxation is easy enough
968 */
969 if( ((nvars - SCIPgetNVars(subscip)) / (SCIP_Real)nvars) >= heurdata->minmipfixingrate )
970 {
971 SCIP_Bool success;
972
973 SCIPdebugMsg(scip, "solving subproblem: nstallnodes=%" SCIP_LONGINT_FORMAT ", maxnodes=%" SCIP_LONGINT_FORMAT "\n", nstallnodes, heurdata->maxnodes);
974
975 SCIP_CALL_ABORT( SCIPsolve(subscip) );
976 SCIPdebug( SCIP_CALL( SCIPprintStatistics(subscip, NULL) ) );
977
978 SCIPdebugMsg(scip, "ending solving clique-submip at time %g, status = %d\n", SCIPgetSolvingTime(scip), SCIPgetStatus(subscip));
979
980 /* check, whether a solution was found; due to numerics, it might happen that not all solutions are feasible ->
981 * try all solutions until one was accepted
982 */
983 SCIP_CALL( SCIPtranslateSubSols(scip, subscip, heur, subvars, &success, NULL) );
984 if( success )
985 *result = SCIP_FOUNDSOL;
986
987 #ifndef NOCONFLICT
988 /* if subscip was infeasible, add a conflict */
989 if( SCIPgetStatus(subscip) == SCIP_STATUS_INFEASIBLE )
990 {
991 /* create own conflict */
992 (void) SCIPsnprintf(consname, SCIP_MAXSTRLEN, "conf%" SCIP_LONGINT_FORMAT "", SCIPgetNNodes(scip));
993
994 /* get variables for the conflict */
995 for( i = 0; i < nonefixvars; ++i )
996 {
997 /* if the variable was fixed to 1 by the heuristic, get its negated variable */
998 if( onefixvals[i] )
999 {
1000 SCIP_CALL( SCIPgetNegatedVar(scip, onefixvars[i], &onefixvars[i]) );
1001 }
1002 }
1003
1004 /* create conflict constraint */
1005 SCIP_CALL( SCIPcreateConsLogicor(scip, &conflictcons, consname, nonefixvars, onefixvars,
1006 FALSE, TRUE, FALSE, FALSE, TRUE, TRUE, FALSE, TRUE, TRUE, FALSE) );
1007 SCIP_CALL( SCIPaddConsNode(scip, SCIPgetFocusNode(scip), conflictcons, NULL) );
1008 SCIPdebugPrintCons(scip, conflictcons, NULL);
1009 SCIP_CALL( SCIPreleaseCons(scip, &conflictcons) );
1010 }
1011 #endif
1012 }
1013
1014 #ifdef SCIP_DEBUG
1015 SCIP_CALL( SCIPprintStatistics(subscip, NULL) );
1016 #endif
1017
1018 /* free subproblem */
1019 SCIPfreeBufferArray(scip, &subvars);
1020 SCIP_CALL( SCIPfree(&subscip) );
1021 }
1022
1023 /*************************** End Subscip Solving ***************************/
1024
1025 TERMINATE:
1026
1027 /* reset the conflict analysis */
1028 if( !SCIPisParamFixed(scip, "conflict/enable") )
1029 {
1030 SCIP_CALL( SCIPsetBoolParam(scip, "conflict/enable", enabledconflicts) );
1031 }
1032
1033 /* free conflict variables */
1034 SCIPfreeBufferArrayNull(scip, &onefixvals);
1035 SCIPfreeBufferArrayNull(scip, &onefixvars);
1036
1037 /* end probing */
1038 if( SCIPinProbing(scip) )
1039 {
1040 SCIP_CALL( SCIPendProbing(scip) );
1041 }
1042
1043 return SCIP_OKAY;
1044 }
1045
1046 /*
1047 * primal heuristic specific interface methods
1048 */
1049
1050 /** creates the clique primal heuristic and includes it in SCIP */
1051 SCIP_RETCODE SCIPincludeHeurClique(
1052 SCIP* scip /**< SCIP data structure */
1053 )
1054 {
1055 SCIP_HEURDATA* heurdata;
1056 SCIP_HEUR* heur;
1057
1058 /* create clique primal heuristic data */
1059 SCIP_CALL( SCIPallocBlockMemory(scip, &heurdata) );
1060
1061 /* include primal heuristic */
1062 SCIP_CALL( SCIPincludeHeurBasic(scip, &heur,
1063 HEUR_NAME, HEUR_DESC, HEUR_DISPCHAR, HEUR_PRIORITY, HEUR_FREQ, HEUR_FREQOFS,
1064 HEUR_MAXDEPTH, HEUR_TIMING, HEUR_USESSUBSCIP, heurExecClique, heurdata) );
1065
1066 assert(heur != NULL);
1067
1068 /* set non-NULL pointers to callback methods */
1069 SCIP_CALL( SCIPsetHeurCopy(scip, heur, heurCopyClique) );
1070 SCIP_CALL( SCIPsetHeurFree(scip, heur, heurFreeClique) );
1071 SCIP_CALL( SCIPsetHeurInit(scip, heur, heurInitClique) );
1072
1073 /* add clique primal heuristic parameters */
1074
1075 SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/minintfixingrate",
1076 "minimum percentage of integer variables that have to be fixable",
1077 &heurdata->minintfixingrate, FALSE, DEFAULT_MININTFIXINGRATE, 0.0, 1.0, NULL, NULL) );
1078
1079 SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/minmipfixingrate",
1080 "minimum percentage of fixed variables in the sub-MIP",
1081 &heurdata->minmipfixingrate, FALSE, DEFAULT_MINMIPFIXINGRATE, 0.0, 1.0, NULL, NULL) );
1082
1083 SCIP_CALL( SCIPaddLongintParam(scip, "heuristics/" HEUR_NAME "/maxnodes",
1084 "maximum number of nodes to regard in the subproblem",
1085 &heurdata->maxnodes, TRUE, DEFAULT_MAXNODES, 0LL, SCIP_LONGINT_MAX, NULL, NULL) );
1086
1087 SCIP_CALL( SCIPaddLongintParam(scip, "heuristics/" HEUR_NAME "/nodesofs",
1088 "number of nodes added to the contingent of the total nodes",
1089 &heurdata->nodesofs, FALSE, DEFAULT_NODESOFS, 0LL, SCIP_LONGINT_MAX, NULL, NULL) );
1090
1091 SCIP_CALL( SCIPaddLongintParam(scip, "heuristics/" HEUR_NAME "/minnodes",
1092 "minimum number of nodes required to start the subproblem",
1093 &heurdata->minnodes, TRUE, DEFAULT_MINNODES, 0LL, SCIP_LONGINT_MAX, NULL, NULL) );
1094
1095 SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/nodesquot",
1096 "contingent of sub problem nodes in relation to the number of nodes of the original problem",
1097 &heurdata->nodesquot, FALSE, DEFAULT_NODESQUOT, 0.0, 1.0, NULL, NULL) );
1098
1099 SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/minimprove",
1100 "factor by which " HEUR_NAME " heuristic should at least improve the incumbent",
1101 &heurdata->minimprove, TRUE, DEFAULT_MINIMPROVE, 0.0, 1.0, NULL, NULL) );
1102
1103 SCIP_CALL( SCIPaddIntParam(scip, "heuristics/" HEUR_NAME "/maxproprounds",
1104 "maximum number of propagation rounds during probing (-1 infinity)",
1105 &heurdata->maxproprounds, TRUE, DEFAULT_MAXPROPROUNDS, -1, INT_MAX/4, NULL, NULL) );
1106
1107 SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/copycuts",
1108 "should all active cuts from cutpool be copied to constraints in subproblem?",
1109 &heurdata->copycuts, TRUE, DEFAULT_COPYCUTS, NULL, NULL) );
1110
1111 SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/uselockfixings",
1112 "should more variables be fixed based on variable locks if the fixing rate was not reached?",
1113 &heurdata->uselockfixings, TRUE, DEFAULT_USELOCKFIXINGS, NULL, NULL) );
1114
1115 SCIP_CALL( SCIPaddIntParam(scip, "heuristics/" HEUR_NAME "/maxbacktracks",
1116 "maximum number of backtracks during the fixing process",
1117 &heurdata->maxbacktracks, TRUE, DEFAULT_MAXBACKTRACKS, -1, INT_MAX/4, NULL, NULL) );
1118
1119 return SCIP_OKAY;
1120 }
1121