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-2022 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
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
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,
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 */
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  {
648  goto TERMINATE;
649  }
650 
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 */
662 
663 #ifdef COLLECTSTATISTICS
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  {
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",
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");
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,
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 */
918 
919  /* disable expensive presolving */
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;
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) );
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  {
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 */
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,
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 }
#define DEFAULT_MINMIPFIXINGRATE
Definition: heur_clique.c:79
#define DEFAULT_MININTFIXINGRATE
Definition: heur_clique.c:78
SCIP_RETCODE SCIPlinkLPSol(SCIP *scip, SCIP_SOL *sol)
Definition: scip_sol.c:1017
SCIP_Real SCIPgetSolvingTime(SCIP *scip)
Definition: scip_timing.c:369
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:949
#define HEUR_TIMING
Definition: heur_clique.c:74
#define DEFAULT_MAXNODES
Definition: heur_clique.c:77
SCIP_VAR ** SCIPcliqueGetVars(SCIP_CLIQUE *clique)
Definition: implics.c:3368
public methods for SCIP parameter handling
SCIP_NODE * SCIPgetCurrentNode(SCIP *scip)
Definition: scip_tree.c:82
SCIP_RETCODE SCIPbacktrackProbing(SCIP *scip, int probingdepth)
Definition: scip_probing.c:216
SCIP_Longint SCIPgetNLPIterations(SCIP *scip)
public methods for memory management
#define HEUR_FREQ
Definition: heur_clique.c:71
int SCIPgetProbingDepth(SCIP *scip)
Definition: scip_probing.c:189
#define SCIPallocClearBufferArray(scip, ptr, num)
Definition: scip_mem.h:117
public methods for implications, variable bounds, and cliques
#define HEUR_MAXDEPTH
Definition: heur_clique.c:73
#define SCIP_MAXSTRLEN
Definition: def.h:293
static int getCliqueUnfixedVars(SCIP_CLIQUE *clique)
Definition: heur_clique.c:138
SCIP_Longint SCIPheurGetNBestSolsFound(SCIP_HEUR *heur)
Definition: heur.c:1587
static SCIP_DECL_HEURFREE(heurFreeClique)
Definition: heur_clique.c:525
static SCIP_DECL_HEUREXEC(heurExecClique)
Definition: heur_clique.c:565
SCIP_Real SCIPvarGetLbLocal(SCIP_VAR *var)
Definition: var.c:17966
int SCIPgetNPseudoBranchCands(SCIP *scip)
Definition: scip_branch.c:749
public solving methods
public methods for timing
#define HEUR_DESC
Definition: heur_clique.c:68
SCIP_RETCODE SCIPgetVarsData(SCIP *scip, SCIP_VAR ***vars, int *nvars, int *nbinvars, int *nintvars, int *nimplvars, int *ncontvars)
Definition: scip_prob.c:1865
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:165
#define FALSE
Definition: def.h:87
SCIP_RETCODE SCIPhashmapCreate(SCIP_HASHMAP **hashmap, BMS_BLKMEM *blkmem, int mapsize)
Definition: misc.c:3014
#define DEFAULT_NODESQUOT
Definition: heur_clique.c:87
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:102
SCIP_RETCODE SCIPcopyLimits(SCIP *sourcescip, SCIP *targetscip)
Definition: scip_copy.c:3278
SCIP_RETCODE SCIPcutoffNode(SCIP *scip, SCIP_NODE *node)
Definition: scip_tree.c:425
SCIP_Real SCIPinfinity(SCIP *scip)
int SCIPsnprintf(char *t, int len, const char *s,...)
Definition: misc.c:10755
#define TRUE
Definition: def.h:86
#define SCIPdebug(x)
Definition: pub_message.h:84
SCIP_RETCODE SCIPapplyLockFixings(SCIP *scip, SCIP_HEURDATA *heurdata, SCIP_Bool *cutoff, SCIP_Bool *allrowsfulfilled)
Definition: heur_locks.c:187
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:54
SCIP_RETCODE SCIPsetPresolving(SCIP *scip, SCIP_PARAMSETTING paramsetting, SCIP_Bool quiet)
Definition: scip_param.c:923
SCIP_BRANCHRULE * SCIPfindBranchrule(SCIP *scip, const char *name)
Definition: scip_branch.c:288
#define DEFAULT_MAXPROPROUNDS
Definition: heur_clique.c:88
struct SCIP_HeurData SCIP_HEURDATA
Definition: type_heur.h:67
public methods for problem variables
#define SCIPfreeBlockMemory(scip, ptr)
Definition: scip_mem.h:99
SCIP_RETCODE SCIPincludeHeurBasic(SCIP *scip, SCIP_HEUR **heur, const char *name, const char *desc, char dispchar, int priority, int freq, int freqofs, int maxdepth, SCIP_HEURTIMING timingmask, SCIP_Bool usessubscip, SCIP_DECL_HEUREXEC((*heurexec)), SCIP_HEURDATA *heurdata)
Definition: scip_heur.c:108
#define HEUR_FREQOFS
Definition: heur_clique.c:72
SCIP_RETCODE SCIPtranslateSubSols(SCIP *scip, SCIP *subscip, SCIP_HEUR *heur, SCIP_VAR **subvars, SCIP_Bool *success, int *solindex)
Definition: scip_copy.c:1439
#define DEFAULT_MAXBACKTRACKS
Definition: heur_clique.c:89
void * SCIPhashmapGetImage(SCIP_HASHMAP *hashmap, void *origin)
Definition: misc.c:3201
SCIP_RETCODE SCIPconstructLP(SCIP *scip, SCIP_Bool *cutoff)
Definition: scip_lp.c:115
#define SCIP_LONGINT_MAX
Definition: def.h:163
#define SCIPfreeBufferArray(scip, ptr)
Definition: scip_mem.h:127
enum SCIP_LPSolStat SCIP_LPSOLSTAT
Definition: type_lp.h:42
SCIP_RETCODE SCIPcreate(SCIP **scip)
Definition: scip_general.c:283
void SCIPheurSetData(SCIP_HEUR *heur, SCIP_HEURDATA *heurdata)
Definition: heur.c:1362
#define SCIPdebugPrintCons(x, y, z)
Definition: pub_message.h:93
public methods for SCIP variables
void SCIPwarningMessage(SCIP *scip, const char *formatstr,...)
Definition: scip_message.c:111
#define SCIPdebugMsg
Definition: scip_message.h:69
SCIP_RETCODE SCIPaddIntParam(SCIP *scip, const char *name, const char *desc, int *valueptr, SCIP_Bool isadvanced, int defaultvalue, int minvalue, int maxvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition: scip_param.c:74
SCIP_RETCODE SCIPprintStatistics(SCIP *scip, FILE *file)
#define DEFAULT_MINNODES
Definition: heur_clique.c:85
public methods for numerical tolerances
public methods for querying solving statistics
public methods for the branch-and-bound tree
SCIP_Bool SCIPisLPConstructed(SCIP *scip)
Definition: scip_lp.c:92
SCIP_Bool SCIPisLPSolBasic(SCIP *scip)
Definition: scip_lp.c:658
#define HEUR_DISPCHAR
Definition: heur_clique.c:69
SCIP_RETCODE SCIPsolve(SCIP *scip)
Definition: scip_solve.c:2613
const char * SCIPheurGetName(SCIP_HEUR *heur)
Definition: heur.c:1441
SCIP_RETCODE SCIPincludeHeurClique(SCIP *scip)
Definition: heur_clique.c:1055
SCIP_Bool SCIPisParamFixed(SCIP *scip, const char *name)
Definition: scip_param.c:210
SCIP_RETCODE SCIPsetHeurFree(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURFREE((*heurfree)))
Definition: scip_heur.c:169
SCIP_RETCODE SCIPpropagateProbing(SCIP *scip, int maxproprounds, SCIP_Bool *cutoff, SCIP_Longint *ndomredsfound)
Definition: scip_probing.c:571
SCIP_RETCODE SCIPfixVarProbing(SCIP *scip, SCIP_VAR *var, SCIP_Real fixedval)
Definition: scip_probing.c:409
Constraint handler for logicor constraints (equivalent to set covering, but algorithms are suited fo...
#define HEUR_USESSUBSCIP
Definition: heur_clique.c:75
#define SCIPfreeBufferArrayNull(scip, ptr)
Definition: scip_mem.h:128
SCIP_RETCODE SCIPsetBoolParam(SCIP *scip, const char *name, SCIP_Bool value)
Definition: scip_param.c:420
SCIP_STATUS SCIPgetStatus(SCIP *scip)
Definition: scip_general.c:474
SCIP_RETCODE SCIPpresolve(SCIP *scip)
Definition: scip_solve.c:2443
SCIP_RETCODE SCIPcopyCuts(SCIP *sourcescip, SCIP *targetscip, SCIP_HASHMAP *varmap, SCIP_HASHMAP *consmap, SCIP_Bool global, int *ncutsadded)
Definition: scip_copy.c:2116
BMS_BLKMEM * SCIPblkmem(SCIP *scip)
Definition: scip_mem.c:48
SCIP_RETCODE SCIPendProbing(SCIP *scip)
Definition: scip_probing.c:251
const char * SCIPvarGetName(SCIP_VAR *var)
Definition: var.c:17251
void SCIPhashmapFree(SCIP_HASHMAP **hashmap)
Definition: misc.c:3048
char * SCIPsnprintfProbingStats(SCIP *scip, char *strbuf, int len)
SCIP_RETCODE SCIPgetBoolParam(SCIP *scip, const char *name, SCIP_Bool *value)
Definition: scip_param.c:241
#define NULL
Definition: lpi_spx1.cpp:155
#define SCIP_Shortbool
Definition: def.h:92
#define DEFAULT_USELOCKFIXINGS
Definition: heur_clique.c:93
public methods for problem copies
int SCIPgetNUnfixedLPCols(SCIP *scip)
Definition: scip_lp.c:539
#define SCIP_CALL(x)
Definition: def.h:384
SCIP_Real SCIPgetLowerbound(SCIP *scip)
SCIP_RETCODE SCIPsolveProbingLP(SCIP *scip, int itlim, SCIP_Bool *lperror, SCIP_Bool *cutoff)
Definition: scip_probing.c:810
#define DEFAULT_MINIMPROVE
Definition: heur_clique.c:82
void SCIPverbMessage(SCIP *scip, SCIP_VERBLEVEL msgverblevel, FILE *file, const char *formatstr,...)
Definition: scip_message.c:216
SCIP_Longint SCIPheurGetNCalls(SCIP_HEUR *heur)
Definition: heur.c:1567
SCIP_Bool SCIPhasCurrentNodeLP(SCIP *scip)
Definition: scip_lp.c:74
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:3322
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 threadsafe, SCIP_Bool passmessagehdlr, SCIP_Bool *valid)
Definition: scip_copy.c:2951
#define SCIPallocBufferArray(scip, ptr, num)
Definition: scip_mem.h:115
public data structures and miscellaneous methods
#define DEFAULT_NODESOFS
Definition: heur_clique.c:86
#define SCIP_Bool
Definition: def.h:84
SCIP_LPSOLSTAT SCIPgetLPSolstat(SCIP *scip)
Definition: scip_lp.c:159
SCIP_RETCODE SCIProundSol(SCIP *scip, SCIP_SOL *sol, SCIP_Bool *success)
Definition: scip_sol.c:2446
SCIP_RETCODE SCIPsetObjlimit(SCIP *scip, SCIP_Real objlimit)
Definition: scip_prob.c:1421
int SCIPgetDepth(SCIP *scip)
Definition: scip_tree.c:661
SCIP_Bool * SCIPcliqueGetValues(SCIP_CLIQUE *clique)
Definition: implics.c:3380
SCIP_RETCODE SCIPsetIntParam(SCIP *scip, const char *name, int value)
Definition: scip_param.c:478
SCIP_RETCODE SCIPfreeSol(SCIP *scip, SCIP_SOL **sol)
Definition: scip_sol.c:976
void SCIPenableVarHistory(SCIP *scip)
Definition: scip_var.c:8738
SCIP_Real SCIPvarGetObj(SCIP_VAR *var)
Definition: var.c:17758
int SCIPgetNSols(SCIP *scip)
Definition: scip_sol.c:2205
static SCIP_DECL_SORTINDCOMP(compCliquesSize)
Definition: heur_clique.c:130
SCIP_Real SCIPgetSolOrigObj(SCIP *scip, SCIP_SOL *sol)
Definition: scip_sol.c:1435
SCIP_RETCODE SCIPflushLP(SCIP *scip)
Definition: scip_lp.c:139
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:3125
SCIP_NODE * SCIPgetFocusNode(SCIP *scip)
Definition: scip_tree.c:63
#define SCIP_MAXTREEDEPTH
Definition: def.h:320
int SCIPgetNBinVars(SCIP *scip)
Definition: scip_prob.c:2036
SCIP_Bool SCIPinProbing(SCIP *scip)
Definition: scip_probing.c:88
public methods for the LP relaxation, rows and columns
int SCIPgetNVars(SCIP *scip)
Definition: scip_prob.c:1991
methods for sorting joint arrays of various types
SCIP_CLIQUE ** SCIPgetCliques(SCIP *scip)
Definition: scip_var.c:7626
public methods for branching rule plugins and branching
general public methods
SCIP_Real SCIPgetLPObjval(SCIP *scip)
Definition: scip_lp.c:238
void SCIPsort(int *perm, SCIP_DECL_SORTINDCOMP((*indcomp)), void *dataptr, int len)
Definition: misc.c:5440
public methods for solutions
int SCIPgetNConss(SCIP *scip)
Definition: scip_prob.c:3041
public methods for the probing mode
SCIP_RETCODE SCIPreleaseCons(SCIP *scip, SCIP_CONS **cons)
Definition: scip_cons.c:1110
#define HEUR_NAME
Definition: heur_clique.c:67
public methods for message output
int SCIPgetNCliques(SCIP *scip)
Definition: scip_var.c:7572
SCIP_RETCODE SCIPsetHeurInit(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURINIT((*heurinit)))
Definition: scip_heur.c:185
#define SCIP_Real
Definition: def.h:177
SCIP_Bool SCIPisStopped(SCIP *scip)
Definition: scip_general.c:694
public methods for message handling
#define HEUR_PRIORITY
Definition: heur_clique.c:70
#define SCIP_Longint
Definition: def.h:162
SCIP_Bool SCIPallColsInLP(SCIP *scip)
Definition: scip_lp.c:640
static SCIP_DECL_HEURINIT(heurInitClique)
Definition: heur_clique.c:546
SCIP_RETCODE SCIPcheckCopyLimits(SCIP *sourcescip, SCIP_Bool *success)
Definition: scip_copy.c:3235
#define DEFAULT_COPYCUTS
Definition: heur_clique.c:90
int SCIPgetNLPCols(SCIP *scip)
Definition: scip_lp.c:518
SCIP_RETCODE SCIPsetHeurCopy(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURCOPY((*heurcopy)))
Definition: scip_heur.c:153
SCIP_Real SCIPvarGetUbLocal(SCIP_VAR *var)
Definition: var.c:17976
SCIP_RETCODE SCIPnewProbingNode(SCIP *scip)
Definition: scip_probing.c:156
int SCIPcliqueGetNVars(SCIP_CLIQUE *clique)
Definition: implics.c:3358
SCIP_Real SCIPsumepsilon(SCIP *scip)
SCIP_Real SCIPgetUpperbound(SCIP *scip)
SCIP_RETCODE SCIPstartProbing(SCIP *scip)
Definition: scip_probing.c:110
public methods for primal heuristics
SCIPallocBlockMemory(scip, subsol))
SCIP_RETCODE SCIPaddConflict(SCIP *scip, SCIP_NODE *node, SCIP_CONS *cons, SCIP_NODE *validnode, SCIP_CONFTYPE conftype, SCIP_Bool iscutoffinvolved)
Definition: scip_prob.c:3227
#define SCIP_CALL_ABORT(x)
Definition: def.h:363
SCIP_HEURDATA * SCIPheurGetData(SCIP_HEUR *heur)
Definition: heur.c:1352
SCIP_Longint SCIPgetNNodes(SCIP *scip)
public methods for global and local (sub)problems
static SCIP_DECL_HEURCOPY(heurCopyClique)
Definition: heur_clique.c:511
SCIP_RETCODE SCIPaddRealParam(SCIP *scip, const char *name, const char *desc, SCIP_Real *valueptr, SCIP_Bool isadvanced, SCIP_Real defaultvalue, SCIP_Real minvalue, SCIP_Real maxvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition: scip_param.c:130
SCIP_RETCODE SCIPsetSubscipsOff(SCIP *scip, SCIP_Bool quiet)
Definition: scip_param.c:874
SCIP_RETCODE SCIPsetLongintParam(SCIP *scip, const char *name, SCIP_Longint value)
Definition: scip_param.c:536
SCIP_RETCODE SCIPgetNegatedVar(SCIP *scip, SCIP_VAR *var, SCIP_VAR **negvar)
Definition: scip_var.c:1524
SCIP_RETCODE SCIPaddBoolParam(SCIP *scip, const char *name, const char *desc, SCIP_Bool *valueptr, SCIP_Bool isadvanced, SCIP_Bool defaultvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition: scip_param.c:48
SCIP_RETCODE SCIPfree(SCIP **scip)
Definition: scip_general.c:315
SCIP_RETCODE SCIPcreateSol(SCIP *scip, SCIP_SOL **sol, SCIP_HEUR *heur)
Definition: scip_sol.c:319
memory allocation routines
SCIP_RETCODE SCIPprintSol(SCIP *scip, SCIP_SOL *sol, FILE *file, SCIP_Bool printzeros)
Definition: scip_sol.c:1766