Scippy

SCIP

Solving Constraint Integer Programs

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