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