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