Scippy

SCIP

Solving Constraint Integer Programs

heur_locks.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-2020 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_locks.c
17  * @ingroup DEFPLUGINS_HEUR
18  * @brief rounding locks primal heuristic
19  * @author Michael Winkler
20  * @author Gerald Gamrath
21  */
22 
23 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
24 
25 #include "blockmemshell/memory.h"
26 #include "scip/heur_locks.h"
27 #include "scip/pub_cons.h"
28 #include "scip/pub_heur.h"
29 #include "scip/pub_lp.h"
30 #include "scip/pub_message.h"
31 #include "scip/pub_misc.h"
32 #include "scip/pub_var.h"
33 #include "scip/scip_branch.h"
34 #include "scip/scip_cons.h"
35 #include "scip/scip_copy.h"
36 #include "scip/scip_general.h"
37 #include "scip/scip_heur.h"
38 #include "scip/scip_lp.h"
39 #include "scip/scip_mem.h"
40 #include "scip/scip_message.h"
41 #include "scip/scip_numerics.h"
42 #include "scip/scip_param.h"
43 #include "scip/scip_prob.h"
44 #include "scip/scip_probing.h"
45 #include "scip/scip_randnumgen.h"
46 #include "scip/scip_sol.h"
47 #include "scip/scip_solve.h"
48 #include "scip/scip_solvingstats.h"
49 #include "scip/scip_timing.h"
50 #include "scip/scip_tree.h"
51 #include <string.h>
52 
53 #define HEUR_NAME "locks"
54 #define HEUR_DESC "heuristic that fixes variables based on their rounding locks"
55 #define HEUR_DISPCHAR SCIP_HEURDISPCHAR_PROP
56 #define HEUR_PRIORITY 3000
57 #define HEUR_FREQ 0
58 #define HEUR_FREQOFS 0
59 #define HEUR_MAXDEPTH -1
60 #define HEUR_TIMING SCIP_HEURTIMING_BEFORENODE
61 #define HEUR_USESSUBSCIP TRUE /**< does the heuristic use a secondary SCIP instance? */
62 
63 #define DEFAULT_MAXNODES 5000LL /**< maximum number of nodes to regard in the subproblem */
64 #define DEFAULT_ROUNDUPPROBABILITY 0.67 /**< probability for rounding a variable up in case of ties */
65 #define DEFAULT_MINFIXINGRATE 0.65 /**< minimum percentage of variables that have to be fixed */
66 #define DEFAULT_MINIMPROVE 0.01 /**< factor by which locks heuristic should at least improve the
67  * incumbent */
68 #define DEFAULT_MINNODES 500LL /**< minimum number of nodes to regard in the subproblem */
69 #define DEFAULT_NODESOFS 500LL /**< number of nodes added to the contingent of the total nodes */
70 #define DEFAULT_NODESQUOT 0.1 /**< subproblem nodes in relation to nodes of the original problem */
71 #define DEFAULT_MAXPROPROUNDS 2 /**< maximum number of propagation rounds during probing */
72 #define DEFAULT_UPDATELOCKS TRUE /**< should the locks be updated based on LP rows? */
73 #define DEFAULT_COPYCUTS TRUE /**< should all active cuts from the cutpool of the
74  * original scip be copied to constraints of the subscip? */
75 #define DEFAULT_USEFINALSUBMIP TRUE /**< should a final sub-MIP be solved to construct a feasible
76  * solution if the LP was not roundable? */
77 #define DEFAULT_RANDSEED 73 /**< initial random seed */
78 #define DEFAULT_MINFIXINGRATELP 0.0 /**< minimum fixing rate over all variables (including continuous)
79  * to solve LP */
80 
81 /** primal heuristic data */
82 struct SCIP_HeurData
83 {
84  SCIP_RANDNUMGEN* randnumgen; /**< random number generation */
85  SCIP_Longint maxnodes; /**< maximum number of nodes to regard in the subproblem */
86  SCIP_Longint minnodes; /**< minimum number of nodes to regard in the subproblem */
87  SCIP_Longint nodesofs; /**< number of nodes added to the contingent of the total nodes */
88  SCIP_Longint usednodes; /**< nodes already used by locks heuristic in earlier calls */
89  SCIP_Real roundupprobability; /**< probability for rounding a variable up in case of ties */
90  SCIP_Real minfixingrate; /**< minimum percentage of variables that have to be fixed */
91  SCIP_Real minfixingratelp; /**< minimum fixing rate over all variables (including continuous) to solve LP */
92  SCIP_Real minimprove; /**< factor by which locks heuristic should at least improve the incumbent */
93  SCIP_Real nodesquot; /**< subproblem nodes in relation to nodes of the original problem */
94  int maxproprounds; /**< maximum number of propagation rounds during probing */
95  SCIP_Bool updatelocks; /**< should the locks be updated based on LP rows? */
96  SCIP_Bool copycuts; /**< should all active cuts from cutpool be copied to constraints in
97  * the subproblem? */
98  SCIP_Bool usefinalsubmip; /**< should a final sub-MIP be solved to costruct a feasible solution if
99  * the LP was not roundable? */
100 };
101 
102 /*
103  * Local methods
104  */
105 
106 /** copy method for primal heuristic plugins (called when SCIP copies plugins) */
107 static
108 SCIP_DECL_HEURCOPY(heurCopyLocks)
109 { /*lint --e{715}*/
110  assert(scip != NULL);
111  assert(heur != NULL);
112  assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0);
113 
114  /* call inclusion method of primal heuristic */
116 
117  return SCIP_OKAY;
118 }
119 
120 /** free method for primal heuristic plugins (called when SCIP is exiting) */
121 static
122 SCIP_DECL_HEURFREE(heurFreeLocks)
123 { /*lint --e{715}*/
124  SCIP_HEURDATA* heurdata;
125 
126  assert(scip != NULL);
127  assert(heur != NULL);
128  assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0);
129 
130  heurdata = SCIPheurGetData(heur);
131 
132  /* free primal heuristic data */
133  SCIPfreeBlockMemory(scip, &heurdata);
134 
135  return SCIP_OKAY;
136 }
137 
138 /** initialization method of primal heuristic (called after problem was transformed) */
139 static
140 SCIP_DECL_HEURINIT(heurInitLocks) /*lint --e{715}*/
141 { /*lint --e{715}*/
142  SCIP_HEURDATA* heurdata;
143 
144  assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0);
145  heurdata = SCIPheurGetData(heur);
146  assert(heurdata != NULL);
147 
148  /* initialize data */
149  heurdata->usednodes = 0;
150 
151  /* create random number generator */
152  SCIP_CALL( SCIPcreateRandom(scip, &heurdata->randnumgen,
154 
155  return SCIP_OKAY;
156 }
157 
158 /** deinitialization method of primal heuristic (called before transformed problem is freed) */
159 static
160 SCIP_DECL_HEUREXIT(heurExitLocks) /*lint --e{715}*/
161 { /*lint --e{715}*/
162  SCIP_HEURDATA* heurdata;
163 
164  assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0);
165 
166  /* free heuristic data */
167  heurdata = SCIPheurGetData(heur);
168  assert(heurdata != NULL);
169 
170  /* free random number generator */
171  SCIPfreeRandom(scip, &heurdata->randnumgen);
172 
173  return SCIP_OKAY;
174 }
175 
176 #define heurInitsolLocks NULL
177 #define heurExitsolLocks NULL
178 
179 /** apply fix-and-propagate scheme based on variable locks
180  *
181  * @note probing mode of SCIP needs to be enabled before
182  */
184  SCIP* scip, /**< SCIP data structure */
185  SCIP_HEURDATA* heurdata, /**< primal heuristic data */
186  SCIP_Bool* cutoff, /**< pointer to store if a cutoff was detected */
187  SCIP_Bool* allrowsfulfilled /**< pointer to store if all rows became redundant */
188  )
189 {
190  SCIP_ROW** lprows;
191  SCIP_VAR** vars;
192  SCIP_VAR** sortvars;
193  SCIP_Real* minact;
194  SCIP_Real* maxact;
195  SCIP_Bool* fulfilled;
196  SCIP_VAR* var;
197  SCIP_ROW* row;
198  SCIP_COL* col;
199  SCIP_ROW** colrows;
200  SCIP_Real* colvals;
201  int ncolrows;
202  int* ndownlocks;
203  int* nuplocks;
204  int* varpos = NULL;
205  SCIP_Real lastfixval;
206  SCIP_Real randnumber;
207  SCIP_Real roundupprobability;
208  SCIP_Bool propagate;
209  SCIP_Bool propagated;
210  SCIP_Bool haslhs;
211  SCIP_Bool hasrhs;
212  SCIP_Bool updatelocks;
213  int lastfixlocks;
214  int maxproprounds;
215  int nglbfulfilledrows;
216  int rowpos;
217  int nbinvars;
218  int nvars;
219  int nlprows;
220  int nfulfilledrows;
221  int bestpos;
222  int lastbestscore;
223  int bestscore;
224  int score;
225  int v;
226  int r;
227  int i;
228 
229  assert(scip != NULL);
230  assert(cutoff != NULL);
231  assert(allrowsfulfilled != NULL);
232  assert(SCIPinProbing(scip));
233 
234  if( heurdata == NULL )
235  {
236  SCIP_HEUR* heur = SCIPfindHeur(scip, HEUR_NAME);
237  heurdata = SCIPheurGetData(heur);
238  }
239  assert(heurdata != NULL);
240 
241  *cutoff = FALSE;
242  *allrowsfulfilled = FALSE;
243 
244  propagate = (heurdata->maxproprounds != 0);
245 
246  if( heurdata->maxproprounds == -2 )
247  maxproprounds = 0;
248  else
249  maxproprounds = heurdata->maxproprounds;
250 
251  roundupprobability = heurdata->roundupprobability;
252 
253  updatelocks = heurdata->updatelocks && (SCIPgetNCheckConss(scip) == SCIPgetNLPRows(scip));
254 
255  SCIPdebugMsg(scip, "%d constraints: %d logicor, updatelocks=%d\n", SCIPgetNConss(scip), SCIPconshdlrGetNCheckConss(SCIPfindConshdlr(scip, "logicor")), updatelocks);
256 
257  SCIP_CALL( SCIPgetVarsData(scip, &vars, &nvars, &nbinvars, NULL, NULL, NULL) );
258  assert(vars != NULL);
259 
260  /* allocate memory */
261  SCIP_CALL( SCIPduplicateBufferArray(scip, &sortvars, vars, nbinvars) );
262  SCIP_CALL( SCIPallocBufferArray(scip, &nuplocks, nbinvars) );
263  SCIP_CALL( SCIPallocBufferArray(scip, &ndownlocks, nbinvars) );
264 
265  /* get LP data */
266  SCIP_CALL( SCIPgetLPRowsData(scip, &lprows, &nlprows) );
267  SCIP_CALL( SCIPallocBufferArray(scip, &minact, nlprows) );
268  SCIP_CALL( SCIPallocBufferArray(scip, &maxact, nlprows) );
269  SCIP_CALL( SCIPallocClearBufferArray(scip, &fulfilled, nlprows) );
270 
271  /* @todo add objective value as second sorting criteria */
272 
273  nglbfulfilledrows = 0;
274 
275  /* get locks of variables */
276  for( v = 0; v < nbinvars; ++v )
277  {
278  var = sortvars[v];
279  nuplocks[v] = SCIPvarGetNLocksUpType(var, SCIP_LOCKTYPE_MODEL);
280  ndownlocks[v] = SCIPvarGetNLocksDownType(var, SCIP_LOCKTYPE_MODEL);
281  }
282 
283  /* get activities of rows */
284  for( r = 0; r < nlprows; ++r )
285  {
286  row = lprows[r];
287  assert(SCIProwGetLPPos(row) == r);
288 
289  /* no trivial rows */
290  assert(!SCIPisInfinity(scip, -SCIProwGetLhs(row)) || !SCIPisInfinity(scip, SCIProwGetRhs(row)));
291 
292  minact[r] = SCIPgetRowMinActivity(scip, row);
293  maxact[r] = SCIPgetRowMaxActivity(scip, row);
294  }
295 
296  propagated = TRUE;
297  lastbestscore = INT_MAX;
298 
299  /* fix variables */
300  for( v = 0; v < nbinvars; v++ )
301  {
302  if( SCIPisStopped(scip) )
303  break;
304 
305  assert(!(*cutoff));
306 
307  nfulfilledrows = 0;
308 
309  while( v < nbinvars && (SCIPvarGetLbLocal(sortvars[v]) > 0.5 || SCIPvarGetUbLocal(sortvars[v]) < 0.5) )
310  {
311  ++v;
312  }
313  if( v == nbinvars )
314  break;
315 
316  bestpos = v;
317  bestscore = nuplocks[v] + ndownlocks[v];
318 
319  /* get best variable */
320  if( bestscore < lastbestscore )
321  {
322  for( i = v + 1; i < nbinvars; ++i )
323  {
324  var = sortvars[i];
325 
326  /* variable is already fixed; move it to the front and increment v to ignore it */
327  if( SCIPvarGetLbLocal(var) > 0.5 || SCIPvarGetUbLocal(var) < 0.5 )
328  {
329  int locks;
330 
331  sortvars[i] = sortvars[v];
332  sortvars[v] = var;
333 
334  locks = nuplocks[i];
335  nuplocks[i] = nuplocks[v];
336  nuplocks[v] = locks;
337 
338  locks = ndownlocks[i];
339  ndownlocks[i] = ndownlocks[v];
340  ndownlocks[v] = locks;
341 
342  if( varpos != NULL )
343  {
344  varpos[SCIPvarGetProbindex(sortvars[i])] = i;
345  varpos[SCIPvarGetProbindex(sortvars[v])] = v;
346  }
347 
348  if( bestpos == v )
349  bestpos = i;
350 
351  ++v;
352 
353  continue;
354  }
355 
356  score = nuplocks[i] + ndownlocks[i];
357  assert(score <= lastbestscore);
358 
359  if( score > bestscore )
360  {
361  bestscore = score;
362  bestpos = i;
363 
364  if( bestscore == lastbestscore )
365  break;
366  }
367  }
368  if( v == nbinvars )
369  break;
370  }
371  lastbestscore = bestscore;
372 
373  /* move best variable to the front (at position v) */
374  if( bestpos != v )
375  {
376  int locks;
377 
378  var = sortvars[bestpos];
379  sortvars[bestpos] = sortvars[v];
380  sortvars[v] = var;
381 
382  locks = nuplocks[bestpos];
383  nuplocks[bestpos] = nuplocks[v];
384  nuplocks[v] = locks;
385 
386  locks = ndownlocks[bestpos];
387  ndownlocks[bestpos] = ndownlocks[v];
388  ndownlocks[v] = locks;
389 
390  if( varpos != NULL )
391  {
392  varpos[SCIPvarGetProbindex(sortvars[bestpos])] = bestpos;
393  varpos[SCIPvarGetProbindex(sortvars[v])] = v;
394  }
395  }
396 
397  var = sortvars[v];
398 
399  /* all remaining variables are fixed, we can break the fix-and-propagate loop */
400  if( SCIPvarGetLbLocal(var) > 0.5 || SCIPvarGetUbLocal(var) < 0.5 )
401  {
402  assert(v == nbinvars);
403 
404  break;
405  }
406 
407  /* stop if we reached the depth limit */
408  if( SCIP_MAXTREEDEPTH <= SCIPgetDepth(scip) )
409  break;
410 
411  if( propagated )
412  {
413  SCIP_CALL( SCIPnewProbingNode(scip) );
414  propagated = FALSE;
415  }
416 
417  /* set variables to the bound with fewer locks, if tie choose an average value */
418  if( ndownlocks[v] > nuplocks[v] )
419  lastfixval = 1.0;
420  else if( ndownlocks[v] < nuplocks[v] )
421  lastfixval = 0.0;
422  else
423  {
424  /* prefer one-fixing if objective value is not positive */
425  if( !SCIPisPositive(scip, SCIPvarGetObj(var)) )
426  lastfixval = 1.0;
427  else
428  {
429  randnumber = SCIPrandomGetReal(heurdata->randnumgen, 0.0, 1.0);
430 
431  /* if a tie occurs, we randomly round the variable based on the parameter 'roundupprobability' */
432  if( randnumber < roundupprobability )
433  lastfixval = 1.0;
434  else
435  lastfixval = 0.0;
436  }
437  }
438 
439  lastfixlocks = lastfixval > 0.5 ? nuplocks[v] : ndownlocks[v];
440 
441  SCIP_CALL( SCIPfixVarProbing(scip, var, lastfixval) );
442 
443  SCIPdebugMsg(scip, "iteration %d: fixing variable <%s> to %d with locks (%d, %d)\n", v, SCIPvarGetName(var), lastfixval > 0.5 ? 1 : 0, ndownlocks[v], nuplocks[v]);
444 
445  if( propagate && lastfixlocks > 0 )
446  {
447  /* apply propagation */
448  SCIP_CALL( SCIPpropagateProbing(scip, maxproprounds, cutoff, NULL) );
449  propagated = TRUE;
450 
451  if( *cutoff )
452  {
453  SCIPdebugMsg(scip, "last fixing led to infeasibility trying other bound\n");
454 
455  /* fix cutoff variable in other direction */
457  *cutoff = FALSE;
458 
459  if( lastfixval < 0.5 )
460  {
461  lastfixval = 1.0;
462 
463  if( SCIPvarGetUbLocal(var) > 0.5 )
464  {
465  SCIP_CALL( SCIPfixVarProbing(scip, var, 1.0) );
466  }
467  /* because of the limited number of propagation rounds, it may happen that conflict analysis finds a
468  * valid global fixing for the last fixed variable that conflicts with applying the reverse fixing
469  * after backtracking; in that case, we ran into a deadend and stop
470  */
471  else
472  *cutoff = TRUE;
473  }
474  else
475  {
476  lastfixval = 0.0;
477 
478  if( SCIPvarGetLbLocal(var) < 0.5 )
479  {
480  SCIP_CALL( SCIPfixVarProbing(scip, var, 0.0) );
481  }
482  /* because of the limited number of propagation rounds, it may happen that conflict analysis finds a
483  * valid global fixing for the last fixed variable that conflicts with applying the reverse fixing
484  * after backtracking; in that case, we ran into a deadend and stop
485  */
486  else
487  *cutoff = TRUE;
488  }
489 
490  if( !(*cutoff) )
491  {
492  SCIP_CALL( SCIPpropagateProbing(scip, maxproprounds, cutoff, NULL) );
493  }
494  if( *cutoff )
495  {
496  SCIPdebugMsg(scip, "probing was infeasible\n");
497 
498  break;
499  }
500  }
501  /* @todo collect propagated bounds and use them to update row activities as well */
502  }
503 
504  if( updatelocks )
505  {
507  continue;
508 
509  col = SCIPvarGetCol(var);
510  assert(col != NULL);
511 
512  colrows = SCIPcolGetRows(col);
513  colvals = SCIPcolGetVals(col);
514  ncolrows = SCIPcolGetNNonz(col);
515 
516  /* update activities */
517  for( r = 0; r < ncolrows; ++r )
518  {
519  row = colrows[r];
520  rowpos = SCIProwGetLPPos(row);
521 
522  /* the row is not in the LP */
523  if( rowpos == -1 )
524  continue;
525 
526  assert(lprows[rowpos] == row);
527 
528  /* we disregard cuts */
529  if( SCIProwGetRank(row) > 0 )
530  continue;
531 
532  /* the row is already fulfilled */
533  if( fulfilled[rowpos] )
534  continue;
535 
536  haslhs = !SCIPisInfinity(scip, -SCIProwGetLhs(row));
537  hasrhs = !SCIPisInfinity(scip, SCIProwGetRhs(row));
538 
539  /* no trivial rows */
540  assert(hasrhs || haslhs);
541 
542  if( ((colvals[r] > 0) == (lastfixval < 0.5)) )
543  {
544  maxact[rowpos] -= REALABS(colvals[r]);
545  }
546  if( ((colvals[r] > 0) == (lastfixval > 0.5)) )
547  {
548  minact[rowpos] += REALABS(colvals[r]);
549  }
550 
551  /* check if the row cannot be violated anymore */
552  if( (!haslhs || SCIPisFeasGE(scip, minact[rowpos], SCIProwGetLhs(row)))
553  && (!hasrhs || SCIPisFeasLE(scip, maxact[rowpos], SCIProwGetRhs(row))) )
554  {
555  SCIP_COL** cols;
556  SCIP_VAR* colvar;
557  SCIP_Real* vals;
558  int ncols;
559  int pos;
560  int w;
561 
562  SCIPdebugMsg(scip, "Row <%s> has activity [%g, %g], lhs=%g, rhs=%g\n", SCIProwGetName(row), minact[rowpos], maxact[rowpos], SCIProwGetLhs(row), SCIProwGetRhs(row));
563  SCIPdebug( SCIP_CALL( SCIPprintRow(scip, row, NULL) ) );
564 
565  if( varpos == NULL )
566  {
567  SCIP_CALL( SCIPallocBufferArray(scip, &varpos, nbinvars) );
568 
569  for( pos = 0; pos < nbinvars; ++pos )
570  varpos[SCIPvarGetProbindex(sortvars[pos])] = pos;
571  }
572 
573  ++nfulfilledrows;
574  fulfilled[rowpos] = TRUE;
575  cols = SCIProwGetCols(row);
576  vals = SCIProwGetVals(row);
577  ncols = SCIProwGetNNonz(row);
578 
579  /* we assume that all rows are locking the variables */
580  for( w = ncols - 1; w >= 0; --w )
581  {
582  colvar = SCIPcolGetVar(cols[w]);
583  if( SCIPvarGetType(colvar) == SCIP_VARTYPE_BINARY && colvar != var )
584  {
585  assert(sortvars[varpos[SCIPvarGetProbindex(colvar)]] == colvar);
586  pos = varpos[SCIPvarGetProbindex(colvar)];
587 
588  if( haslhs )
589  {
590  if( vals[w] > 0.0 )
591  --(ndownlocks[pos]);
592  else
593  --(nuplocks[pos]);
594  }
595  if( hasrhs )
596  {
597  if( vals[w] > 0.0 )
598  --(nuplocks[pos]);
599  else
600  --(ndownlocks[pos]);
601  }
602  }
603  }
604 
605  continue;
606  }
607  else if( SCIPisFeasLT(scip, maxact[rowpos], SCIProwGetLhs(row)) || SCIPisFeasGT(scip, minact[rowpos], SCIProwGetRhs(row)) )
608  {
609  *cutoff = TRUE;
610  break;
611  }
612  }
613 
614  if( *cutoff )
615  {
616  SCIPdebugMsg(scip, "found infeasible row, stopping heur\n");
617  break;
618  }
619 
620  nglbfulfilledrows += nfulfilledrows;
621  SCIPdebugMsg(scip, "last fixing led to %d fulfilled rows, now %d of %d rows are fulfilled\n", nfulfilledrows, nglbfulfilledrows, nlprows);
622 
623  if( nglbfulfilledrows == nlprows )
624  {
625  *allrowsfulfilled = TRUE;
626  break;
627  }
628  }
629  } /*lint --e{850}*/
630 
631  SCIPfreeBufferArrayNull(scip, &varpos);
632  SCIPfreeBufferArray(scip, &fulfilled);
633  SCIPfreeBufferArray(scip, &maxact);
634  SCIPfreeBufferArray(scip, &minact);
635  SCIPfreeBufferArray(scip, &ndownlocks);
636  SCIPfreeBufferArray(scip, &nuplocks);
637  SCIPfreeBufferArray(scip, &sortvars);
638 
639  return SCIP_OKAY;
640 }
641 
642 
643 
644 
645 /** execution method of primal heuristic */
646 static
647 SCIP_DECL_HEUREXEC(heurExecLocks)
648 { /*lint --e{715}*/
649  SCIP_HEURDATA* heurdata;
650  SCIP_VAR** vars;
652  SCIP_Real lowerbound;
653  SCIP_Bool cutoff;
654  SCIP_Bool lperror;
655  SCIP_Bool allrowsfulfilled = FALSE;
656 #ifdef NOCONFLICT
657  SCIP_Bool enabledconflicts;
658 #endif
659  int oldnpscands;
660  int npscands;
661 
662  int nvars;
663  int i;
664 
665  *result = SCIP_DIDNOTRUN;
666 
667  /* only run once */
668  if( SCIPgetNRuns(scip) > 1 )
669  return SCIP_OKAY;
670 
671  if( SCIPgetNBinVars(scip) == 0 )
672  return SCIP_OKAY;
673 
674  /* only run if we are allowed to solve an LP at the current node in the tree */
675  if( !SCIPhasCurrentNodeLP(scip) )
676  return SCIP_OKAY;
677 
678  if( !SCIPisLPConstructed(scip) )
679  {
680  SCIP_CALL( SCIPconstructLP(scip, &cutoff) );
681 
682  /* manually cut off the node if the LP construction detected infeasibility (heuristics cannot return such a result) */
683  if( cutoff )
684  {
686  return SCIP_OKAY;
687  }
688 
690 
691  /* we need an LP */
692  if( SCIPgetNLPRows(scip) == 0 )
693  return SCIP_OKAY;
694  }
695 
696  *result = SCIP_DIDNOTFIND;
697 
698  heurdata = SCIPheurGetData(heur);
699  assert(heurdata != NULL);
700 
701 #ifdef NOCONFLICT
702  /* disable conflict analysis */
703  SCIP_CALL( SCIPgetBoolParam(scip, "conflict/enable", &enabledconflicts) );
704 
705  if( !SCIPisParamFixed(scip, "conflict/enable") )
706  {
707  SCIP_CALL( SCIPsetBoolParam(scip, "conflict/enable", FALSE) );
708  }
709 #endif
710 
711  lowerbound = SCIPgetLowerbound(scip);
712  oldnpscands = SCIPgetNPseudoBranchCands(scip);
713 
714  /* start probing mode */
716 
717 #ifdef COLLECTSTATISTICS
719 #endif
720 
721  cutoff = FALSE;
722  lperror = FALSE;
723 
724  SCIP_CALL( SCIPapplyLockFixings(scip, heurdata, &cutoff, &allrowsfulfilled) );
725 
726  if( cutoff || SCIPisStopped(scip) )
727  goto TERMINATE;
728 
729  /* check that we had enough fixings */
730  npscands = SCIPgetNPseudoBranchCands(scip);
731 
732  SCIPdebugMsg(scip, "npscands=%d, oldnpscands=%d, allrowsfulfilled=%u heurdata->minfixingrate=%g\n",
733  npscands, oldnpscands, allrowsfulfilled, heurdata->minfixingrate);
734 
735  if( !allrowsfulfilled && npscands > oldnpscands * (1 - heurdata->minfixingrate) )
736  {
737  SCIPdebugMsg(scip, "--> too few fixings\n");
738 
739  goto TERMINATE;
740  }
741  else
742  {
743  char strbuf[SCIP_MAXSTRLEN];
744 
745  if( SCIPgetNContVars(scip) > 0 )
746  {
747  int nminfixings;
748  int nfixedvars = 0;
749 
750  nvars = SCIPgetNVars(scip);
751  vars = SCIPgetVars(scip);
752  nminfixings = (int)(SCIPceil(scip, heurdata->minfixingratelp * nvars));
753 
754  /* count fixed variables */
755  for( i = 0; i < nvars && nfixedvars < nminfixings; ++i )
756  {
757  if( SCIPisEQ(scip, SCIPvarGetLbLocal(vars[i]), SCIPvarGetUbLocal(vars[i])) )
758  ++nfixedvars;
759  }
760 
761  SCIPdebugMsg(scip, "Fixed %d of %d (%.1f %%) variables after probing -> %s\n",
762  nfixedvars, nvars, (100.0 * nfixedvars / (SCIP_Real)nvars),
763  nfixedvars >= nminfixings ? "continue and solve LP for remaining variables" : "terminate without LP");
764 
765  if( nfixedvars < nminfixings )
766  goto TERMINATE;
767  }
768 
769  /* print probing stats before LP */
770  SCIPverbMessage(scip, SCIP_VERBLEVEL_FULL, NULL, "Heuristic " HEUR_NAME " probing LP: %s\n",
772 
773  SCIPdebugMsg(scip, "starting solving locks-lp at time %g\n", SCIPgetSolvingTime(scip));
774  /* solve LP;
775  * errors in the LP solver should not kill the overall solving process, if the LP is just needed for a heuristic.
776  * hence in optimized mode, the return code is caught and a warning is printed, only in debug mode, SCIP will stop.
777  */
778 #ifdef NDEBUG
779  {
780  SCIP_Bool retstat;
781  retstat = SCIPsolveProbingLP(scip, -1, &lperror, &cutoff);
782  if( retstat != SCIP_OKAY )
783  {
784  SCIPwarningMessage(scip, "Error while solving LP in LOCKS heuristic; LP solve terminated with code <%d>\n",
785  retstat);
786  }
787  }
788 #else
789  SCIP_CALL( SCIPsolveProbingLP(scip, -1, &lperror, &cutoff) );
790 #endif
791  SCIPdebugMsg(scip, "ending solving locks-lp at time %g\n", SCIPgetSolvingTime(scip));
792 
793  lpstatus = SCIPgetLPSolstat(scip);
794 
795  SCIPdebugMsg(scip, " -> new LP iterations: %" SCIP_LONGINT_FORMAT "\n", SCIPgetNLPIterations(scip));
796  SCIPdebugMsg(scip, " -> error=%u, status=%d\n", lperror, SCIPgetLPSolstat(scip));
797 
798  /* check if this is a feasible solution */
799  if( !lperror && lpstatus == SCIP_LPSOLSTAT_OPTIMAL )
800  {
801  SCIP_SOL* sol;
802  SCIP_Bool success;
803 
804  lowerbound = SCIPgetLPObjval(scip);
805 
806  /* create a copy of the current LP solution */
807  SCIP_CALL( SCIPcreateSol(scip, &sol, heur) );
808  SCIP_CALL( SCIPlinkLPSol(scip, sol) );
809 
810  SCIP_CALL( SCIProundSol(scip, sol, &success) );
811 
812  if( success )
813  {
814  SCIP_Bool stored;
815 
816  /* check solution for feasibility, and add it to solution store if possible.
817  * Neither integrality nor feasibility of LP rows have to be checked, because they
818  * are guaranteed by the heuristic at this stage.
819  */
820  SCIP_CALL( SCIPtrySol(scip, sol, FALSE, FALSE, FALSE, FALSE, FALSE, &stored) );
821 
822  if( stored )
823  {
824 #ifdef SCIP_MORE_DEBUG
825  SCIP_Bool feasible;
826  SCIP_CALL( SCIPcheckSol(scip, sol, TRUE, TRUE, TRUE, TRUE, TRUE, &feasible) );
827  assert(feasible);
828 #endif
829 
830  SCIPdebugMsg(scip, "found feasible solution:\n");
832  *result = SCIP_FOUNDSOL;
833  }
834 
835  SCIP_CALL( SCIPfreeSol(scip, &sol) );
836 
837  /* we found a solution, so we are done */
838  goto TERMINATE;
839  }
840 
841  SCIP_CALL( SCIPfreeSol(scip, &sol) );
842  }
843  }
844 
845  if( heurdata->usefinalsubmip && !cutoff && !lperror && lpstatus != SCIP_LPSOLSTAT_INFEASIBLE && lpstatus != SCIP_LPSOLSTAT_OBJLIMIT )
846  {
847  SCIP* subscip;
848  SCIP_VAR** subvars;
849  SCIP_HASHMAP* varmap;
850  SCIP_Longint nstallnodes;
851  SCIP_Bool valid;
852 
853  /* calculate the maximal number of branching nodes until heuristic is aborted */
854  nstallnodes = (SCIP_Longint)(heurdata->nodesquot * SCIPgetNNodes(scip));
855 
856  /* reward locks heuristic if it succeeded often */
857  nstallnodes = (SCIP_Longint)(nstallnodes * 3.0 * (SCIPheurGetNBestSolsFound(heur)+1.0)/(SCIPheurGetNCalls(heur) + 1.0));
858  nstallnodes -= 100 * SCIPheurGetNCalls(heur); /* count the setup costs for the sub-MIP as 100 nodes */
859  nstallnodes += heurdata->nodesofs;
860 
861  /* determine the node limit for the current process */
862  nstallnodes -= heurdata->usednodes;
863  nstallnodes = MIN(nstallnodes, heurdata->maxnodes);
864 
865  /* check whether we have enough nodes left to call subproblem solving */
866  if( nstallnodes < heurdata->minnodes )
867  {
868  SCIPdebugMsg(scip, "skipping " HEUR_NAME ": nstallnodes=%" SCIP_LONGINT_FORMAT ", minnodes=%" SCIP_LONGINT_FORMAT "\n", nstallnodes, heurdata->minnodes);
869  goto TERMINATE;
870  }
871 
872  /* check whether there is enough time and memory left */
873  SCIP_CALL( SCIPcheckCopyLimits(scip, &valid) );
874 
875  if( !valid )
876  goto TERMINATE;
877 
878  /* get all variables */
879  SCIP_CALL( SCIPgetVarsData(scip, &vars, &nvars, NULL, NULL, NULL, NULL) );
880 
881  /* create subproblem */
882  SCIP_CALL( SCIPcreate(&subscip) );
883 
884  /* allocate temporary memory for subscip variables */
885  SCIP_CALL( SCIPallocBufferArray(scip, &subvars, nvars) );
886 
887  /* create the variable mapping hash map */
888  SCIP_CALL( SCIPhashmapCreate(&varmap, SCIPblkmem(subscip), nvars) );
889 
890  SCIP_CALL( SCIPcopy(scip, subscip, varmap, NULL, "_locks", FALSE, FALSE, FALSE, TRUE, &valid) );
891 
892  if( heurdata->copycuts )
893  {
894  /* copies all active cuts from cutpool of sourcescip to linear constraints in targetscip */
895  SCIP_CALL( SCIPcopyCuts(scip, subscip, varmap, NULL, FALSE, NULL) );
896  }
897 
898  for( i = 0; i < nvars; i++ )
899  subvars[i] = (SCIP_VAR*) SCIPhashmapGetImage(varmap, vars[i]);
900 
901  /* free hash map */
902  SCIPhashmapFree(&varmap);
903 
904  /* do not abort subproblem on CTRL-C */
905  SCIP_CALL( SCIPsetBoolParam(subscip, "misc/catchctrlc", FALSE) );
906 
907 #ifdef SCIP_DEBUG
908  /* for debugging, enable full output */
909  SCIP_CALL( SCIPsetIntParam(subscip, "display/verblevel", 5) );
910  SCIP_CALL( SCIPsetIntParam(subscip, "display/freq", 100000000) );
911 #else
912  /* disable statistic timing inside sub SCIP and output to console */
913  SCIP_CALL( SCIPsetIntParam(subscip, "display/verblevel", 0) );
914  SCIP_CALL( SCIPsetBoolParam(subscip, "timing/statistictiming", FALSE) );
915 #endif
916 
917  /* set limits for the subproblem */
918  SCIP_CALL( SCIPcopyLimits(scip, subscip) );
919  SCIP_CALL( SCIPsetLongintParam(subscip, "limits/stallnodes", nstallnodes) );
920  SCIP_CALL( SCIPsetLongintParam(subscip, "limits/nodes", heurdata->maxnodes) );
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  /* speed up sub-SCIP by not checking dual LP feasibility */
938  SCIP_CALL( SCIPsetBoolParam(subscip, "lp/checkdualfeas", FALSE) );
939 
940  /* employ a limit on the number of enforcement rounds in the quadratic constraint handler; this fixes the issue that
941  * sometimes the quadratic constraint handler needs hundreds or thousands of enforcement rounds to determine the
942  * feasibility status of a single node without fractional branching candidates by separation (namely for uflquad
943  * instances); however, the solution status of the sub-SCIP might get corrupted by this; hence no deductions shall be
944  * made for the original SCIP
945  */
946  if( SCIPfindConshdlr(subscip, "quadratic") != NULL && !SCIPisParamFixed(subscip, "constraints/quadratic/enfolplimit") )
947  {
948  SCIP_CALL( SCIPsetIntParam(subscip, "constraints/quadratic/enfolplimit", 10) );
949  }
950 
951  /* if there is already a solution, add an objective cutoff */
952  if( SCIPgetNSols(scip) > 0 )
953  {
954  SCIP_Real upperbound;
955  SCIP_Real minimprove;
956  SCIP_Real cutoffbound;
957 
958  minimprove = heurdata->minimprove;
960 
961  upperbound = SCIPgetUpperbound(scip) - SCIPsumepsilon(scip);
962 
963  if( !SCIPisInfinity(scip, -1.0 * lowerbound) )
964  {
965  cutoffbound = (1-minimprove) * SCIPgetUpperbound(scip) + minimprove * lowerbound;
966  }
967  else
968  {
969  if( SCIPgetUpperbound ( scip ) >= 0 )
970  cutoffbound = (1 - minimprove) * SCIPgetUpperbound(scip);
971  else
972  cutoffbound = (1 + minimprove) * SCIPgetUpperbound(scip);
973  }
974  cutoffbound = MIN(upperbound, cutoffbound);
975  SCIP_CALL( SCIPsetObjlimit(subscip, cutoffbound) );
976  SCIPdebugMsg(scip, "setting objlimit for subscip to %g\n", cutoffbound);
977  }
978 
979  SCIPdebugMsg(scip, "starting solving locks-submip at time %g\n", SCIPgetSolvingTime(scip));
980 
981  /* solve the subproblem */
982  /* Errors in the LP solver should not kill the overall solving process, if the LP is just needed for a heuristic.
983  * Hence in optimized mode, the return code is caught and a warning is printed, only in debug mode, SCIP will stop.
984  */
985 #ifdef NDEBUG
986  {
987  SCIP_RETCODE retstat;
988  retstat = SCIPpresolve(subscip);
989  if( retstat != SCIP_OKAY )
990  {
991  SCIPwarningMessage(scip, "Error while presolving subMIP in locks heuristic; sub-SCIP terminated with code <%d>\n", retstat);
992 
993  goto FREESCIPANDTERMINATE;
994  }
995  }
996 #else
997  SCIP_CALL_ABORT( SCIPpresolve(subscip) );
998 #endif
999 
1000  SCIPdebugMsg(scip, "locks 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));
1001 
1002  /* after presolving, we should have at least reached a certain fixing rate over ALL variables (including continuous)
1003  * to ensure that not only the MIP but also the LP relaxation is easy enough
1004  */
1005  if( ((nvars - SCIPgetNVars(subscip)) / (SCIP_Real)nvars) >= heurdata->minfixingrate )
1006  {
1007  SCIP_Bool success;
1008 
1009  SCIPdebugMsg(scip, "solving subproblem: nstallnodes=%" SCIP_LONGINT_FORMAT ", maxnodes=%" SCIP_LONGINT_FORMAT "\n", nstallnodes, heurdata->maxnodes);
1010 
1011 #ifdef NDEBUG
1012  {
1013  SCIP_RETCODE retstat;
1014  retstat = SCIPsolve(subscip);
1015  if( retstat != SCIP_OKAY )
1016  {
1017  SCIPwarningMessage(scip, "Error while solving subMIP in locks heuristic; sub-SCIP terminated with code <%d>\n",retstat);
1018 
1019  goto FREESCIPANDTERMINATE;
1020  }
1021  }
1022 #else
1023  SCIP_CALL_ABORT( SCIPsolve(subscip) );
1024 #endif
1025  SCIPdebugMsg(scip, "ending solving locks-submip at time %g, status = %d\n", SCIPgetSolvingTime(scip), SCIPgetStatus(subscip));
1026 
1027  /* check, whether a solution was found; due to numerics, it might happen that not all solutions are feasible ->
1028  * try all solutions until one was accepted
1029  */
1030  SCIP_CALL( SCIPtranslateSubSols(scip, subscip, heur, subvars, &success, NULL) );
1031  if( success )
1032  *result = SCIP_FOUNDSOL;
1033  }
1034 
1035 #ifdef SCIP_DEBUG
1036  SCIP_CALL( SCIPprintStatistics(subscip, NULL) );
1037 #endif
1038 
1039  heurdata->usednodes += SCIPgetNNodes(subscip);
1040 #ifdef NDEBUG
1041  FREESCIPANDTERMINATE:
1042 #endif
1043  /* free subproblem */
1044  SCIPfreeBufferArray(scip, &subvars);
1045  SCIP_CALL( SCIPfree(&subscip) );
1046  }
1047 
1048  TERMINATE:
1049  /* exit probing mode */
1051 
1052 #ifdef NOCONFLICT
1053  /* reset the conflict analysis */
1054  if( !SCIPisParamFixed(scip, "conflict/enable") )
1055  {
1056  SCIP_CALL( SCIPsetBoolParam(scip, "conflict/enable", enabledconflicts) );
1057  }
1058 #endif
1059 
1060  return SCIP_OKAY;
1061 }
1062 
1063 
1064 /*
1065  * primal heuristic specific interface methods
1066  */
1067 
1068 /** creates the locks primal heuristic and includes it in SCIP */
1070  SCIP* scip /**< SCIP data structure */
1071  )
1072 {
1073  SCIP_HEURDATA* heurdata;
1074 
1075  /* create primal heuristic data */
1076  SCIP_CALL( SCIPallocBlockMemory(scip, &heurdata) );
1077 
1078  /* include primal heuristic */
1081  heurCopyLocks,
1082  heurFreeLocks, heurInitLocks, heurExitLocks,
1083  heurInitsolLocks, heurExitsolLocks, heurExecLocks,
1084  heurdata) );
1085 
1086  SCIP_CALL( SCIPaddIntParam(scip, "heuristics/" HEUR_NAME "/maxproprounds",
1087  "maximum number of propagation rounds to be performed in each propagation call (-1: no limit, -2: parameter settings)",
1088  &heurdata->maxproprounds, TRUE, DEFAULT_MAXPROPROUNDS, -2, INT_MAX, NULL, NULL) );
1089 
1090  SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/minfixingrate",
1091  "minimum percentage of integer variables that have to be fixable",
1092  &heurdata->minfixingrate, FALSE, DEFAULT_MINFIXINGRATE, 0.0, 1.0, NULL, NULL) );
1093 
1094  SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/roundupprobability",
1095  "probability for rounding a variable up in case of ties",
1096  &heurdata->roundupprobability, FALSE, DEFAULT_ROUNDUPPROBABILITY, 0.0, 1.0, NULL, NULL) );
1097 
1098  SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/usefinalsubmip",
1099  "should a final sub-MIP be solved to costruct a feasible solution if the LP was not roundable?",
1100  &heurdata->usefinalsubmip, TRUE, DEFAULT_USEFINALSUBMIP, NULL, NULL) );
1101 
1102  SCIP_CALL( SCIPaddLongintParam(scip, "heuristics/" HEUR_NAME "/maxnodes",
1103  "maximum number of nodes to regard in the subproblem",
1104  &heurdata->maxnodes, TRUE, DEFAULT_MAXNODES, 0LL, SCIP_LONGINT_MAX, NULL, NULL) );
1105 
1106  SCIP_CALL( SCIPaddLongintParam(scip, "heuristics/" HEUR_NAME "/nodesofs",
1107  "number of nodes added to the contingent of the total nodes",
1108  &heurdata->nodesofs, FALSE, DEFAULT_NODESOFS, 0LL, SCIP_LONGINT_MAX, NULL, NULL) );
1109 
1110  SCIP_CALL( SCIPaddLongintParam(scip, "heuristics/" HEUR_NAME "/minnodes",
1111  "minimum number of nodes required to start the subproblem",
1112  &heurdata->minnodes, TRUE, DEFAULT_MINNODES, 0LL, SCIP_LONGINT_MAX, NULL, NULL) );
1113 
1114  SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/nodesquot",
1115  "contingent of sub problem nodes in relation to the number of nodes of the original problem",
1116  &heurdata->nodesquot, FALSE, DEFAULT_NODESQUOT, 0.0, 1.0, NULL, NULL) );
1117 
1118  SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/minimprove",
1119  "factor by which " HEUR_NAME " heuristic should at least improve the incumbent",
1120  &heurdata->minimprove, TRUE, DEFAULT_MINIMPROVE, 0.0, 1.0, NULL, NULL) );
1121 
1122  SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/copycuts",
1123  "should all active cuts from cutpool be copied to constraints in subproblem?",
1124  &heurdata->copycuts, TRUE, DEFAULT_COPYCUTS, NULL, NULL) );
1125 
1126  SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/updatelocks",
1127  "should the locks be updated based on LP rows?",
1128  &heurdata->updatelocks, TRUE, DEFAULT_UPDATELOCKS, NULL, NULL) );
1129 
1130  SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/minfixingratelp",
1131  "minimum fixing rate over all variables (including continuous) to solve LP",
1132  &heurdata->minfixingratelp, TRUE, DEFAULT_MINFIXINGRATELP, 0.0, 1.0, NULL, NULL) );
1133 
1134  return SCIP_OKAY;
1135 }
SCIP_Bool SCIPisEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
#define DEFAULT_NODESOFS
Definition: heur_locks.c:70
SCIP_Longint SCIPheurGetNCalls(SCIP_HEUR *heur)
Definition: heur.c:1555
int SCIPgetNContVars(SCIP *scip)
Definition: scip_prob.c:2166
int SCIPconshdlrGetNCheckConss(SCIP_CONSHDLR *conshdlr)
Definition: cons.c:4614
SCIP_RETCODE SCIPfreeSol(SCIP *scip, SCIP_SOL **sol)
Definition: scip_sol.c:977
SCIP_Bool SCIPisPositive(SCIP *scip, SCIP_Real val)
SCIP_RETCODE SCIProundSol(SCIP *scip, SCIP_SOL *sol, SCIP_Bool *success)
Definition: scip_sol.c:2447
SCIP_Bool SCIPisStopped(SCIP *scip)
Definition: scip_general.c:687
SCIP_Real SCIPsumepsilon(SCIP *scip)
#define DEFAULT_MINIMPROVE
Definition: heur_locks.c:66
SCIP_CONSHDLR * SCIPfindConshdlr(SCIP *scip, const char *name)
Definition: scip_cons.c:877
const char * SCIPheurGetName(SCIP_HEUR *heur)
Definition: heur.c:1429
public methods for SCIP parameter handling
void SCIPfreeRandom(SCIP *scip, SCIP_RANDNUMGEN **randnumgen)
SCIP_RETCODE SCIPfixVarProbing(SCIP *scip, SCIP_VAR *var, SCIP_Real fixedval)
Definition: scip_probing.c:409
int SCIPgetNLPRows(SCIP *scip)
Definition: scip_lp.c:596
SCIP_RETCODE SCIPnewProbingNode(SCIP *scip)
Definition: scip_probing.c:156
SCIP_EXPORT int SCIPvarGetNLocksUpType(SCIP_VAR *var, SCIP_LOCKTYPE locktype)
Definition: var.c:3250
public methods for memory management
SCIP_HEURDATA * SCIPheurGetData(SCIP_HEUR *heur)
Definition: heur.c:1340
SCIP_Real SCIPgetRowMaxActivity(SCIP *scip, SCIP_ROW *row)
Definition: scip_lp.c:1896
SCIP_STATUS SCIPgetStatus(SCIP *scip)
Definition: scip_general.c:467
#define SCIPallocClearBufferArray(scip, ptr, num)
Definition: scip_mem.h:113
#define SCIP_MAXSTRLEN
Definition: def.h:273
SCIP_Real * SCIPcolGetVals(SCIP_COL *col)
Definition: lp.c:17010
void SCIPwarningMessage(SCIP *scip, const char *formatstr,...)
Definition: scip_message.c:123
SCIP_RETCODE SCIPincludeHeur(SCIP *scip, const char *name, const char *desc, char dispchar, int priority, int freq, int freqofs, int maxdepth, SCIP_HEURTIMING timingmask, SCIP_Bool usessubscip, SCIP_DECL_HEURCOPY((*heurcopy)), SCIP_DECL_HEURFREE((*heurfree)), SCIP_DECL_HEURINIT((*heurinit)), SCIP_DECL_HEUREXIT((*heurexit)), SCIP_DECL_HEURINITSOL((*heurinitsol)), SCIP_DECL_HEUREXITSOL((*heurexitsol)), SCIP_DECL_HEUREXEC((*heurexec)), SCIP_HEURDATA *heurdata)
Definition: scip_heur.c:58
int SCIProwGetNNonz(SCIP_ROW *row)
Definition: lp.c:17062
public solving methods
SCIP_RETCODE SCIPprintRow(SCIP *scip, SCIP_ROW *row, FILE *file)
Definition: scip_lp.c:2152
public methods for timing
int SCIPcolGetNNonz(SCIP_COL *col)
Definition: lp.c:16975
static SCIP_DECL_HEUREXEC(heurExecLocks)
Definition: heur_locks.c:651
SCIP_RETCODE SCIPtranslateSubSols(SCIP *scip, SCIP *subscip, SCIP_HEUR *heur, SCIP_VAR **subvars, SCIP_Bool *success, int *solindex)
Definition: scip_copy.c:1396
SCIP_RETCODE SCIPgetBoolParam(SCIP *scip, const char *name, SCIP_Bool *value)
Definition: scip_param.c:241
SCIP_NODE * SCIPgetCurrentNode(SCIP *scip)
Definition: scip_tree.c:81
int SCIPgetNVars(SCIP *scip)
Definition: scip_prob.c:1986
int SCIPgetNConss(SCIP *scip)
Definition: scip_prob.c:3036
SCIP_Real SCIPgetSolvingTime(SCIP *scip)
Definition: scip_timing.c:360
void SCIPverbMessage(SCIP *scip, SCIP_VERBLEVEL msgverblevel, FILE *file, const char *formatstr,...)
Definition: scip_message.c:216
#define FALSE
Definition: def.h:73
SCIP_ROW ** SCIPcolGetRows(SCIP_COL *col)
Definition: lp.c:17000
SCIP_EXPORT SCIP_Real SCIPvarGetObj(SCIP_VAR *var)
Definition: var.c:17510
SCIP_Real SCIPrandomGetReal(SCIP_RANDNUMGEN *randnumgen, SCIP_Real minrandval, SCIP_Real maxrandval)
Definition: misc.c:9967
#define DEFAULT_RANDSEED
Definition: heur_locks.c:80
int SCIProwGetRank(SCIP_ROW *row)
Definition: lp.c:17230
char * SCIPsnprintfProbingStats(SCIP *scip, char *strbuf, int len)
SCIP_EXPORT SCIP_VARTYPE SCIPvarGetType(SCIP_VAR *var)
Definition: var.c:17177
#define TRUE
Definition: def.h:72
#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 SCIPlinkLPSol(SCIP *scip, SCIP_SOL *sol)
Definition: scip_sol.c:1018
#define HEUR_DESC
Definition: heur_locks.c:54
SCIP_Bool SCIPisLPConstructed(SCIP *scip)
Definition: scip_lp.c:92
SCIP_RETCODE SCIPcutoffNode(SCIP *scip, SCIP_NODE *node)
Definition: scip_tree.c:424
SCIP_RETCODE SCIPsolve(SCIP *scip)
Definition: scip_solve.c:2527
SCIP_Bool SCIPisFeasLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
void * SCIPhashmapGetImage(SCIP_HASHMAP *hashmap, void *origin)
Definition: misc.c:3200
struct SCIP_HeurData SCIP_HEURDATA
Definition: type_heur.h:67
SCIP_RETCODE SCIPcopy(SCIP *sourcescip, SCIP *targetscip, SCIP_HASHMAP *varmap, SCIP_HASHMAP *consmap, const char *suffix, SCIP_Bool global, SCIP_Bool enablepricing, SCIP_Bool threadsafe, SCIP_Bool passmessagehdlr, SCIP_Bool *valid)
Definition: scip_copy.c:2814
public methods for problem variables
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_Real SCIPceil(SCIP *scip, SCIP_Real val)
#define SCIPfreeBlockMemory(scip, ptr)
Definition: scip_mem.h:95
SCIP_EXPORT SCIP_VARSTATUS SCIPvarGetStatus(SCIP_VAR *var)
Definition: var.c:17131
#define HEUR_FREQ
Definition: heur_locks.c:57
SCIP_RETCODE SCIPsetSubscipsOff(SCIP *scip, SCIP_Bool quiet)
Definition: scip_param.c:893
#define SCIPduplicateBufferArray(scip, ptr, source, num)
Definition: scip_mem.h:119
int SCIProwGetLPPos(SCIP_ROW *row)
Definition: lp.c:17350
SCIP_Real SCIPgetUpperbound(SCIP *scip)
#define SCIP_LONGINT_MAX
Definition: def.h:149
#define SCIPfreeBufferArray(scip, ptr)
Definition: scip_mem.h:123
enum SCIP_LPSolStat SCIP_LPSOLSTAT
Definition: type_lp.h:42
#define SCIPallocBlockMemory(scip, ptr)
Definition: scip_mem.h:78
SCIP_RETCODE SCIPpresolve(SCIP *scip)
Definition: scip_solve.c:2366
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
#define SCIPdebugMsg
Definition: scip_message.h:69
#define DEFAULT_COPYCUTS
Definition: heur_locks.c:74
SCIP_LPSOLSTAT SCIPgetLPSolstat(SCIP *scip)
Definition: scip_lp.c:159
SCIP_RETCODE SCIPcheckCopyLimits(SCIP *sourcescip, SCIP_Bool *success)
Definition: scip_copy.c:3192
static SCIP_DECL_HEUREXIT(heurExitLocks)
Definition: heur_locks.c:164
SCIP_Longint SCIPheurGetNBestSolsFound(SCIP_HEUR *heur)
Definition: heur.c:1575
#define DEFAULT_MINNODES
Definition: heur_locks.c:69
SCIP_Bool SCIPhasCurrentNodeLP(SCIP *scip)
Definition: scip_lp.c:74
SCIP_Bool SCIPisInfinity(SCIP *scip, SCIP_Real val)
public methods for numerical tolerances
SCIP_RETCODE SCIPcreateRandom(SCIP *scip, SCIP_RANDNUMGEN **randnumgen, unsigned int initialseed, SCIP_Bool useglobalseed)
SCIP_HEUR * SCIPfindHeur(SCIP *scip, const char *name)
Definition: scip_heur.c:249
SCIP_RETCODE SCIPcreateSol(SCIP *scip, SCIP_SOL **sol, SCIP_HEUR *heur)
Definition: scip_sol.c:320
#define DEFAULT_ROUNDUPPROBABILITY
Definition: heur_locks.c:64
SCIP_RETCODE SCIPsetObjlimit(SCIP *scip, SCIP_Real objlimit)
Definition: scip_prob.c:1420
public methods for querying solving statistics
int SCIPgetNSols(SCIP *scip)
Definition: scip_sol.c:2206
public methods for the branch-and-bound tree
#define DEFAULT_MAXNODES
Definition: heur_locks.c:63
int SCIPgetNPseudoBranchCands(SCIP *scip)
Definition: scip_branch.c:749
SCIP_Longint SCIPgetNNodes(SCIP *scip)
SCIP_VAR * w
Definition: circlepacking.c:58
SCIP_RETCODE SCIPcreate(SCIP **scip)
Definition: scip_general.c:283
public methods for managing constraints
SCIP_EXPORT const char * SCIPvarGetName(SCIP_VAR *var)
Definition: var.c:17012
SCIP_COL ** SCIProwGetCols(SCIP_ROW *row)
Definition: lp.c:17087
void SCIPenableVarHistory(SCIP *scip)
Definition: scip_var.c:8674
SCIP_RETCODE SCIPgetLPRowsData(SCIP *scip, SCIP_ROW ***rows, int *nrows)
Definition: scip_lp.c:540
SCIP_BRANCHRULE * SCIPfindBranchrule(SCIP *scip, const char *name)
Definition: scip_branch.c:288
SCIP_VAR ** SCIPgetVars(SCIP *scip)
Definition: scip_prob.c:1941
#define DEFAULT_MINFIXINGRATELP
Definition: heur_locks.c:81
#define SCIPfreeBufferArrayNull(scip, ptr)
Definition: scip_mem.h:124
static SCIP_DECL_HEURINIT(heurInitLocks)
Definition: heur_locks.c:144
BMS_BLKMEM * SCIPblkmem(SCIP *scip)
Definition: scip_mem.c:48
SCIP_Real * SCIProwGetVals(SCIP_ROW *row)
Definition: lp.c:17097
int SCIPgetProbingDepth(SCIP *scip)
Definition: scip_probing.c:189
static SCIP_DECL_HEURCOPY(heurCopyLocks)
Definition: heur_locks.c:112
SCIP_Bool SCIPinProbing(SCIP *scip)
Definition: scip_probing.c:88
SCIP_RETCODE SCIPcopyCuts(SCIP *sourcescip, SCIP *targetscip, SCIP_HASHMAP *varmap, SCIP_HASHMAP *consmap, SCIP_Bool global, int *ncutsadded)
Definition: scip_copy.c:2073
#define DEFAULT_NODESQUOT
Definition: heur_locks.c:71
#define DEFAULT_UPDATELOCKS
Definition: heur_locks.c:73
#define NULL
Definition: lpi_spx1.cpp:155
SCIP_RETCODE SCIPendProbing(SCIP *scip)
Definition: scip_probing.c:251
#define heurInitsolLocks
Definition: heur_locks.c:180
#define REALABS(x)
Definition: def.h:187
public methods for problem copies
#define SCIP_CALL(x)
Definition: def.h:364
SCIP_RETCODE SCIPsetPresolving(SCIP *scip, SCIP_PARAMSETTING paramsetting, SCIP_Bool quiet)
Definition: scip_param.c:942
SCIP_RETCODE SCIPbacktrackProbing(SCIP *scip, int probingdepth)
Definition: scip_probing.c:216
SCIP_Real SCIPgetLPObjval(SCIP *scip)
Definition: scip_lp.c:238
public methods for primal heuristic plugins and divesets
public methods for constraint handler plugins and constraints
SCIP_EXPORT SCIP_COL * SCIPvarGetCol(SCIP_VAR *var)
Definition: var.c:17376
#define SCIPallocBufferArray(scip, ptr, num)
Definition: scip_mem.h:111
public data structures and miscellaneous methods
#define HEUR_FREQOFS
Definition: heur_locks.c:58
int SCIPgetDepth(SCIP *scip)
Definition: scip_tree.c:638
#define SCIP_Bool
Definition: def.h:70
SCIP_RETCODE SCIPconstructLP(SCIP *scip, SCIP_Bool *cutoff)
Definition: scip_lp.c:115
#define HEUR_USESSUBSCIP
Definition: heur_locks.c:61
SCIP_RETCODE SCIPhashmapCreate(SCIP_HASHMAP **hashmap, BMS_BLKMEM *blkmem, int mapsize)
Definition: misc.c:3013
int SCIPgetNCheckConss(SCIP *scip)
Definition: scip_prob.c:3178
#define DEFAULT_MAXPROPROUNDS
Definition: heur_locks.c:72
SCIP_Bool SCIPisParamFixed(SCIP *scip, const char *name)
Definition: scip_param.c:210
SCIP_RETCODE SCIPpropagateProbing(SCIP *scip, int maxproprounds, SCIP_Bool *cutoff, SCIP_Longint *ndomredsfound)
Definition: scip_probing.c:571
SCIP_Real SCIProwGetLhs(SCIP_ROW *row)
Definition: lp.c:17141
#define heurExitsolLocks
Definition: heur_locks.c:181
public methods for LP management
SCIP_RETCODE SCIPprintStatistics(SCIP *scip, FILE *file)
SCIP_RETCODE SCIPflushLP(SCIP *scip)
Definition: scip_lp.c:139
#define DEFAULT_USEFINALSUBMIP
Definition: heur_locks.c:77
locks primal heuristic
SCIP_Bool SCIPisFeasGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_RETCODE SCIPcopyLimits(SCIP *sourcescip, SCIP *targetscip)
Definition: scip_copy.c:3228
SCIP_EXPORT SCIP_Real SCIPvarGetLbLocal(SCIP_VAR *var)
Definition: var.c:17718
#define SCIP_MAXTREEDEPTH
Definition: def.h:300
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_VAR * SCIPcolGetVar(SCIP_COL *col)
Definition: lp.c:16901
public methods for the LP relaxation, rows and columns
SCIP_EXPORT int SCIPvarGetNLocksDownType(SCIP_VAR *var, SCIP_LOCKTYPE locktype)
Definition: var.c:3193
#define HEUR_PRIORITY
Definition: heur_locks.c:56
#define HEUR_DISPCHAR
Definition: heur_locks.c:55
#define HEUR_NAME
Definition: heur_locks.c:53
SCIP_Real * r
Definition: circlepacking.c:50
SCIP_EXPORT SCIP_Real SCIPvarGetUbLocal(SCIP_VAR *var)
Definition: var.c:17728
SCIP_RETCODE SCIPsetLongintParam(SCIP *scip, const char *name, SCIP_Longint value)
Definition: scip_param.c:555
public methods for branching rule plugins and branching
general public methods
SCIP_Bool SCIPisFeasGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Longint SCIPgetNLPIterations(SCIP *scip)
public methods for solutions
public methods for random numbers
SCIP_Real SCIPgetLowerbound(SCIP *scip)
public methods for the probing mode
SCIP_Bool SCIPisFeasLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_RETCODE SCIPstartProbing(SCIP *scip)
Definition: scip_probing.c:110
public methods for message output
SCIP_RETCODE SCIPgetVarsData(SCIP *scip, SCIP_VAR ***vars, int *nvars, int *nbinvars, int *nintvars, int *nimplvars, int *ncontvars)
Definition: scip_prob.c:1860
SCIP_RETCODE SCIPincludeHeurLocks(SCIP *scip)
Definition: heur_locks.c:1073
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
void SCIPhashmapFree(SCIP_HASHMAP **hashmap)
Definition: misc.c:3047
SCIP_RETCODE SCIPprintSol(SCIP *scip, SCIP_SOL *sol, FILE *file, SCIP_Bool printzeros)
Definition: scip_sol.c:1767
#define SCIP_Real
Definition: def.h:163
#define HEUR_TIMING
Definition: heur_locks.c:60
const char * SCIProwGetName(SCIP_ROW *row)
Definition: lp.c:17200
static SCIP_DECL_HEURFREE(heurFreeLocks)
Definition: heur_locks.c:126
public methods for message handling
#define SCIP_Longint
Definition: def.h:148
SCIP_RETCODE SCIPsetBoolParam(SCIP *scip, const char *name, SCIP_Bool value)
Definition: scip_param.c:439
int SCIPgetNBinVars(SCIP *scip)
Definition: scip_prob.c:2031
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_EXPORT int SCIPvarGetProbindex(SCIP_VAR *var)
Definition: var.c:17355
#define HEUR_MAXDEPTH
Definition: heur_locks.c:59
SCIP_Real SCIProwGetRhs(SCIP_ROW *row)
Definition: lp.c:17151
public methods for primal heuristics
SCIP_RETCODE SCIPfree(SCIP **scip)
Definition: scip_general.c:315
#define SCIP_CALL_ABORT(x)
Definition: def.h:343
public methods for global and local (sub)problems
SCIP_Real SCIPgetRowMinActivity(SCIP *scip, SCIP_ROW *row)
Definition: scip_lp.c:1879
SCIP_RETCODE SCIPsetIntParam(SCIP *scip, const char *name, int value)
Definition: scip_param.c:497
SCIP_RETCODE SCIPcheckSol(SCIP *scip, SCIP_SOL *sol, SCIP_Bool printreason, SCIP_Bool completely, SCIP_Bool checkbounds, SCIP_Bool checkintegrality, SCIP_Bool checklprows, SCIP_Bool *feasible)
Definition: scip_sol.c:3440
SCIP_RETCODE SCIPsetSeparating(SCIP *scip, SCIP_PARAMSETTING paramsetting, SCIP_Bool quiet)
Definition: scip_param.c:968
SCIP_RETCODE SCIPsolveProbingLP(SCIP *scip, int itlim, SCIP_Bool *lperror, SCIP_Bool *cutoff)
Definition: scip_probing.c:810
#define DEFAULT_MINFIXINGRATE
Definition: heur_locks.c:65
int SCIPgetNRuns(SCIP *scip)
memory allocation routines