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-2022 Konrad-Zuse-Zentrum */
7 /* fuer Informationstechnik Berlin */
8 /* */
9 /* SCIP is distributed under the terms of the ZIB Academic License. */
10 /* */
11 /* You should have received a copy of the ZIB Academic License */
12 /* along with SCIP; see the file COPYING. If not visit scipopt.org. */
13 /* */
14 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
15 
16 /**@file heur_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=%u\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  int ncols;
745 
746  if( SCIPgetNContVars(scip) > 0 )
747  {
748  int nminfixings;
749  int nfixedvars = 0;
750 
751  nvars = SCIPgetNVars(scip);
752  vars = SCIPgetVars(scip);
753  nminfixings = (int)(SCIPceil(scip, heurdata->minfixingratelp * nvars));
754 
755  /* count fixed variables */
756  for( i = 0; i < nvars && nfixedvars < nminfixings; ++i )
757  {
758  if( SCIPisEQ(scip, SCIPvarGetLbLocal(vars[i]), SCIPvarGetUbLocal(vars[i])) )
759  ++nfixedvars;
760  }
761 
762  SCIPdebugMsg(scip, "Fixed %d of %d (%.1f %%) variables after probing -> %s\n",
763  nfixedvars, nvars, (100.0 * nfixedvars / (SCIP_Real)nvars),
764  nfixedvars >= nminfixings ? "continue and solve LP for remaining variables" : "terminate without LP");
765 
766  if( nfixedvars < nminfixings )
767  goto TERMINATE;
768  }
769 
770  /* print message if relatively large LP is solved from scratch, since this could lead to a longer period during
771  * which the user sees no output; more detailed probing stats only in debug mode */
772  ncols = SCIPgetNLPCols(scip);
773  if( !SCIPisLPSolBasic(scip) && ncols > 1000 )
774  {
775  int nunfixedcols = SCIPgetNUnfixedLPCols(scip);
776 
777  if( nunfixedcols > 0.5 * ncols )
778  {
780  "Heuristic " HEUR_NAME " solving LP from scratch with %.1f %% unfixed columns (%d of %d) ...\n",
781  100.0 * (nunfixedcols / (SCIP_Real)ncols), nunfixedcols, ncols);
782  }
783  }
784  SCIPdebugMsg(scip, "Heuristic " HEUR_NAME " probing LP: %s\n",
786 
787  /* solve LP;
788  * errors in the LP solver should not kill the overall solving process, if the LP is just needed for a heuristic.
789  * hence in optimized mode, the return code is caught and a warning is printed, only in debug mode, SCIP will stop.
790  */
791  SCIPdebugMsg(scip, "starting solving locks-lp at time %g\n", SCIPgetSolvingTime(scip));
792 #ifdef NDEBUG
793  {
794  SCIP_Bool retstat;
795  retstat = SCIPsolveProbingLP(scip, -1, &lperror, &cutoff);
796  if( retstat != SCIP_OKAY )
797  {
798  SCIPwarningMessage(scip, "Error while solving LP in LOCKS heuristic; LP solve terminated with code <%d>\n",
799  retstat);
800  }
801  }
802 #else
803  SCIP_CALL( SCIPsolveProbingLP(scip, -1, &lperror, &cutoff) );
804 #endif
805  SCIPdebugMsg(scip, "ending solving locks-lp at time %g\n", SCIPgetSolvingTime(scip));
806 
807  lpstatus = SCIPgetLPSolstat(scip);
808 
809  SCIPdebugMsg(scip, " -> new LP iterations: %" SCIP_LONGINT_FORMAT "\n", SCIPgetNLPIterations(scip));
810  SCIPdebugMsg(scip, " -> error=%u, status=%d\n", lperror, SCIPgetLPSolstat(scip));
811 
812  /* check if this is a feasible solution */
813  if( !lperror && lpstatus == SCIP_LPSOLSTAT_OPTIMAL )
814  {
815  SCIP_SOL* sol;
816  SCIP_Bool success;
817 
818  lowerbound = SCIPgetLPObjval(scip);
819 
820  /* create a copy of the current LP solution */
821  SCIP_CALL( SCIPcreateSol(scip, &sol, heur) );
822  SCIP_CALL( SCIPlinkLPSol(scip, sol) );
823 
824  SCIP_CALL( SCIProundSol(scip, sol, &success) );
825 
826  if( success )
827  {
828  SCIP_Bool stored;
829 
830  /* check solution for feasibility, and add it to solution store if possible.
831  * Neither integrality nor feasibility of LP rows have to be checked, because they
832  * are guaranteed by the heuristic at this stage.
833  */
834  SCIP_CALL( SCIPtrySol(scip, sol, FALSE, FALSE, FALSE, FALSE, FALSE, &stored) );
835 
836  if( stored )
837  {
838 #ifdef SCIP_MORE_DEBUG
839  SCIP_Bool feasible;
840  SCIP_CALL( SCIPcheckSol(scip, sol, TRUE, TRUE, TRUE, TRUE, TRUE, &feasible) );
841  assert(feasible);
842 #endif
843 
844  SCIPdebugMsg(scip, "found feasible solution:\n");
846  *result = SCIP_FOUNDSOL;
847  }
848 
849  SCIP_CALL( SCIPfreeSol(scip, &sol) );
850 
851  /* we found a solution, so we are done */
852  goto TERMINATE;
853  }
854 
855  SCIP_CALL( SCIPfreeSol(scip, &sol) );
856  }
857  }
858 
859  if( heurdata->usefinalsubmip && !cutoff && !lperror && lpstatus != SCIP_LPSOLSTAT_INFEASIBLE && lpstatus != SCIP_LPSOLSTAT_OBJLIMIT )
860  {
861  SCIP* subscip;
862  SCIP_VAR** subvars;
863  SCIP_HASHMAP* varmap;
864  SCIP_Longint nstallnodes;
865  SCIP_Bool valid;
866 
867  /* calculate the maximal number of branching nodes until heuristic is aborted */
868  nstallnodes = (SCIP_Longint)(heurdata->nodesquot * SCIPgetNNodes(scip));
869 
870  /* reward locks heuristic if it succeeded often */
871  nstallnodes = (SCIP_Longint)(nstallnodes * 3.0 * (SCIPheurGetNBestSolsFound(heur)+1.0)/(SCIPheurGetNCalls(heur) + 1.0));
872  nstallnodes -= 100 * SCIPheurGetNCalls(heur); /* count the setup costs for the sub-MIP as 100 nodes */
873  nstallnodes += heurdata->nodesofs;
874 
875  /* determine the node limit for the current process */
876  nstallnodes -= heurdata->usednodes;
877  nstallnodes = MIN(nstallnodes, heurdata->maxnodes);
878 
879  /* check whether we have enough nodes left to call subproblem solving */
880  if( nstallnodes < heurdata->minnodes )
881  {
882  SCIPdebugMsg(scip, "skipping " HEUR_NAME ": nstallnodes=%" SCIP_LONGINT_FORMAT ", minnodes=%" SCIP_LONGINT_FORMAT "\n", nstallnodes, heurdata->minnodes);
883  goto TERMINATE;
884  }
885 
886  /* check whether there is enough time and memory left */
887  SCIP_CALL( SCIPcheckCopyLimits(scip, &valid) );
888 
889  if( !valid )
890  goto TERMINATE;
891 
892  /* get all variables */
893  SCIP_CALL( SCIPgetVarsData(scip, &vars, &nvars, NULL, NULL, NULL, NULL) );
894 
895  /* create subproblem */
896  SCIP_CALL( SCIPcreate(&subscip) );
897 
898  /* allocate temporary memory for subscip variables */
899  SCIP_CALL( SCIPallocBufferArray(scip, &subvars, nvars) );
900 
901  /* create the variable mapping hash map */
902  SCIP_CALL( SCIPhashmapCreate(&varmap, SCIPblkmem(subscip), nvars) );
903 
904  SCIP_CALL( SCIPcopy(scip, subscip, varmap, NULL, "_locks", FALSE, FALSE, FALSE, TRUE, &valid) );
905 
906  if( heurdata->copycuts )
907  {
908  /* copies all active cuts from cutpool of sourcescip to linear constraints in targetscip */
909  SCIP_CALL( SCIPcopyCuts(scip, subscip, varmap, NULL, FALSE, NULL) );
910  }
911 
912  for( i = 0; i < nvars; i++ )
913  subvars[i] = (SCIP_VAR*) SCIPhashmapGetImage(varmap, vars[i]);
914 
915  /* free hash map */
916  SCIPhashmapFree(&varmap);
917 
918  /* do not abort subproblem on CTRL-C */
919  SCIP_CALL( SCIPsetBoolParam(subscip, "misc/catchctrlc", FALSE) );
920 
921 #ifdef SCIP_DEBUG
922  /* for debugging, enable full output */
923  SCIP_CALL( SCIPsetIntParam(subscip, "display/verblevel", 5) );
924  SCIP_CALL( SCIPsetIntParam(subscip, "display/freq", 100000000) );
925 #else
926  /* disable statistic timing inside sub SCIP and output to console */
927  SCIP_CALL( SCIPsetIntParam(subscip, "display/verblevel", 0) );
928  SCIP_CALL( SCIPsetBoolParam(subscip, "timing/statistictiming", FALSE) );
929 #endif
930 
931  /* set limits for the subproblem */
932  SCIP_CALL( SCIPcopyLimits(scip, subscip) );
933  SCIP_CALL( SCIPsetLongintParam(subscip, "limits/stallnodes", nstallnodes) );
934  SCIP_CALL( SCIPsetLongintParam(subscip, "limits/nodes", heurdata->maxnodes) );
935 
936  /* forbid call of heuristics and separators solving sub-CIPs */
937  SCIP_CALL( SCIPsetSubscipsOff(subscip, TRUE) );
938 
939  /* disable cutting plane separation */
941 
942  /* disable expensive presolving */
944 
945  /* use inference branching */
946  if( SCIPfindBranchrule(subscip, "inference") != NULL && !SCIPisParamFixed(subscip, "branching/inference/priority") )
947  {
948  SCIP_CALL( SCIPsetIntParam(subscip, "branching/inference/priority", INT_MAX/4) );
949  }
950 
951  /* speed up sub-SCIP by not checking dual LP feasibility */
952  SCIP_CALL( SCIPsetBoolParam(subscip, "lp/checkdualfeas", FALSE) );
953 
954  /* if there is already a solution, add an objective cutoff */
955  if( SCIPgetNSols(scip) > 0 )
956  {
957  SCIP_Real upperbound;
958  SCIP_Real minimprove;
959  SCIP_Real cutoffbound;
960 
961  minimprove = heurdata->minimprove;
963 
964  upperbound = SCIPgetUpperbound(scip) - SCIPsumepsilon(scip);
965 
966  if( !SCIPisInfinity(scip, -1.0 * lowerbound) )
967  {
968  cutoffbound = (1-minimprove) * SCIPgetUpperbound(scip) + minimprove * lowerbound;
969  }
970  else
971  {
972  if( SCIPgetUpperbound ( scip ) >= 0 )
973  cutoffbound = (1 - minimprove) * SCIPgetUpperbound(scip);
974  else
975  cutoffbound = (1 + minimprove) * SCIPgetUpperbound(scip);
976  }
977  cutoffbound = MIN(upperbound, cutoffbound);
978  SCIP_CALL( SCIPsetObjlimit(subscip, cutoffbound) );
979  SCIPdebugMsg(scip, "setting objlimit for subscip to %g\n", cutoffbound);
980  }
981 
982  SCIPdebugMsg(scip, "starting solving locks-submip at time %g\n", SCIPgetSolvingTime(scip));
983 
984  /* solve the subproblem */
985  /* Errors in the LP solver should not kill the overall solving process, if the LP is just needed for a heuristic.
986  * Hence in optimized mode, the return code is caught and a warning is printed, only in debug mode, SCIP will stop.
987  */
988 #ifdef NDEBUG
989  {
990  SCIP_RETCODE retstat;
991  retstat = SCIPpresolve(subscip);
992  if( retstat != SCIP_OKAY )
993  {
994  SCIPwarningMessage(scip, "Error while presolving subMIP in locks heuristic; sub-SCIP terminated with code <%d>\n", retstat);
995 
996  goto FREESCIPANDTERMINATE;
997  }
998  }
999 #else
1000  SCIP_CALL_ABORT( SCIPpresolve(subscip) );
1001 #endif
1002 
1003  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));
1004 
1005  /* after presolving, we should have at least reached a certain fixing rate over ALL variables (including continuous)
1006  * to ensure that not only the MIP but also the LP relaxation is easy enough
1007  */
1008  if( ((nvars - SCIPgetNVars(subscip)) / (SCIP_Real)nvars) >= heurdata->minfixingrate )
1009  {
1010  SCIP_Bool success;
1011 
1012  SCIPdebugMsg(scip, "solving subproblem: nstallnodes=%" SCIP_LONGINT_FORMAT ", maxnodes=%" SCIP_LONGINT_FORMAT "\n", nstallnodes, heurdata->maxnodes);
1013 
1014 #ifdef NDEBUG
1015  {
1016  SCIP_RETCODE retstat;
1017  retstat = SCIPsolve(subscip);
1018  if( retstat != SCIP_OKAY )
1019  {
1020  SCIPwarningMessage(scip, "Error while solving subMIP in locks heuristic; sub-SCIP terminated with code <%d>\n",retstat);
1021 
1022  goto FREESCIPANDTERMINATE;
1023  }
1024  }
1025 #else
1026  SCIP_CALL_ABORT( SCIPsolve(subscip) );
1027 #endif
1028  SCIPdebugMsg(scip, "ending solving locks-submip at time %g, status = %d\n", SCIPgetSolvingTime(scip), SCIPgetStatus(subscip));
1029 
1030  /* check, whether a solution was found; due to numerics, it might happen that not all solutions are feasible ->
1031  * try all solutions until one was accepted
1032  */
1033  SCIP_CALL( SCIPtranslateSubSols(scip, subscip, heur, subvars, &success, NULL) );
1034  if( success )
1035  *result = SCIP_FOUNDSOL;
1036  }
1037 
1038 #ifdef SCIP_DEBUG
1039  SCIP_CALL( SCIPprintStatistics(subscip, NULL) );
1040 #endif
1041 
1042  heurdata->usednodes += SCIPgetNNodes(subscip);
1043 #ifdef NDEBUG
1044  FREESCIPANDTERMINATE:
1045 #endif
1046  /* free subproblem */
1047  SCIPfreeBufferArray(scip, &subvars);
1048  SCIP_CALL( SCIPfree(&subscip) );
1049  }
1050 
1051  TERMINATE:
1052  /* exit probing mode */
1054 
1055 #ifdef NOCONFLICT
1056  /* reset the conflict analysis */
1057  if( !SCIPisParamFixed(scip, "conflict/enable") )
1058  {
1059  SCIP_CALL( SCIPsetBoolParam(scip, "conflict/enable", enabledconflicts) );
1060  }
1061 #endif
1062 
1063  return SCIP_OKAY;
1064 }
1065 
1066 
1067 /*
1068  * primal heuristic specific interface methods
1069  */
1070 
1071 /** creates the locks primal heuristic and includes it in SCIP */
1073  SCIP* scip /**< SCIP data structure */
1074  )
1075 {
1076  SCIP_HEURDATA* heurdata;
1077 
1078  /* create primal heuristic data */
1079  SCIP_CALL( SCIPallocBlockMemory(scip, &heurdata) );
1080 
1081  /* include primal heuristic */
1084  heurCopyLocks,
1085  heurFreeLocks, heurInitLocks, heurExitLocks,
1086  heurInitsolLocks, heurExitsolLocks, heurExecLocks,
1087  heurdata) );
1088 
1089  SCIP_CALL( SCIPaddIntParam(scip, "heuristics/" HEUR_NAME "/maxproprounds",
1090  "maximum number of propagation rounds to be performed in each propagation call (-1: no limit, -2: parameter settings)",
1091  &heurdata->maxproprounds, TRUE, DEFAULT_MAXPROPROUNDS, -2, INT_MAX, NULL, NULL) );
1092 
1093  SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/minfixingrate",
1094  "minimum percentage of integer variables that have to be fixable",
1095  &heurdata->minfixingrate, FALSE, DEFAULT_MINFIXINGRATE, 0.0, 1.0, NULL, NULL) );
1096 
1097  SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/roundupprobability",
1098  "probability for rounding a variable up in case of ties",
1099  &heurdata->roundupprobability, FALSE, DEFAULT_ROUNDUPPROBABILITY, 0.0, 1.0, NULL, NULL) );
1100 
1101  SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/usefinalsubmip",
1102  "should a final sub-MIP be solved to costruct a feasible solution if the LP was not roundable?",
1103  &heurdata->usefinalsubmip, TRUE, DEFAULT_USEFINALSUBMIP, NULL, NULL) );
1104 
1105  SCIP_CALL( SCIPaddLongintParam(scip, "heuristics/" HEUR_NAME "/maxnodes",
1106  "maximum number of nodes to regard in the subproblem",
1107  &heurdata->maxnodes, TRUE, DEFAULT_MAXNODES, 0LL, SCIP_LONGINT_MAX, NULL, NULL) );
1108 
1109  SCIP_CALL( SCIPaddLongintParam(scip, "heuristics/" HEUR_NAME "/nodesofs",
1110  "number of nodes added to the contingent of the total nodes",
1111  &heurdata->nodesofs, FALSE, DEFAULT_NODESOFS, 0LL, SCIP_LONGINT_MAX, NULL, NULL) );
1112 
1113  SCIP_CALL( SCIPaddLongintParam(scip, "heuristics/" HEUR_NAME "/minnodes",
1114  "minimum number of nodes required to start the subproblem",
1115  &heurdata->minnodes, TRUE, DEFAULT_MINNODES, 0LL, SCIP_LONGINT_MAX, NULL, NULL) );
1116 
1117  SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/nodesquot",
1118  "contingent of sub problem nodes in relation to the number of nodes of the original problem",
1119  &heurdata->nodesquot, FALSE, DEFAULT_NODESQUOT, 0.0, 1.0, NULL, NULL) );
1120 
1121  SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/minimprove",
1122  "factor by which " HEUR_NAME " heuristic should at least improve the incumbent",
1123  &heurdata->minimprove, TRUE, DEFAULT_MINIMPROVE, 0.0, 1.0, NULL, NULL) );
1124 
1125  SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/copycuts",
1126  "should all active cuts from cutpool be copied to constraints in subproblem?",
1127  &heurdata->copycuts, TRUE, DEFAULT_COPYCUTS, NULL, NULL) );
1128 
1129  SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/updatelocks",
1130  "should the locks be updated based on LP rows?",
1131  &heurdata->updatelocks, TRUE, DEFAULT_UPDATELOCKS, NULL, NULL) );
1132 
1133  SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/minfixingratelp",
1134  "minimum fixing rate over all variables (including continuous) to solve LP",
1135  &heurdata->minfixingratelp, TRUE, DEFAULT_MINFIXINGRATELP, 0.0, 1.0, NULL, NULL) );
1136 
1137  return SCIP_OKAY;
1138 }
void SCIPfreeRandom(SCIP *scip, SCIP_RANDNUMGEN **randnumgen)
#define DEFAULT_NODESOFS
Definition: heur_locks.c:70
int SCIPgetNCheckConss(SCIP *scip)
Definition: scip_prob.c:3183
SCIP_RETCODE SCIPlinkLPSol(SCIP *scip, SCIP_SOL *sol)
Definition: scip_sol.c:1017
SCIP_Real SCIPgetSolvingTime(SCIP *scip)
Definition: scip_timing.c:369
SCIP_RETCODE SCIPsetSeparating(SCIP *scip, SCIP_PARAMSETTING paramsetting, SCIP_Bool quiet)
Definition: scip_param.c:949
#define DEFAULT_MINIMPROVE
Definition: heur_locks.c:66
public methods for SCIP parameter handling
int SCIPvarGetNLocksDownType(SCIP_VAR *var, SCIP_LOCKTYPE locktype)
Definition: var.c:3289
SCIP_NODE * SCIPgetCurrentNode(SCIP *scip)
Definition: scip_tree.c:82
SCIP_RETCODE SCIPbacktrackProbing(SCIP *scip, int probingdepth)
Definition: scip_probing.c:216
SCIP_Longint SCIPgetNLPIterations(SCIP *scip)
SCIP_Bool SCIPisFeasLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
public methods for memory management
SCIP_CONSHDLR * SCIPfindConshdlr(SCIP *scip, const char *name)
Definition: scip_cons.c:877
int SCIPgetProbingDepth(SCIP *scip)
Definition: scip_probing.c:189
#define SCIPallocClearBufferArray(scip, ptr, num)
Definition: scip_mem.h:117
#define SCIP_MAXSTRLEN
Definition: def.h:293
int SCIPvarGetNLocksUpType(SCIP_VAR *var, SCIP_LOCKTYPE locktype)
Definition: var.c:3347
SCIP_Longint SCIPheurGetNBestSolsFound(SCIP_HEUR *heur)
Definition: heur.c:1587
SCIP_Real * SCIPcolGetVals(SCIP_COL *col)
Definition: lp.c:17127
int SCIProwGetNNonz(SCIP_ROW *row)
Definition: lp.c:17179
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:2857
SCIP_Bool SCIPisPositive(SCIP *scip, SCIP_Real val)
SCIP_Real SCIPvarGetLbLocal(SCIP_VAR *var)
Definition: var.c:17966
int SCIPgetNPseudoBranchCands(SCIP *scip)
Definition: scip_branch.c:749
public solving methods
public methods for timing
const char * SCIProwGetName(SCIP_ROW *row)
Definition: lp.c:17317
static SCIP_DECL_HEUREXEC(heurExecLocks)
Definition: heur_locks.c:651
SCIP_Bool SCIPisFeasGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_RETCODE SCIPgetVarsData(SCIP *scip, SCIP_VAR ***vars, int *nvars, int *nbinvars, int *nintvars, int *nimplvars, int *ncontvars)
Definition: scip_prob.c:1865
SCIP_Real SCIProwGetLhs(SCIP_ROW *row)
Definition: lp.c:17258
#define FALSE
Definition: def.h:87
SCIP_RETCODE SCIPhashmapCreate(SCIP_HASHMAP **hashmap, BMS_BLKMEM *blkmem, int mapsize)
Definition: misc.c:3014
SCIP_RETCODE SCIPaddLongintParam(SCIP *scip, const char *name, const char *desc, SCIP_Longint *valueptr, SCIP_Bool isadvanced, SCIP_Longint defaultvalue, SCIP_Longint minvalue, SCIP_Longint maxvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition: scip_param.c:102
SCIP_RETCODE SCIPcopyLimits(SCIP *sourcescip, SCIP *targetscip)
Definition: scip_copy.c:3278
#define DEFAULT_RANDSEED
Definition: heur_locks.c:80
SCIP_RETCODE SCIPcutoffNode(SCIP *scip, SCIP_NODE *node)
Definition: scip_tree.c:425
#define TRUE
Definition: def.h:86
#define SCIPdebug(x)
Definition: pub_message.h:84
SCIP_RETCODE SCIPapplyLockFixings(SCIP *scip, SCIP_HEURDATA *heurdata, SCIP_Bool *cutoff, SCIP_Bool *allrowsfulfilled)
Definition: heur_locks.c:187
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:54
#define HEUR_DESC
Definition: heur_locks.c:54
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
SCIP_RETCODE SCIPsetPresolving(SCIP *scip, SCIP_PARAMSETTING paramsetting, SCIP_Bool quiet)
Definition: scip_param.c:923
SCIP_BRANCHRULE * SCIPfindBranchrule(SCIP *scip, const char *name)
Definition: scip_branch.c:288
int SCIPvarGetProbindex(SCIP_VAR *var)
Definition: var.c:17600
struct SCIP_HeurData SCIP_HEURDATA
Definition: type_heur.h:67
public methods for problem variables
#define SCIPfreeBlockMemory(scip, ptr)
Definition: scip_mem.h:99
SCIP_RETCODE SCIPtranslateSubSols(SCIP *scip, SCIP *subscip, SCIP_HEUR *heur, SCIP_VAR **subvars, SCIP_Bool *success, int *solindex)
Definition: scip_copy.c:1439
#define HEUR_FREQ
Definition: heur_locks.c:57
#define SCIPduplicateBufferArray(scip, ptr, source, num)
Definition: scip_mem.h:123
void * SCIPhashmapGetImage(SCIP_HASHMAP *hashmap, void *origin)
Definition: misc.c:3201
SCIP_Bool SCIPisEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_RETCODE SCIPconstructLP(SCIP *scip, SCIP_Bool *cutoff)
Definition: scip_lp.c:115
#define SCIP_LONGINT_MAX
Definition: def.h:163
#define SCIPfreeBufferArray(scip, ptr)
Definition: scip_mem.h:127
enum SCIP_LPSolStat SCIP_LPSOLSTAT
Definition: type_lp.h:42
SCIP_RETCODE SCIPcreate(SCIP **scip)
Definition: scip_general.c:283
void SCIPwarningMessage(SCIP *scip, const char *formatstr,...)
Definition: scip_message.c:111
#define SCIPdebugMsg
Definition: scip_message.h:69
SCIP_RETCODE SCIPaddIntParam(SCIP *scip, const char *name, const char *desc, int *valueptr, SCIP_Bool isadvanced, int defaultvalue, int minvalue, int maxvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition: scip_param.c:74
#define DEFAULT_COPYCUTS
Definition: heur_locks.c:74
SCIP_RETCODE SCIPprintStatistics(SCIP *scip, FILE *file)
int SCIPgetNContVars(SCIP *scip)
Definition: scip_prob.c:2171
static SCIP_DECL_HEUREXIT(heurExitLocks)
Definition: heur_locks.c:164
#define DEFAULT_MINNODES
Definition: heur_locks.c:69
SCIP_Real SCIPgetRowMaxActivity(SCIP *scip, SCIP_ROW *row)
Definition: scip_lp.c:1941
public methods for numerical tolerances
#define DEFAULT_ROUNDUPPROBABILITY
Definition: heur_locks.c:64
public methods for querying solving statistics
public methods for the branch-and-bound tree
#define DEFAULT_MAXNODES
Definition: heur_locks.c:63
SCIP_Bool SCIPisLPConstructed(SCIP *scip)
Definition: scip_lp.c:92
SCIP_Bool SCIPisLPSolBasic(SCIP *scip)
Definition: scip_lp.c:658
SCIP_VAR * w
Definition: circlepacking.c:58
public methods for managing constraints
SCIP_RETCODE SCIPsolve(SCIP *scip)
Definition: scip_solve.c:2613
const char * SCIPheurGetName(SCIP_HEUR *heur)
Definition: heur.c:1441
SCIP_HEUR * SCIPfindHeur(SCIP *scip, const char *name)
Definition: scip_heur.c:249
SCIP_Bool SCIPisParamFixed(SCIP *scip, const char *name)
Definition: scip_param.c:210
SCIP_ROW ** SCIPcolGetRows(SCIP_COL *col)
Definition: lp.c:17117
SCIP_RETCODE SCIPpropagateProbing(SCIP *scip, int maxproprounds, SCIP_Bool *cutoff, SCIP_Longint *ndomredsfound)
Definition: scip_probing.c:571
SCIP_RETCODE SCIPfixVarProbing(SCIP *scip, SCIP_VAR *var, SCIP_Real fixedval)
Definition: scip_probing.c:409
#define DEFAULT_MINFIXINGRATELP
Definition: heur_locks.c:81
#define SCIPfreeBufferArrayNull(scip, ptr)
Definition: scip_mem.h:128
SCIP_RETCODE SCIPsetBoolParam(SCIP *scip, const char *name, SCIP_Bool value)
Definition: scip_param.c:420
SCIP_STATUS SCIPgetStatus(SCIP *scip)
Definition: scip_general.c:474
SCIP_RETCODE SCIPpresolve(SCIP *scip)
Definition: scip_solve.c:2443
static SCIP_DECL_HEURINIT(heurInitLocks)
Definition: heur_locks.c:144
SCIP_RETCODE SCIPcopyCuts(SCIP *sourcescip, SCIP *targetscip, SCIP_HASHMAP *varmap, SCIP_HASHMAP *consmap, SCIP_Bool global, int *ncutsadded)
Definition: scip_copy.c:2116
BMS_BLKMEM * SCIPblkmem(SCIP *scip)
Definition: scip_mem.c:48
static SCIP_DECL_HEURCOPY(heurCopyLocks)
Definition: heur_locks.c:112
SCIP_RETCODE SCIPendProbing(SCIP *scip)
Definition: scip_probing.c:251
const char * SCIPvarGetName(SCIP_VAR *var)
Definition: var.c:17251
void SCIPhashmapFree(SCIP_HASHMAP **hashmap)
Definition: misc.c:3048
char * SCIPsnprintfProbingStats(SCIP *scip, char *strbuf, int len)
SCIP_RETCODE SCIPgetBoolParam(SCIP *scip, const char *name, SCIP_Bool *value)
Definition: scip_param.c:241
#define DEFAULT_NODESQUOT
Definition: heur_locks.c:71
#define DEFAULT_UPDATELOCKS
Definition: heur_locks.c:73
#define NULL
Definition: lpi_spx1.cpp:155
#define heurInitsolLocks
Definition: heur_locks.c:180
#define REALABS(x)
Definition: def.h:201
int SCIPgetNLPRows(SCIP *scip)
Definition: scip_lp.c:617
public methods for problem copies
int SCIPgetNUnfixedLPCols(SCIP *scip)
Definition: scip_lp.c:539
#define SCIP_CALL(x)
Definition: def.h:384
SCIP_Real SCIPgetLowerbound(SCIP *scip)
SCIP_Bool SCIPisFeasGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_RETCODE SCIPsolveProbingLP(SCIP *scip, int itlim, SCIP_Bool *lperror, SCIP_Bool *cutoff)
Definition: scip_probing.c:810
SCIP_Bool SCIPisFeasLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Real SCIProwGetRhs(SCIP_ROW *row)
Definition: lp.c:17268
void SCIPverbMessage(SCIP *scip, SCIP_VERBLEVEL msgverblevel, FILE *file, const char *formatstr,...)
Definition: scip_message.c:216
SCIP_Longint SCIPheurGetNCalls(SCIP_HEUR *heur)
Definition: heur.c:1567
SCIP_COL ** SCIProwGetCols(SCIP_ROW *row)
Definition: lp.c:17204
SCIP_Bool SCIPhasCurrentNodeLP(SCIP *scip)
Definition: scip_lp.c:74
public methods for primal heuristic plugins and divesets
public methods for constraint handler plugins and constraints
SCIP_RETCODE SCIPcreateRandom(SCIP *scip, SCIP_RANDNUMGEN **randnumgen, unsigned int initialseed, SCIP_Bool useglobalseed)
#define SCIPallocBufferArray(scip, ptr, num)
Definition: scip_mem.h:115
SCIP_Real * SCIProwGetVals(SCIP_ROW *row)
Definition: lp.c:17214
public data structures and miscellaneous methods
#define HEUR_FREQOFS
Definition: heur_locks.c:58
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
#define SCIP_Bool
Definition: def.h:84
SCIP_LPSOLSTAT SCIPgetLPSolstat(SCIP *scip)
Definition: scip_lp.c:159
#define HEUR_USESSUBSCIP
Definition: heur_locks.c:61
SCIP_RETCODE SCIProundSol(SCIP *scip, SCIP_SOL *sol, SCIP_Bool *success)
Definition: scip_sol.c:2446
SCIP_RETCODE SCIPsetObjlimit(SCIP *scip, SCIP_Real objlimit)
Definition: scip_prob.c:1421
#define DEFAULT_MAXPROPROUNDS
Definition: heur_locks.c:72
int SCIPgetDepth(SCIP *scip)
Definition: scip_tree.c:661
#define heurExitsolLocks
Definition: heur_locks.c:181
SCIP_RETCODE SCIPsetIntParam(SCIP *scip, const char *name, int value)
Definition: scip_param.c:478
public methods for LP management
SCIP_RETCODE SCIPincludeHeurLocks(SCIP *scip)
Definition: heur_locks.c:1076
SCIP_RETCODE SCIPfreeSol(SCIP *scip, SCIP_SOL **sol)
Definition: scip_sol.c:976
void SCIPenableVarHistory(SCIP *scip)
Definition: scip_var.c:8738
SCIP_Real SCIPvarGetObj(SCIP_VAR *var)
Definition: var.c:17758
int SCIPgetNSols(SCIP *scip)
Definition: scip_sol.c:2205
#define DEFAULT_USEFINALSUBMIP
Definition: heur_locks.c:77
int SCIPgetNRuns(SCIP *scip)
SCIP_COL * SCIPvarGetCol(SCIP_VAR *var)
Definition: var.c:17621
SCIP_RETCODE SCIPflushLP(SCIP *scip)
Definition: scip_lp.c:139
locks primal heuristic
SCIP_Bool SCIPisInfinity(SCIP *scip, SCIP_Real val)
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 SCIP_MAXTREEDEPTH
Definition: def.h:320
int SCIPgetNBinVars(SCIP *scip)
Definition: scip_prob.c:2036
SCIP_Real SCIPrandomGetReal(SCIP_RANDNUMGEN *randnumgen, SCIP_Real minrandval, SCIP_Real maxrandval)
Definition: misc.c:10025
SCIP_Bool SCIPinProbing(SCIP *scip)
Definition: scip_probing.c:88
public methods for the LP relaxation, rows and columns
int SCIProwGetRank(SCIP_ROW *row)
Definition: lp.c:17347
int SCIPgetNVars(SCIP *scip)
Definition: scip_prob.c:1991
#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
public methods for branching rule plugins and branching
general public methods
int SCIPcolGetNNonz(SCIP_COL *col)
Definition: lp.c:17092
SCIP_Real SCIPgetLPObjval(SCIP *scip)
Definition: scip_lp.c:238
SCIP_VAR * SCIPcolGetVar(SCIP_COL *col)
Definition: lp.c:17008
public methods for solutions
public methods for random numbers
int SCIPgetNConss(SCIP *scip)
Definition: scip_prob.c:3041
public methods for the probing mode
public methods for message output
SCIP_VAR ** SCIPgetVars(SCIP *scip)
Definition: scip_prob.c:1946
SCIP_VARSTATUS SCIPvarGetStatus(SCIP_VAR *var)
Definition: var.c:17370
int SCIProwGetLPPos(SCIP_ROW *row)
Definition: lp.c:17467
#define SCIP_Real
Definition: def.h:177
#define HEUR_TIMING
Definition: heur_locks.c:60
SCIP_Bool SCIPisStopped(SCIP *scip)
Definition: scip_general.c:694
SCIP_Real SCIPgetRowMinActivity(SCIP *scip, SCIP_ROW *row)
Definition: scip_lp.c:1924
int SCIPconshdlrGetNCheckConss(SCIP_CONSHDLR *conshdlr)
Definition: cons.c:4610
static SCIP_DECL_HEURFREE(heurFreeLocks)
Definition: heur_locks.c:126
public methods for message handling
SCIP_RETCODE SCIPprintRow(SCIP *scip, SCIP_ROW *row, FILE *file)
Definition: scip_lp.c:2197
#define SCIP_Longint
Definition: def.h:162
SCIP_RETCODE SCIPcheckCopyLimits(SCIP *sourcescip, SCIP_Bool *success)
Definition: scip_copy.c:3235
SCIP_VARTYPE SCIPvarGetType(SCIP_VAR *var)
Definition: var.c:17416
#define HEUR_MAXDEPTH
Definition: heur_locks.c:59
int SCIPgetNLPCols(SCIP *scip)
Definition: scip_lp.c:518
SCIP_Real SCIPvarGetUbLocal(SCIP_VAR *var)
Definition: var.c:17976
SCIP_RETCODE SCIPnewProbingNode(SCIP *scip)
Definition: scip_probing.c:156
SCIP_Real SCIPsumepsilon(SCIP *scip)
SCIP_Real SCIPgetUpperbound(SCIP *scip)
SCIP_RETCODE SCIPstartProbing(SCIP *scip)
Definition: scip_probing.c:110
public methods for primal heuristics
SCIP_RETCODE SCIPgetLPRowsData(SCIP *scip, SCIP_ROW ***rows, int *nrows)
Definition: scip_lp.c:561
SCIPallocBlockMemory(scip, subsol))
#define SCIP_CALL_ABORT(x)
Definition: def.h:363
SCIP_Real SCIPceil(SCIP *scip, SCIP_Real val)
SCIP_HEURDATA * SCIPheurGetData(SCIP_HEUR *heur)
Definition: heur.c:1352
SCIP_Longint SCIPgetNNodes(SCIP *scip)
public methods for global and local (sub)problems
SCIP_RETCODE SCIPaddRealParam(SCIP *scip, const char *name, const char *desc, SCIP_Real *valueptr, SCIP_Bool isadvanced, SCIP_Real defaultvalue, SCIP_Real minvalue, SCIP_Real maxvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition: scip_param.c:130
SCIP_RETCODE SCIPsetSubscipsOff(SCIP *scip, SCIP_Bool quiet)
Definition: scip_param.c:874
SCIP_RETCODE SCIPsetLongintParam(SCIP *scip, const char *name, SCIP_Longint value)
Definition: scip_param.c:536
SCIP_RETCODE SCIPaddBoolParam(SCIP *scip, const char *name, const char *desc, SCIP_Bool *valueptr, SCIP_Bool isadvanced, SCIP_Bool defaultvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition: scip_param.c:48
SCIP_RETCODE SCIPfree(SCIP **scip)
Definition: scip_general.c:315
#define DEFAULT_MINFIXINGRATE
Definition: heur_locks.c:65
SCIP_RETCODE SCIPcreateSol(SCIP *scip, SCIP_SOL **sol, SCIP_HEUR *heur)
Definition: scip_sol.c:319
memory allocation routines
SCIP_RETCODE SCIPprintSol(SCIP *scip, SCIP_SOL *sol, FILE *file, SCIP_Bool printzeros)
Definition: scip_sol.c:1766