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-2017 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 email to scip@zib.de. */
13 /* */
14 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
15 
16 /**@file heur_locks.c
17  * @brief rounding locks primal heuristic
18  * @author Michael Winkler
19  * @author Gerald Gamrath
20  */
21 
22 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
23 
24 #include <assert.h>
25 #include <string.h>
26 
27 #include "scip/heur_locks.h"
28 
29 #define HEUR_NAME "locks"
30 #define HEUR_DESC "heuristic that fixes variables based on their rounding locks"
31 #define HEUR_DISPCHAR 'k'
32 #define HEUR_PRIORITY 2000
33 #define HEUR_FREQ 0
34 #define HEUR_FREQOFS 0
35 #define HEUR_MAXDEPTH -1
36 #define HEUR_TIMING SCIP_HEURTIMING_BEFORENODE
37 #define HEUR_USESSUBSCIP TRUE /**< does the heuristic use a secondary SCIP instance? */
38 
39 #define DEFAULT_MAXNODES 5000LL /**< maximum number of nodes to regard in the subproblem */
40 #define DEFAULT_ROUNDUPPROBABILITY 0.67 /**< probability for rounding a variable up in case of ties */
41 #define DEFAULT_MINFIXINGRATE 0.25 /**< minimum percentage of variables that have to be fixed */
42 #define DEFAULT_MINIMPROVE 0.01 /**< factor by which locks heuristic should at least improve the
43  * incumbent
44  */
45 #define DEFAULT_MINNODES 500LL /**< minimum number of nodes to regard in the subproblem */
46 #define DEFAULT_NODESOFS 500LL /**< number of nodes added to the contingent of the total nodes */
47 #define DEFAULT_NODESQUOT 0.1 /**< subproblem nodes in relation to nodes of the original problem */
48 #define DEFAULT_MAXPROPROUNDS 2 /**< maximum number of propagation rounds during probing */
49 #define DEFAULT_UPDATELOCKS TRUE /**< should the locks be updated based on LP rows? */
50 #define DEFAULT_COPYCUTS TRUE /**< should all active cuts from the cutpool of the
51  * original scip be copied to constraints of the subscip? */
52 #define DEFAULT_USEFINALSUBMIP TRUE /**< should a final sub-MIP be solved to construct a feasible
53  * solution if the LP was not roundable? */
54 #define DEFAULT_RANDSEED 73 /**< initial random seed */
55 
56 /** primal heuristic data */
57 struct SCIP_HeurData
58 {
59  SCIP_RANDNUMGEN* randnumgen; /**< random number generation */
60  SCIP_Longint maxnodes; /**< maximum number of nodes to regard in the subproblem */
61  SCIP_Longint minnodes; /**< minimum number of nodes to regard in the subproblem */
62  SCIP_Longint nodesofs; /**< number of nodes added to the contingent of the total nodes */
63  SCIP_Longint usednodes; /**< nodes already used by locks heuristic in earlier calls */
64  SCIP_Real roundupprobability; /**< probability for rounding a variable up in case of ties */
65  SCIP_Real minfixingrate; /**< minimum percentage of variables that have to be fixed */
66  SCIP_Real minimprove; /**< factor by which locks heuristic should at least improve the incumbent */
67  SCIP_Real nodesquot; /**< subproblem nodes in relation to nodes of the original problem */
68  int maxproprounds; /**< maximum number of propagation rounds during probing */
69  SCIP_Bool updatelocks; /**< should the locks be updated based on LP rows? */
70  SCIP_Bool copycuts; /**< should all active cuts from cutpool be copied to constraints in
71  * the subproblem? */
72  SCIP_Bool usefinalsubmip; /**< should a final sub-MIP be solved to costruct a feasible solution if
73  * the LP was not roundable? */
74 };
75 
76 /*
77  * Local methods
78  */
79 
80 /** creates a new solution for the original problem by copying the solution of the subproblem */
81 static
83  SCIP* scip, /**< original SCIP data structure */
84  SCIP* subscip, /**< SCIP structure of the subproblem */
85  SCIP_VAR** subvars, /**< the variables of the subproblem */
86  SCIP_SOL* newsol, /**< working solution */
87  SCIP_SOL* subsol, /**< solution of the subproblem */
88  SCIP_Bool* success /**< used to store whether new solution was found or not */
89  )
90 {
91  SCIP_VAR** vars; /* the original problem's variables */
92  int nvars;
93  SCIP_Real* subsolvals; /* solution values of the subproblem */
94 
95  assert(scip != NULL);
96  assert(subscip != NULL);
97  assert(subvars != NULL);
98  assert(subsol != NULL);
99  assert(success != NULL);
100 
101  /* get variables' data */
102  SCIP_CALL( SCIPgetVarsData(scip, &vars, &nvars, NULL, NULL, NULL, NULL) );
103 
104  /* sub-SCIP may have more variables than the number of active (transformed) variables in the main SCIP
105  * since constraint copying may have required the copy of variables that are fixed in the main SCIP
106  */
107  assert(nvars <= SCIPgetNOrigVars(subscip));
108 
109  SCIP_CALL( SCIPallocBufferArray(scip, &subsolvals, nvars) );
110 
111  /* copy the solution */
112  SCIP_CALL( SCIPgetSolVals(subscip, subsol, nvars, subvars, subsolvals) );
113 
114  SCIP_CALL( SCIPsetSolVals(scip, newsol, nvars, vars, subsolvals) );
115 
116  /* try to add new solution to scip and free it immediately */
117  SCIP_CALL( SCIPtrySol(scip, newsol, FALSE, FALSE, TRUE, TRUE, TRUE, success) );
118 
119  SCIPfreeBufferArray(scip, &subsolvals);
120 
121  return SCIP_OKAY;
122 }
123 
124 /** copy method for primal heuristic plugins (called when SCIP copies plugins) */
125 static
126 SCIP_DECL_HEURCOPY(heurCopyLocks)
127 { /*lint --e{715}*/
128  assert(scip != NULL);
129  assert(heur != NULL);
130  assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0);
131 
132  /* call inclusion method of primal heuristic */
134 
135  return SCIP_OKAY;
136 }
137 
138 /** free method for primal heuristic plugins (called when SCIP is exiting) */
139 static
140 SCIP_DECL_HEURFREE(heurFreeLocks)
141 { /*lint --e{715}*/
142  SCIP_HEURDATA* heurdata;
143 
144  assert(scip != NULL);
145  assert(heur != NULL);
146  assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0);
147 
148  heurdata = SCIPheurGetData(heur);
149 
150  /* free primal heuristic data */
151  SCIPfreeBlockMemory(scip, &heurdata);
152 
153  return SCIP_OKAY;
154 }
155 
156 /** initialization method of primal heuristic (called after problem was transformed) */
157 static
158 SCIP_DECL_HEURINIT(heurInitLocks) /*lint --e{715}*/
159 { /*lint --e{715}*/
160  SCIP_HEURDATA* heurdata;
161 
162  assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0);
163  heurdata = SCIPheurGetData(heur);
164  assert(heurdata != NULL);
165 
166  /* initialize data */
167  heurdata->usednodes = 0;
168 
169  /* create random number generator */
170  SCIP_CALL( SCIPrandomCreate(&heurdata->randnumgen, SCIPblkmem(scip),
172 
173  return SCIP_OKAY;
174 }
175 
176 /** deinitialization method of primal heuristic (called before transformed problem is freed) */
177 static
178 SCIP_DECL_HEUREXIT(heurExitLocks) /*lint --e{715}*/
179 { /*lint --e{715}*/
180  SCIP_HEURDATA* heurdata;
181 
182  assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0);
183 
184  /* free heuristic data */
185  heurdata = SCIPheurGetData(heur);
186  assert(heurdata != NULL);
187 
188  /* free random number generator */
189  SCIPrandomFree(&heurdata->randnumgen);
190 
191  return SCIP_OKAY;
192 }
193 
194 #define heurInitsolLocks NULL
195 #define heurExitsolLocks NULL
196 
197 /** execution method of primal heuristic */
198 static
199 SCIP_DECL_HEUREXEC(heurExecLocks)
200 { /*lint --e{715}*/
201  SCIP_HEURDATA* heurdata;
202  SCIP_SOL* sol;
203  SCIP_ROW** lprows;
204  SCIP_VAR** vars;
205  SCIP_VAR** sortvars;
206  SCIP_Real* minact;
207  SCIP_Real* maxact;
208  SCIP_Bool* fulfilled;
209  SCIP_VAR* var;
210  SCIP_ROW* row;
211  SCIP_COL* col;
212  SCIP_ROW** colrows;
213  SCIP_Real* colvals;
214  int ncolrows;
215  int* ndownlocks;
216  int* nuplocks;
217  int* varpos = NULL;
218  SCIP_LPSOLSTAT lpstatus;
219  SCIP_Real lastfixval;
220  SCIP_Real randnumber;
221  SCIP_Real roundupprobability;
222  SCIP_Bool cutoff;
223  SCIP_Bool propagate;
224  SCIP_Bool propagated;
225  SCIP_Bool haslhs;
226  SCIP_Bool hasrhs;
227  SCIP_Bool updatelocks;
228  SCIP_Bool lperror;
229  int oldnpscands;
230  int npscands;
231  int lastfixlocks;
232  int maxproprounds;
233  int nglbfulfilledrows;
234  int rowpos;
235  int nbinvars;
236  int nvars;
237  int nlprows;
238  int nfulfilledrows;
239  int bestpos;
240  int lastbestscore;
241  int bestscore;
242  int score;
243  int v;
244  int r;
245  int i;
246 
247  *result = SCIP_DIDNOTRUN;
248 
249  /* only run once */
250  if( SCIPgetNRuns(scip) > 1 )
251  return SCIP_OKAY;
252 
253  if( SCIPgetNBinVars(scip) == 0 )
254  return SCIP_OKAY;
255 
256  cutoff = FALSE;
257  lperror = FALSE;
258 
259  heurdata = SCIPheurGetData(heur);
260  assert(heurdata != NULL);
261 
262  propagate = (heurdata->maxproprounds != 0);
263 
264  if( heurdata->maxproprounds == -2 )
265  maxproprounds = 0;
266  else
267  maxproprounds = heurdata->maxproprounds;
268 
269  roundupprobability = heurdata->roundupprobability;
270 
271  /* only run if we are allowed to solve an LP at the current node in the tree */
272  if( !SCIPhasCurrentNodeLP(scip) )
273  return SCIP_OKAY;
274 
275  if( !SCIPisLPConstructed(scip) )
276  {
277  SCIP_CALL( SCIPconstructLP(scip, &cutoff) );
278 
279  /* manually cut off the node if the LP construction detected infeasibility (heuristics cannot return such a result) */
280  if( cutoff )
281  {
283  return SCIP_OKAY;
284  }
285 
286  SCIP_CALL( SCIPflushLP(scip) );
287 
288  /* we need an LP */
289  if( SCIPgetNLPRows(scip) == 0 )
290  return SCIP_OKAY;
291  }
292 
293  *result = SCIP_DIDNOTFIND;
294 
295  updatelocks = heurdata->updatelocks && (SCIPgetNCheckConss(scip) == SCIPgetNLPRows(scip));
296 
297  SCIPdebugMsg(scip, "%d constraints: %d logicor, updatelocks=%d\n", SCIPgetNConss(scip), SCIPconshdlrGetNCheckConss(SCIPfindConshdlr(scip, "logicor")), updatelocks);
298 
299  SCIP_CALL( SCIPgetVarsData(scip, &vars, &nvars, &nbinvars, NULL, NULL, NULL) );
300  assert(vars != NULL);
301  oldnpscands = SCIPgetNPseudoBranchCands(scip);
302 
303  /* create solution */
304  SCIP_CALL( SCIPcreateSol(scip, &sol, heur) );
305 
306  /* allocate memory */
307  SCIP_CALL( SCIPduplicateBufferArray(scip, &sortvars, vars, nbinvars) );
308  SCIP_CALL( SCIPallocBufferArray(scip, &nuplocks, nbinvars) );
309  SCIP_CALL( SCIPallocBufferArray(scip, &ndownlocks, nbinvars) );
310 
311  /* get LP data */
312  SCIP_CALL( SCIPgetLPRowsData(scip, &lprows, &nlprows) );
313  SCIP_CALL( SCIPallocBufferArray(scip, &minact, nlprows) );
314  SCIP_CALL( SCIPallocBufferArray(scip, &maxact, nlprows) );
315  SCIP_CALL( SCIPallocClearBufferArray(scip, &fulfilled, nlprows) );
316 
317  /* @todo add objective value as second sorting criteria */
318 
319  nglbfulfilledrows = 0;
320 
321  /* get locks of variables */
322  for( v = 0; v < nbinvars; ++v )
323  {
324  var = sortvars[v];
325  nuplocks[v] = SCIPvarGetNLocksUp(var);
326  ndownlocks[v] = SCIPvarGetNLocksDown(var);
327  }
328 
329  /* get activities of rows */
330  for( r = 0; r < nlprows; ++r )
331  {
332  row = lprows[r];
333  assert(SCIProwGetLPPos(row) == r);
334 
335  /* no trivial rows */
336  assert(!SCIPisInfinity(scip, -SCIProwGetLhs(row)) || !SCIPisInfinity(scip, SCIProwGetRhs(row)));
337 
338  minact[r] = SCIPgetRowMinActivity(scip, row);
339  maxact[r] = SCIPgetRowMaxActivity(scip, row);
340  }
341 
342  /* start probing mode */
343  SCIP_CALL( SCIPstartProbing(scip) );
344  propagated = TRUE;
345  lastbestscore = INT_MAX;
346 
347  /* fix variables */
348  for( v = 0; v < nbinvars && !cutoff; v++ )
349  {
350  if( SCIPisStopped(scip) )
351  goto TERMINATE;
352 
353  nfulfilledrows = 0;
354 
355  while( v < nbinvars && (SCIPvarGetLbLocal(sortvars[v]) > 0.5 || SCIPvarGetUbLocal(sortvars[v]) < 0.5) )
356  {
357  ++v;
358  }
359  if( v == nbinvars )
360  break;
361 
362  bestpos = v;
363  bestscore = nuplocks[v] + ndownlocks[v];
364 
365  /* get best variable */
366  if( bestscore < lastbestscore )
367  {
368  for( i = v + 1; i < nbinvars; ++i )
369  {
370  var = sortvars[i];
371 
372  /* variable is already fixed; move it to the front and increment v to ignore it */
373  if( SCIPvarGetLbLocal(var) > 0.5 || SCIPvarGetUbLocal(var) < 0.5 )
374  {
375  int locks;
376 
377  sortvars[i] = sortvars[v];
378  sortvars[v] = var;
379 
380  locks = nuplocks[i];
381  nuplocks[i] = nuplocks[v];
382  nuplocks[v] = locks;
383 
384  locks = ndownlocks[i];
385  ndownlocks[i] = ndownlocks[v];
386  ndownlocks[v] = locks;
387 
388  if( varpos != NULL )
389  {
390  varpos[SCIPvarGetProbindex(sortvars[i])] = i;
391  varpos[SCIPvarGetProbindex(sortvars[v])] = v;
392  }
393 
394  if( bestpos == v )
395  bestpos = i;
396 
397  ++v;
398 
399  continue;
400  }
401 
402  score = nuplocks[i] + ndownlocks[i];
403  assert(score <= lastbestscore);
404 
405  if( score > bestscore )
406  {
407  bestscore = score;
408  bestpos = i;
409 
410  if( bestscore == lastbestscore )
411  break;
412  }
413  }
414  if( v == nbinvars )
415  break;
416  }
417  lastbestscore = bestscore;
418 
419  /* move best variable to the front (at position v) */
420  if( bestpos != v )
421  {
422  int locks;
423 
424  var = sortvars[bestpos];
425  sortvars[bestpos] = sortvars[v];
426  sortvars[v] = var;
427 
428  locks = nuplocks[bestpos];
429  nuplocks[bestpos] = nuplocks[v];
430  nuplocks[v] = locks;
431 
432  locks = ndownlocks[bestpos];
433  ndownlocks[bestpos] = ndownlocks[v];
434  ndownlocks[v] = locks;
435 
436  if( varpos != NULL )
437  {
438  varpos[SCIPvarGetProbindex(sortvars[bestpos])] = bestpos;
439  varpos[SCIPvarGetProbindex(sortvars[v])] = v;
440  }
441  }
442 
443  var = sortvars[v];
444 
445  /* all remaining variables are fixed, we can break the fix-and-propagate loop */
446  if( SCIPvarGetLbLocal(var) > 0.5 || SCIPvarGetUbLocal(var) < 0.5 )
447  {
448  assert(v == nbinvars);
449 
450  break;
451  }
452 
453  /* stop if we reached the depth limit */
454  if( SCIP_MAXTREEDEPTH <= SCIPgetDepth(scip) )
455  break;
456 
457  if( propagated )
458  {
459  SCIP_CALL( SCIPnewProbingNode(scip) );
460  propagated = FALSE;
461  }
462 
463  /* set variables to the bound with fewer locks, if tie choose an average value */
464  if( ndownlocks[v] > nuplocks[v] )
465  lastfixval = 1.0;
466  else if( ndownlocks[v] < nuplocks[v] )
467  lastfixval = 0.0;
468  else
469  {
470  /* prefer one-fixing if objective value is not positive */
471  if( !SCIPisPositive(scip, SCIPvarGetObj(var)) )
472  lastfixval = 1.0;
473  else
474  {
475  randnumber = SCIPrandomGetReal(heurdata->randnumgen, 0.0, 1.0);
476 
477  /* if a tie occurs, we randomly round the variable based on the parameter 'roundupprobability' */
478  if( randnumber < roundupprobability )
479  lastfixval = 1.0;
480  else
481  lastfixval = 0.0;
482  }
483  }
484 
485  lastfixlocks = lastfixval > 0.5 ? nuplocks[v] : ndownlocks[v];
486 
487  SCIP_CALL( SCIPfixVarProbing(scip, var, lastfixval) );
488 
489  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]);
490 
491  if( propagate && lastfixlocks > 0 )
492  {
493  /* apply propagation */
494  SCIP_CALL( SCIPpropagateProbing(scip, maxproprounds, &cutoff, NULL) );
495  propagated = TRUE;
496 
497  if( cutoff )
498  {
499  /* fix cutoff variable in other direction */
501  if( lastfixval < 0.5 )
502  {
503  if( SCIPvarGetUbLocal(var) > 0.5 )
504  {
505  SCIP_CALL( SCIPfixVarProbing(scip, var, 1.0) );
506  }
507  }
508  else
509  {
510  if( SCIPvarGetLbLocal(var) < 0.5 )
511  {
512  SCIP_CALL( SCIPfixVarProbing(scip, var, 0.0) );
513  }
514  }
515 
516  SCIPdebugMsg(scip, "last fixing led to infeasibility trying other bound\n");
517 
518  SCIP_CALL( SCIPpropagateProbing(scip, maxproprounds, &cutoff, NULL) );
519  if( cutoff )
520  break;
521  }
522  /* @todo collect propagated bounds and use them to update row activities as well */
523  }
524 
525  if( updatelocks )
526  {
527  col = SCIPvarGetCol(var);
528  assert(col != NULL);
529 
530  colrows = SCIPcolGetRows(col);
531  colvals = SCIPcolGetVals(col);
532  ncolrows = SCIPcolGetNNonz(col);
533 
534  /* update activities */
535  for( r = 0; r < ncolrows; ++r )
536  {
537  row = colrows[r];
538  rowpos = SCIProwGetLPPos(row);
539 
540  /* the row is not in the LP */
541  if( rowpos == -1 )
542  continue;
543 
544  assert(lprows[rowpos] == row);
545 
546  /* we disregard cuts */
547  if( SCIProwGetRank(row) > 0 )
548  continue;
549 
550  /* the row is already fulfilled */
551  if( fulfilled[rowpos] )
552  continue;
553 
554  haslhs = !SCIPisInfinity(scip, -SCIProwGetLhs(row));
555  hasrhs = !SCIPisInfinity(scip, SCIProwGetRhs(row));
556 
557  /* no trivial rows */
558  assert(hasrhs || haslhs);
559 
560  if( ((colvals[r] > 0) == (lastfixval < 0.5)) )
561  {
562  maxact[rowpos] -= REALABS(colvals[r]);
563  }
564  if( ((colvals[r] > 0) == (lastfixval > 0.5)) )
565  {
566  minact[rowpos] += REALABS(colvals[r]);
567  }
568 
569  /* check if the row cannot be violated anymore */
570  if( (!haslhs || SCIPisFeasGE(scip, minact[rowpos], SCIProwGetLhs(row)))
571  && (!hasrhs || SCIPisFeasLE(scip, maxact[rowpos], SCIProwGetRhs(row))) )
572  {
573  SCIP_COL** cols;
574  SCIP_VAR* colvar;
575  SCIP_Real* vals;
576  int ncols;
577  int pos;
578  int w;
579 
580  SCIPdebugMsg(scip, "Row <%s> has activity [%g, %g], lhs=%g, rhs=%g\n", SCIProwGetName(row), minact[rowpos], maxact[rowpos], SCIProwGetLhs(row), SCIProwGetRhs(row));
581  SCIPdebug( SCIP_CALL( SCIPprintRow(scip, row, NULL) ) );
582 
583  if( varpos == NULL )
584  {
585  SCIP_CALL( SCIPallocBufferArray(scip, &varpos, nbinvars) );
586 
587  for( pos = 0; pos < nbinvars; ++pos )
588  varpos[SCIPvarGetProbindex(sortvars[pos])] = pos;
589  }
590 
591  ++nfulfilledrows;
592  fulfilled[rowpos] = TRUE;
593  cols = SCIProwGetCols(row);
594  vals = SCIProwGetVals(row);
595  ncols = SCIProwGetNNonz(row);
596 
597  /* we assume that all rows are locking the variables */
598  for( w = ncols - 1; w >= 0; --w )
599  {
600  colvar = SCIPcolGetVar(cols[w]);
601  if( SCIPvarGetType(colvar) == SCIP_VARTYPE_BINARY && colvar != var )
602  {
603  assert(sortvars[varpos[SCIPvarGetProbindex(colvar)]] == colvar);
604  pos = varpos[SCIPvarGetProbindex(colvar)];
605 
606  if( haslhs )
607  {
608  if( vals[w] > 0.0 )
609  --(ndownlocks[pos]);
610  else
611  --(nuplocks[pos]);
612  }
613  if( hasrhs )
614  {
615  if( vals[w] > 0.0 )
616  --(nuplocks[pos]);
617  else
618  --(ndownlocks[pos]);
619  }
620  }
621  }
622 
623  continue;
624  }
625  else if( SCIPisFeasLT(scip, maxact[rowpos], SCIProwGetLhs(row)) || SCIPisFeasGT(scip, minact[rowpos], SCIProwGetRhs(row)) )
626  {
627  cutoff = TRUE;
628  SCIPdebug( SCIP_CALL( SCIPprintRow(scip, row, NULL) ) );
629  SCIPdebugMsg(scip, "row <%s> activity [%g,%g] violates bounds, lhs = %g, rhs = %g\n",
630  SCIProwGetName(row), minact[rowpos], maxact[rowpos], SCIProwGetLhs(row), SCIProwGetRhs(row));
631  break;
632  }
633  }
634 
635  if( cutoff )
636  {
637  SCIPdebugMsg(scip, "found infeasible row, stopping heur\n");
638  break;
639  }
640 
641  nglbfulfilledrows += nfulfilledrows;
642  SCIPdebugMsg(scip, "last fixing led to %d fulfilled rows, now %d of %d rows are fulfilled\n", nfulfilledrows, nglbfulfilledrows, nlprows);
643 
644  if( nglbfulfilledrows == nlprows )
645  break;
646  }
647  } /*lint --e{850}*/
648 
649  /* check that we had enough fixings */
650  npscands = SCIPgetNPseudoBranchCands(scip);
651 
652  SCIPdebugMsg(scip, "npscands=%d, oldnpscands=%d, heurdata->minfixingrate=%g\n", npscands, oldnpscands, heurdata->minfixingrate);
653 
654  if( nglbfulfilledrows != nlprows && npscands > oldnpscands * (1 - heurdata->minfixingrate) )
655  {
656  SCIPdebugMsg(scip, "--> too few fixings\n");
657 
658  goto TERMINATE;
659  }
660 
661  lpstatus = SCIP_LPSOLSTAT_ERROR;
662  if( !cutoff )
663  {
664  SCIPdebugMsg(scip, "solve probing LP in LOCKS heuristic: %d unfixed integer variables\n", SCIPgetNPseudoBranchCands(scip));
665 
666  /* solve LP;
667  * errors in the LP solver should not kill the overall solving process, if the LP is just needed for a heuristic.
668  * hence in optimized mode, the return code is caught and a warning is printed, only in debug mode, SCIP will stop.
669  */
670 #ifdef NDEBUG
671  {
672  SCIP_Bool retstat;
673  retstat = SCIPsolveProbingLP(scip, -1, &lperror, &cutoff);
674  if( retstat != SCIP_OKAY )
675  {
676  SCIPwarningMessage(scip, "Error while solving LP in LOCKS heuristic; LP solve terminated with code <%d>\n",
677  retstat);
678  }
679  }
680 #else
681  SCIP_CALL( SCIPsolveProbingLP(scip, -1, &lperror, &cutoff) );
682 #endif
683  assert(nvars == nbinvars ? (SCIPgetLPSolstat(scip) == SCIP_LPSOLSTAT_OPTIMAL || cutoff) : TRUE);
684 
685  lpstatus = SCIPgetLPSolstat(scip);
686 
687  SCIPdebugMsg(scip, " -> new LP iterations: %"SCIP_LONGINT_FORMAT"\n", SCIPgetNLPIterations(scip));
688  SCIPdebugMsg(scip, " -> error=%u, status=%d\n", lperror, SCIPgetLPSolstat(scip));
689 
690  /* check if this is a feasible solution */
691  if( !lperror && lpstatus == SCIP_LPSOLSTAT_OPTIMAL )
692  {
693  SCIP_Bool success;
694 
695  /* copy the current LP solution to the working solution */
696  SCIP_CALL( SCIPlinkLPSol(scip, sol) );
697 
698  SCIP_CALL( SCIProundSol(scip, sol, &success) );
699 
700  if( success )
701  {
702  SCIP_Bool stored;
703 
704  /* check solution for feasibility, and add it to solution store if possible.
705  * Neither integrality nor feasibility of LP rows have to be checked, because they
706  * are guaranteed by the heuristic at this stage.
707  */
708  SCIP_CALL( SCIPtrySol(scip, sol, FALSE, FALSE, FALSE, FALSE, FALSE, &stored) );
709 
710  if( stored )
711  {
712 #ifdef SCIP_MORE_DEBUG
713  SCIP_Bool feasible;
714  SCIP_CALL( SCIPcheckSol(scip, sol, TRUE, TRUE, TRUE, TRUE, TRUE, &feasible) );
715  assert(feasible);
716 #endif
717 
718  SCIPdebugMsg(scip, "found feasible solution:\n");
719  SCIPdebug(SCIP_CALL( SCIPprintSol(scip, sol, NULL, FALSE)) );
720  *result = SCIP_FOUNDSOL;
721  }
722 
723  /* we found a solution, so we are done */
724  goto TERMINATE;
725  }
726  }
727  }
728 
729  if( heurdata->usefinalsubmip && !cutoff && !lperror && lpstatus != SCIP_LPSOLSTAT_INFEASIBLE && lpstatus != SCIP_LPSOLSTAT_OBJLIMIT )
730  {
731  SCIP* subscip;
732  SCIP_VAR** subvars;
733  SCIP_HASHMAP* varmap;
734  SCIP_Longint nstallnodes;
735  SCIP_Bool valid;
736 
737  /* calculate the maximal number of branching nodes until heuristic is aborted */
738  nstallnodes = (SCIP_Longint)(heurdata->nodesquot * SCIPgetNNodes(scip));
739 
740  /* reward locks heuristic if it succeeded often */
741  nstallnodes = (SCIP_Longint)(nstallnodes * 3.0 * (SCIPheurGetNBestSolsFound(heur)+1.0)/(SCIPheurGetNCalls(heur) + 1.0));
742  nstallnodes -= 100 * SCIPheurGetNCalls(heur); /* count the setup costs for the sub-MIP as 100 nodes */
743  nstallnodes += heurdata->nodesofs;
744 
745  /* determine the node limit for the current process */
746  nstallnodes -= heurdata->usednodes;
747  nstallnodes = MIN(nstallnodes, heurdata->maxnodes);
748 
749  /* check whether we have enough nodes left to call subproblem solving */
750  if( nstallnodes < heurdata->minnodes )
751  {
752  SCIPdebugMsg(scip, "skipping " HEUR_NAME ": nstallnodes=%" SCIP_LONGINT_FORMAT ", minnodes=%" SCIP_LONGINT_FORMAT "\n", nstallnodes, heurdata->minnodes);
753  goto TERMINATE;
754  }
755 
756  /* check whether there is enough time and memory left */
757  SCIP_CALL( SCIPcheckCopyLimits(scip, &valid) );
758 
759  if( !valid )
760  goto TERMINATE;
761 
762  /* get all variables */
763  SCIP_CALL( SCIPgetVarsData(scip, &vars, &nvars, NULL, NULL, NULL, NULL) );
764 
765  /* create subproblem */
766  SCIP_CALL( SCIPcreate(&subscip) );
767 
768  /* allocate temporary memory for subscip variables */
769  SCIP_CALL( SCIPallocBufferArray(scip, &subvars, nvars) );
770 
771  /* create the variable mapping hash map */
772  SCIP_CALL( SCIPhashmapCreate(&varmap, SCIPblkmem(subscip), nvars) );
773 
774  SCIP_CALL( SCIPcopy(scip, subscip, varmap, NULL, "_locks", FALSE, FALSE, TRUE, &valid) );
775 
776  if( heurdata->copycuts )
777  {
778  /* copies all active cuts from cutpool of sourcescip to linear constraints in targetscip */
779  SCIP_CALL( SCIPcopyCuts(scip, subscip, varmap, NULL, FALSE, NULL) );
780  }
781 
782  for( i = 0; i < nvars; i++ )
783  subvars[i] = (SCIP_VAR*) SCIPhashmapGetImage(varmap, vars[i]);
784 
785  /* free hash map */
786  SCIPhashmapFree(&varmap);
787 
788  /* do not abort subproblem on CTRL-C */
789  SCIP_CALL( SCIPsetBoolParam(subscip, "misc/catchctrlc", FALSE) );
790 
791 #ifdef SCIP_DEBUG
792  /* for debugging, enable full output */
793  SCIP_CALL( SCIPsetIntParam(subscip, "display/verblevel", 5) );
794  SCIP_CALL( SCIPsetIntParam(subscip, "display/freq", 100000000) );
795 #else
796  /* disable statistic timing inside sub SCIP and output to console */
797  SCIP_CALL( SCIPsetIntParam(subscip, "display/verblevel", 0) );
798  SCIP_CALL( SCIPsetBoolParam(subscip, "timing/statistictiming", FALSE) );
799 #endif
800 
801  /* set limits for the subproblem */
802  SCIP_CALL( SCIPcopyLimits(scip, subscip) );
803  SCIP_CALL( SCIPsetLongintParam(subscip, "limits/stallnodes", nstallnodes) );
804  SCIP_CALL( SCIPsetLongintParam(subscip, "limits/nodes", heurdata->maxnodes) );
805 
806  /* forbid call of heuristics and separators solving sub-CIPs */
807  SCIP_CALL( SCIPsetSubscipsOff(subscip, TRUE) );
808 
809  /* disable cutting plane separation */
811 
812  /* disable expensive presolving */
814 
815  /* use inference branching */
816  if( SCIPfindBranchrule(subscip, "inference") != NULL && !SCIPisParamFixed(subscip, "branching/inference/priority") )
817  {
818  SCIP_CALL( SCIPsetIntParam(subscip, "branching/inference/priority", INT_MAX/4) );
819  }
820 
821  /* speed up sub-SCIP by not checking dual LP feasibility */
822  SCIP_CALL( SCIPsetBoolParam(subscip, "lp/checkdualfeas", FALSE) );
823 
824  /* employ a limit on the number of enforcement rounds in the quadratic constraint handler; this fixes the issue that
825  * sometimes the quadratic constraint handler needs hundreds or thousands of enforcement rounds to determine the
826  * feasibility status of a single node without fractional branching candidates by separation (namely for uflquad
827  * instances); however, the solution status of the sub-SCIP might get corrupted by this; hence no deductions shall be
828  * made for the original SCIP
829  */
830  if( SCIPfindConshdlr(subscip, "quadratic") != NULL && !SCIPisParamFixed(subscip, "constraints/quadratic/enfolplimit") )
831  {
832  SCIP_CALL( SCIPsetIntParam(subscip, "constraints/quadratic/enfolplimit", 10) );
833  }
834 
835  /* if there is already a solution, add an objective cutoff */
836  if( SCIPgetNSols(scip) > 0 )
837  {
838  SCIP_Real upperbound;
839  SCIP_Real minimprove;
840  SCIP_Real cutoffbound;
841 
842  minimprove = heurdata->minimprove;
843  assert( !SCIPisInfinity(scip,SCIPgetUpperbound(scip)) );
844 
845  upperbound = SCIPgetUpperbound(scip) - SCIPsumepsilon(scip);
846 
847  if( !SCIPisInfinity(scip, -1.0 * SCIPgetLowerbound(scip)) )
848  {
849  cutoffbound = (1-minimprove) * SCIPgetUpperbound(scip) + minimprove * SCIPgetLowerbound(scip);
850  }
851  else
852  {
853  if( SCIPgetUpperbound ( scip ) >= 0 )
854  cutoffbound = (1 - minimprove) * SCIPgetUpperbound(scip);
855  else
856  cutoffbound = (1 + minimprove) * SCIPgetUpperbound(scip);
857  }
858  cutoffbound = MIN(upperbound, cutoffbound);
859  SCIP_CALL( SCIPsetObjlimit(subscip, cutoffbound) );
860  SCIPdebugMsg(scip, "setting objlimit for subscip to %g\n", cutoffbound);
861  }
862 
863  SCIPdebugMsg(scip, "starting solving locks-submip at time %g\n", SCIPgetSolvingTime(scip));
864 
865  /* solve the subproblem */
866  /* Errors in the LP solver should not kill the overall solving process, if the LP is just needed for a heuristic.
867  * Hence in optimized mode, the return code is caught and a warning is printed, only in debug mode, SCIP will stop.
868  */
869 #ifdef NDEBUG
870  {
871  SCIP_RETCODE retstat;
872  retstat = SCIPpresolve(subscip);
873  if( retstat != SCIP_OKAY )
874  {
875  SCIPwarningMessage(scip, "Error while presolving subMIP in locks heuristic; sub-SCIP terminated with code <%d>\n", retstat);
876 
877  goto FREESCIPANDTERMINATE;
878  }
879  }
880 #else
881  SCIP_CALL_ABORT( SCIPpresolve(subscip) );
882 #endif
883 
884  SCIPdebugMsg(scip, "locks heuristic presolved subproblem: %d vars, %d cons; fixing value = %g\n", SCIPgetNVars(subscip), SCIPgetNConss(subscip), ((nvars - SCIPgetNVars(subscip)) / (SCIP_Real)nvars));
885 
886  /* after presolving, we should have at least reached a certain fixing rate over ALL variables (including continuous)
887  * to ensure that not only the MIP but also the LP relaxation is easy enough
888  */
889  if( ((nvars - SCIPgetNVars(subscip)) / (SCIP_Real)nvars) >= heurdata->minfixingrate )
890  {
891  SCIP_SOL** subsols;
892  SCIP_Bool success;
893  int nsubsols;
894 
895  SCIPdebugMsg(scip, "solving subproblem: nstallnodes=%" SCIP_LONGINT_FORMAT ", maxnodes=%" SCIP_LONGINT_FORMAT "\n", nstallnodes, heurdata->maxnodes);
896 
897 #ifdef NDEBUG
898  {
899  SCIP_RETCODE retstat;
900  retstat = SCIPsolve(subscip);
901  if( retstat != SCIP_OKAY )
902  {
903  SCIPwarningMessage(scip, "Error while solving subMIP in locks heuristic; sub-SCIP terminated with code <%d>\n",retstat);
904 
905  goto FREESCIPANDTERMINATE;
906  }
907  }
908 #else
909  SCIP_CALL_ABORT( SCIPsolve(subscip) );
910 #endif
911  SCIPdebugMsg(scip, "ending locks locks-submip at time %g, status = %d\n", SCIPgetSolvingTime(scip), SCIPgetStatus(subscip));
912 
913  /* check, whether a solution was found; due to numerics, it might happen that not all solutions are feasible ->
914  * try all solutions until one was accepted
915  */
916  nsubsols = SCIPgetNSols(subscip);
917  subsols = SCIPgetSols(subscip);
918  success = FALSE;
919 
920  for( i = 0; i < nsubsols && !success; ++i )
921  {
922  SCIP_CALL( createNewSol(scip, subscip, subvars, sol, subsols[i], &success) );
923  }
924  if( success )
925  *result = SCIP_FOUNDSOL;
926  }
927 
928 #ifdef SCIP_DEBUG
929  SCIP_CALL( SCIPprintStatistics(subscip, NULL) );
930 #endif
931 
932  heurdata->usednodes += SCIPgetNNodes(subscip);
933 #ifdef NDEBUG
934  FREESCIPANDTERMINATE:
935 #endif
936  /* free subproblem */
937  SCIPfreeBufferArray(scip, &subvars);
938  SCIP_CALL( SCIPfree(&subscip) );
939  }
940 
941 
942  TERMINATE:
943  /* exit probing mode */
944  SCIP_CALL( SCIPendProbing(scip) );
945 
946  SCIPfreeBufferArrayNull(scip, &varpos);
947  SCIPfreeBufferArray(scip, &fulfilled);
948  SCIPfreeBufferArray(scip, &maxact);
949  SCIPfreeBufferArray(scip, &minact);
950  SCIPfreeBufferArray(scip, &ndownlocks);
951  SCIPfreeBufferArray(scip, &nuplocks);
952  SCIPfreeBufferArray(scip, &sortvars);
953 
954  /* free all allocated memory */
955  SCIP_CALL( SCIPfreeSol(scip, &sol) );
956 
957  return SCIP_OKAY;
958 }
959 
960 
961 /*
962  * primal heuristic specific interface methods
963  */
964 
965 /** creates the locks primal heuristic and includes it in SCIP */
967  SCIP* scip /**< SCIP data structure */
968  )
969 {
970  SCIP_HEURDATA* heurdata;
971 
972  /* create primal heuristic data */
973  SCIP_CALL( SCIPallocBlockMemory(scip, &heurdata) );
974 
975  /* include primal heuristic */
978  heurCopyLocks,
979  heurFreeLocks, heurInitLocks, heurExitLocks,
980  heurInitsolLocks, heurExitsolLocks, heurExecLocks,
981  heurdata) );
982 
983  SCIP_CALL( SCIPaddIntParam(scip, "heuristics/" HEUR_NAME "/maxproprounds",
984  "maximum number of propagation rounds to be performed in each propagation call (-1: no limit, -2: parameter settings)",
985  &heurdata->maxproprounds, TRUE, DEFAULT_MAXPROPROUNDS, -2, INT_MAX, NULL, NULL) );
986 
987  SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/minfixingrate",
988  "minimum percentage of integer variables that have to be fixable",
989  &heurdata->minfixingrate, FALSE, DEFAULT_MINFIXINGRATE, 0.0, 1.0, NULL, NULL) );
990 
991  SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/roundupprobability",
992  "probability for rounding a variable up in case of ties",
993  &heurdata->roundupprobability, FALSE, DEFAULT_ROUNDUPPROBABILITY, 0.0, 1.0, NULL, NULL) );
994 
995  SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/usefinalsubmip",
996  "should a final sub-MIP be solved to costruct a feasible solution if the LP was not roundable?",
997  &heurdata->usefinalsubmip, TRUE, DEFAULT_USEFINALSUBMIP, NULL, NULL) );
998 
999  SCIP_CALL( SCIPaddLongintParam(scip, "heuristics/" HEUR_NAME "/maxnodes",
1000  "maximum number of nodes to regard in the subproblem",
1001  &heurdata->maxnodes, TRUE, DEFAULT_MAXNODES, 0LL, SCIP_LONGINT_MAX, NULL, NULL) );
1002 
1003  SCIP_CALL( SCIPaddLongintParam(scip, "heuristics/" HEUR_NAME "/nodesofs",
1004  "number of nodes added to the contingent of the total nodes",
1005  &heurdata->nodesofs, FALSE, DEFAULT_NODESOFS, 0LL, SCIP_LONGINT_MAX, NULL, NULL) );
1006 
1007  SCIP_CALL( SCIPaddLongintParam(scip, "heuristics/" HEUR_NAME "/minnodes",
1008  "minimum number of nodes required to start the subproblem",
1009  &heurdata->minnodes, TRUE, DEFAULT_MINNODES, 0LL, SCIP_LONGINT_MAX, NULL, NULL) );
1010 
1011  SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/nodesquot",
1012  "contingent of sub problem nodes in relation to the number of nodes of the original problem",
1013  &heurdata->nodesquot, FALSE, DEFAULT_NODESQUOT, 0.0, 1.0, NULL, NULL) );
1014 
1015  SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/minimprove",
1016  "factor by which " HEUR_NAME " heuristic should at least improve the incumbent",
1017  &heurdata->minimprove, TRUE, DEFAULT_MINIMPROVE, 0.0, 1.0, NULL, NULL) );
1018 
1019  SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/copycuts",
1020  "should all active cuts from cutpool be copied to constraints in subproblem?",
1021  &heurdata->copycuts, TRUE, DEFAULT_COPYCUTS, NULL, NULL) );
1022 
1023  SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/updatelocks",
1024  "should the locks be updated based on LP rows?",
1025  &heurdata->updatelocks, TRUE, DEFAULT_UPDATELOCKS, NULL, NULL) );
1026 
1027  return SCIP_OKAY;
1028 }
#define DEFAULT_NODESOFS
Definition: heur_locks.c:48
int SCIPgetNCheckConss(SCIP *scip)
Definition: scip.c:12821
SCIP_RETCODE SCIPrandomCreate(SCIP_RANDNUMGEN **randnumgen, BMS_BLKMEM *blkmem, unsigned int initialseed)
Definition: misc.c:8693
SCIP_RETCODE SCIPlinkLPSol(SCIP *scip, SCIP_SOL *sol)
Definition: scip.c:37672
SCIP_Real SCIPgetSolvingTime(SCIP *scip)
Definition: scip.c:45137
SCIP_RETCODE SCIPsetSeparating(SCIP *scip, SCIP_PARAMSETTING paramsetting, SCIP_Bool quiet)
Definition: scip.c:5095
#define DEFAULT_MINIMPROVE
Definition: heur_locks.c:42
SCIP_NODE * SCIPgetCurrentNode(SCIP *scip)
Definition: scip.c:40453
SCIP_RETCODE SCIPbacktrackProbing(SCIP *scip, int probingdepth)
Definition: scip.c:35152
SCIP_Longint SCIPgetNLPIterations(SCIP *scip)
Definition: scip.c:41382
SCIP_Bool SCIPisFeasLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip.c:46099
SCIP_CONSHDLR * SCIPfindConshdlr(SCIP *scip, const char *name)
Definition: scip.c:6541
int SCIPgetProbingDepth(SCIP *scip)
Definition: scip.c:35125
#define SCIPallocClearBufferArray(scip, ptr, num)
Definition: scip.h:21927
SCIP_Longint SCIPheurGetNBestSolsFound(SCIP_HEUR *heur)
Definition: heur.c:1327
SCIP_Real * SCIPcolGetVals(SCIP_COL *col)
Definition: lp.c:16190
int SCIProwGetNNonz(SCIP_ROW *row)
Definition: lp.c:16232
SCIP_Bool SCIPisPositive(SCIP *scip, SCIP_Real val)
Definition: scip.c:45876
int SCIPgetNOrigVars(SCIP *scip)
Definition: scip.c:12071
SCIP_Real SCIPvarGetLbLocal(SCIP_VAR *var)
Definition: var.c:17222
int SCIPgetNPseudoBranchCands(SCIP *scip)
Definition: scip.c:36492
const char * SCIProwGetName(SCIP_ROW *row)
Definition: lp.c:16370
static SCIP_DECL_HEUREXEC(heurExecLocks)
Definition: heur_locks.c:203
static SCIP_RETCODE createNewSol(SCIP *scip, SCIP *subscip, SCIP_VAR **subvars, SCIP_SOL *newsol, SCIP_SOL *subsol, SCIP_Bool *success)
Definition: heur_locks.c:86
SCIP_Bool SCIPisFeasGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip.c:46138
SCIP_RETCODE SCIPgetVarsData(SCIP *scip, SCIP_VAR ***vars, int *nvars, int *nbinvars, int *nintvars, int *nimplvars, int *ncontvars)
Definition: scip.c:11505
SCIP_SOL ** SCIPgetSols(SCIP *scip)
Definition: scip.c:38881
SCIP_Real SCIProwGetLhs(SCIP_ROW *row)
Definition: lp.c:16311
#define FALSE
Definition: def.h:64
SCIP_RETCODE SCIPhashmapCreate(SCIP_HASHMAP **hashmap, BMS_BLKMEM *blkmem, int mapsize)
Definition: misc.c:2765
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.c:4230
SCIP_RETCODE SCIPcopyLimits(SCIP *sourcescip, SCIP *targetscip)
Definition: scip.c:4126
#define DEFAULT_RANDSEED
Definition: heur_locks.c:58
SCIP_RETCODE SCIPcutoffNode(SCIP *scip, SCIP_NODE *node)
Definition: scip.c:40796
#define TRUE
Definition: def.h:63
#define SCIPdebug(x)
Definition: pub_message.h:74
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:53
#define HEUR_DESC
Definition: heur_locks.c:30
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.c:7949
SCIP_RETCODE SCIPsetPresolving(SCIP *scip, SCIP_PARAMSETTING paramsetting, SCIP_Bool quiet)
Definition: scip.c:5069
SCIP_BRANCHRULE * SCIPfindBranchrule(SCIP *scip, const char *name)
Definition: scip.c:9184
int SCIPvarGetProbindex(SCIP_VAR *var)
Definition: var.c:16859
struct SCIP_HeurData SCIP_HEURDATA
Definition: type_heur.h:51
#define SCIPfreeBlockMemory(scip, ptr)
Definition: scip.h:21907
#define HEUR_FREQ
Definition: heur_locks.c:33
#define SCIPduplicateBufferArray(scip, ptr, source, num)
Definition: scip.h:21933
void * SCIPhashmapGetImage(SCIP_HASHMAP *hashmap, void *origin)
Definition: misc.c:2903
SCIP_RETCODE SCIPconstructLP(SCIP *scip, SCIP_Bool *cutoff)
Definition: scip.c:28810
#define SCIP_LONGINT_MAX
Definition: def.h:121
#define SCIPfreeBufferArray(scip, ptr)
Definition: scip.h:21937
enum SCIP_LPSolStat SCIP_LPSOLSTAT
Definition: type_lp.h:42
SCIP_RETCODE SCIPcreate(SCIP **scip)
Definition: scip.c:696
#define SCIPallocBlockMemory(scip, ptr)
Definition: scip.h:21890
void SCIPwarningMessage(SCIP *scip, const char *formatstr,...)
Definition: scip.c:1260
#define SCIPdebugMsg
Definition: scip.h:451
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.c:4202
#define DEFAULT_COPYCUTS
Definition: heur_locks.c:52
SCIP_RETCODE SCIPprintStatistics(SCIP *scip, FILE *file)
Definition: scip.c:44425
static SCIP_DECL_HEUREXIT(heurExitLocks)
Definition: heur_locks.c:182
#define DEFAULT_MINNODES
Definition: heur_locks.c:47
SCIP_Real SCIPgetRowMaxActivity(SCIP *scip, SCIP_ROW *row)
Definition: scip.c:30525
#define DEFAULT_ROUNDUPPROBABILITY
Definition: heur_locks.c:40
#define DEFAULT_MAXNODES
Definition: heur_locks.c:39
SCIP_Bool SCIPisLPConstructed(SCIP *scip)
Definition: scip.c:28787
void SCIPrandomFree(SCIP_RANDNUMGEN **randnumgen)
Definition: misc.c:8710
SCIP_RETCODE SCIPsolve(SCIP *scip)
Definition: scip.c:15777
const char * SCIPheurGetName(SCIP_HEUR *heur)
Definition: heur.c:1181
SCIP_Bool SCIPisParamFixed(SCIP *scip, const char *name)
Definition: scip.c:4338
SCIP_ROW ** SCIPcolGetRows(SCIP_COL *col)
Definition: lp.c:16180
SCIP_RETCODE SCIPpropagateProbing(SCIP *scip, int maxproprounds, SCIP_Bool *cutoff, SCIP_Longint *ndomredsfound)
Definition: scip.c:35477
SCIP_RETCODE SCIPgetSolVals(SCIP *scip, SCIP_SOL *sol, int nvars, SCIP_VAR **vars, SCIP_Real *vals)
Definition: scip.c:38044
SCIP_RETCODE SCIPfixVarProbing(SCIP *scip, SCIP_VAR *var, SCIP_Real fixedval)
Definition: scip.c:35337
#define SCIPfreeBufferArrayNull(scip, ptr)
Definition: scip.h:21938
SCIP_RETCODE SCIPsetBoolParam(SCIP *scip, const char *name, SCIP_Bool value)
Definition: scip.c:4567
SCIP_STATUS SCIPgetStatus(SCIP *scip)
Definition: scip.c:921
SCIP_RETCODE SCIPpresolve(SCIP *scip)
Definition: scip.c:15616
static SCIP_DECL_HEURINIT(heurInitLocks)
Definition: heur_locks.c:162
SCIP_RETCODE SCIPcopyCuts(SCIP *sourcescip, SCIP *targetscip, SCIP_HASHMAP *varmap, SCIP_HASHMAP *consmap, SCIP_Bool global, int *ncutsadded)
Definition: scip.c:3056
BMS_BLKMEM * SCIPblkmem(SCIP *scip)
Definition: scip.c:45519
static SCIP_DECL_HEURCOPY(heurCopyLocks)
Definition: heur_locks.c:130
SCIP_RETCODE SCIPendProbing(SCIP *scip)
Definition: scip.c:35187
const char * SCIPvarGetName(SCIP_VAR *var)
Definition: var.c:16552
void SCIPhashmapFree(SCIP_HASHMAP **hashmap)
Definition: misc.c:2798
#define DEFAULT_NODESQUOT
Definition: heur_locks.c:49
#define DEFAULT_UPDATELOCKS
Definition: heur_locks.c:51
#define NULL
Definition: lpi_spx1.cpp:137
#define heurInitsolLocks
Definition: heur_locks.c:198
#define REALABS(x)
Definition: def.h:159
int SCIPgetNLPRows(SCIP *scip)
Definition: scip.c:29221
#define SCIP_CALL(x)
Definition: def.h:306
SCIP_Real SCIPgetLowerbound(SCIP *scip)
Definition: scip.c:42323
SCIP_Bool SCIPisFeasGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip.c:46125
SCIP_RETCODE SCIPsolveProbingLP(SCIP *scip, int itlim, SCIP_Bool *lperror, SCIP_Bool *cutoff)
Definition: scip.c:35713
SCIP_Bool SCIPisFeasLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip.c:46112
SCIP_Real SCIProwGetRhs(SCIP_ROW *row)
Definition: lp.c:16321
SCIP_Longint SCIPheurGetNCalls(SCIP_HEUR *heur)
Definition: heur.c:1307
SCIP_COL ** SCIProwGetCols(SCIP_ROW *row)
Definition: lp.c:16257
SCIP_Bool SCIPhasCurrentNodeLP(SCIP *scip)
Definition: scip.c:28769
#define SCIPallocBufferArray(scip, ptr, num)
Definition: scip.h:21925
SCIP_Real * SCIProwGetVals(SCIP_ROW *row)
Definition: lp.c:16267
#define HEUR_FREQOFS
Definition: heur_locks.c:34
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.c:40029
#define SCIP_Bool
Definition: def.h:61
SCIP_LPSOLSTAT SCIPgetLPSolstat(SCIP *scip)
Definition: scip.c:28854
#define HEUR_USESSUBSCIP
Definition: heur_locks.c:37
SCIP_RETCODE SCIProundSol(SCIP *scip, SCIP_SOL *sol, SCIP_Bool *success)
Definition: scip.c:39073
SCIP_RETCODE SCIPsetObjlimit(SCIP *scip, SCIP_Real objlimit)
Definition: scip.c:11078
#define DEFAULT_MAXPROPROUNDS
Definition: heur_locks.c:50
int SCIPgetDepth(SCIP *scip)
Definition: scip.c:42094
int SCIPvarGetNLocksUp(SCIP_VAR *var)
Definition: var.c:3217
#define heurExitsolLocks
Definition: heur_locks.c:199
SCIP_RETCODE SCIPsetIntParam(SCIP *scip, const char *name, int value)
Definition: scip.c:4625
SCIP_RETCODE SCIPincludeHeurLocks(SCIP *scip)
Definition: heur_locks.c:970
unsigned int SCIPinitializeRandomSeed(SCIP *scip, int initialseedvalue)
Definition: scip.c:25467
SCIP_RETCODE SCIPfreeSol(SCIP *scip, SCIP_SOL **sol)
Definition: scip.c:37631
SCIP_Real SCIPvarGetObj(SCIP_VAR *var)
Definition: var.c:17014
int SCIPgetNSols(SCIP *scip)
Definition: scip.c:38832
#define DEFAULT_USEFINALSUBMIP
Definition: heur_locks.c:55
int SCIPgetNRuns(SCIP *scip)
Definition: scip.c:41099
SCIP_COL * SCIPvarGetCol(SCIP_VAR *var)
Definition: var.c:16880
SCIP_RETCODE SCIPflushLP(SCIP *scip)
Definition: scip.c:28834
locks primal heuristic
SCIP_Bool SCIPisInfinity(SCIP *scip, SCIP_Real val)
Definition: scip.c:45827
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.c:39749
#define SCIP_MAXTREEDEPTH
Definition: def.h:242
int SCIPgetNBinVars(SCIP *scip)
Definition: scip.c:11676
SCIP_Real SCIPrandomGetReal(SCIP_RANDNUMGEN *randnumgen, SCIP_Real minrandval, SCIP_Real maxrandval)
Definition: misc.c:8745
int SCIProwGetRank(SCIP_ROW *row)
Definition: lp.c:16400
int SCIPgetNVars(SCIP *scip)
Definition: scip.c:11631
#define HEUR_PRIORITY
Definition: heur_locks.c:32
#define HEUR_DISPCHAR
Definition: heur_locks.c:31
#define HEUR_NAME
Definition: heur_locks.c:29
int SCIPcolGetNNonz(SCIP_COL *col)
Definition: lp.c:16155
int SCIPvarGetNLocksDown(SCIP_VAR *var)
Definition: var.c:3162
SCIP_VAR * SCIPcolGetVar(SCIP_COL *col)
Definition: lp.c:16081
int SCIPgetNConss(SCIP *scip)
Definition: scip.c:12679
SCIP_RETCODE SCIPcopy(SCIP *sourcescip, SCIP *targetscip, SCIP_HASHMAP *varmap, SCIP_HASHMAP *consmap, const char *suffix, SCIP_Bool global, SCIP_Bool enablepricing, SCIP_Bool passmessagehdlr, SCIP_Bool *valid)
Definition: scip.c:3757
int SCIProwGetLPPos(SCIP_ROW *row)
Definition: lp.c:16500
#define SCIP_Real
Definition: def.h:135
#define HEUR_TIMING
Definition: heur_locks.c:36
SCIP_Bool SCIPisStopped(SCIP *scip)
Definition: scip.c:1138
#define MIN(x, y)
Definition: memory.c:75
SCIP_Real SCIPgetRowMinActivity(SCIP *scip, SCIP_ROW *row)
Definition: scip.c:30508
int SCIPconshdlrGetNCheckConss(SCIP_CONSHDLR *conshdlr)
Definition: cons.c:4535
static SCIP_DECL_HEURFREE(heurFreeLocks)
Definition: heur_locks.c:144
SCIP_RETCODE SCIPprintRow(SCIP *scip, SCIP_ROW *row, FILE *file)
Definition: scip.c:30762
#define SCIP_Longint
Definition: def.h:120
SCIP_RETCODE SCIPcheckCopyLimits(SCIP *sourcescip, SCIP_Bool *success)
Definition: scip.c:4090
SCIP_VARTYPE SCIPvarGetType(SCIP_VAR *var)
Definition: var.c:16717
SCIP_RETCODE SCIPsetSolVals(SCIP *scip, SCIP_SOL *sol, int nvars, SCIP_VAR **vars, SCIP_Real *vals)
Definition: scip.c:37909
#define HEUR_MAXDEPTH
Definition: heur_locks.c:35
SCIP_Real SCIPvarGetUbLocal(SCIP_VAR *var)
Definition: var.c:17232
SCIP_RETCODE SCIPnewProbingNode(SCIP *scip)
Definition: scip.c:35092
SCIP_Real SCIPsumepsilon(SCIP *scip)
Definition: scip.c:45260
SCIP_Real SCIPgetUpperbound(SCIP *scip)
Definition: scip.c:42472
SCIP_RETCODE SCIPstartProbing(SCIP *scip)
Definition: scip.c:35055
SCIP_RETCODE SCIPgetLPRowsData(SCIP *scip, SCIP_ROW ***rows, int *nrows)
Definition: scip.c:29165
#define SCIP_CALL_ABORT(x)
Definition: def.h:285
SCIP_HEURDATA * SCIPheurGetData(SCIP_HEUR *heur)
Definition: heur.c:1092
SCIP_Longint SCIPgetNNodes(SCIP *scip)
Definition: scip.c:41182
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.c:4258
SCIP_RETCODE SCIPsetSubscipsOff(SCIP *scip, SCIP_Bool quiet)
Definition: scip.c:5020
SCIP_RETCODE SCIPsetLongintParam(SCIP *scip, const char *name, SCIP_Longint value)
Definition: scip.c:4683
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.c:4176
SCIP_RETCODE SCIPfree(SCIP **scip)
Definition: scip.c:774
#define DEFAULT_MINFIXINGRATE
Definition: heur_locks.c:41
SCIP_RETCODE SCIPcreateSol(SCIP *scip, SCIP_SOL **sol, SCIP_HEUR *heur)
Definition: scip.c:37005
SCIP_RETCODE SCIPprintSol(SCIP *scip, SCIP_SOL *sol, FILE *file, SCIP_Bool printzeros)
Definition: scip.c:38421