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