Scippy

SCIP

Solving Constraint Integer Programs

heur_lpface.c
Go to the documentation of this file.
1 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
2 /* */
3 /* This file is part of the program and library */
4 /* SCIP --- Solving Constraint Integer Programs */
5 /* */
6 /* Copyright (C) 2002-2017 Konrad-Zuse-Zentrum */
7 /* fuer Informationstechnik Berlin */
8 /* */
9 /* SCIP is distributed under the terms of the ZIB Academic License. */
10 /* */
11 /* You should have received a copy of the ZIB Academic License */
12 /* along with SCIP; see the file COPYING. If not email to scip@zib.de. */
13 /* */
14 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
15 
16 /**@file heur_lpface.c
17  * @brief lpface primal heuristic that searches the optimal LP face inside a sub-MIP
18  * @author Gregor Hendel
19  */
20 
21 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
22 
23 #include <assert.h>
24 #include <string.h>
25 #include <stdio.h>
26 #include "scip/scip.h"
27 #include "scip/scipdefplugins.h"
28 #include "scip/cons_linear.h"
29 #include "scip/heur_lpface.h"
30 #include "scip/pub_misc.h"
31 
32 #define HEUR_NAME "lpface"
33 #define HEUR_DESC "LNS heuristic that searches the optimal LP face inside a sub-MIP"
34 #define HEUR_DISPCHAR '_'
35 #define HEUR_PRIORITY -1104000
36 #define HEUR_FREQ 15
37 #define HEUR_FREQOFS 0
38 #define HEUR_MAXDEPTH -1
39 #define HEUR_TIMING SCIP_HEURTIMING_AFTERLPNODE
40 #define HEUR_USESSUBSCIP TRUE /**< does the heuristic use a secondary SCIP instance? */
41 
42 #define DEFAULT_MAXNODES 5000LL /**< maximum number of nodes to regard in the subproblem */
43 #define DEFAULT_MINNODES 50LL /**< minimum number of nodes to regard in the subproblem */
44 #define DEFAULT_MINFIXINGRATE 0.1 /**< required percentage of fixed integer variables in sub-MIP to run */
45 #define DEFAULT_NODESOFS 200LL /**< number of nodes added to the contingent of the total nodes */
46 #define DEFAULT_NODESQUOT 0.1 /**< subproblem nodes in relation to nodes of the original problem */
47 #define DEFAULT_LPLIMFAC 2.0 /**< factor by which the limit on the number of LP depends on the node limit */
48 #define DEFAULT_USELPROWS TRUE /**< should subproblem be created out of the rows in the LP rows,
49  * otherwise, the copy constructors of the constraints handlers are used */
50 #define DEFAULT_COPYCUTS TRUE /**< if uselprows == FALSE, should all active cuts from cutpool be copied
51  * to constraints in subproblem? */
52 #define DEFAULT_DUALBASISEQUATIONS FALSE /**< should the dually nonbasic rows be turned into equations? */
53 #define DEFAULT_KEEPSUBSCIP FALSE /**< should the heuristic continue solving the same sub-SCIP? */
54 #define DEFAULT_MINPATHLEN 5 /**< the minimum active search tree path length along which the lower bound
55  * hasn't changed before heuristic becomes active */
56 /* event handler properties */
57 #define EVENTHDLR_NAME "Lpface"
58 #define EVENTHDLR_DESC "LP event handler for " HEUR_NAME " heuristic"
59 
60 /*
61  * Data structures
62  */
63 
64 /** data structure to keep sub-SCIP across runs */
65 struct SubscipData
66 {
67  SCIP* subscip; /**< pointer to store sub-SCIP data structure */
68  SCIP_VAR** subvars; /**< array of variables of the sub-problem */
69  int nsubvars; /**< number of sub-problem variables */
70  SCIP_Real objbound; /**< lower bound on objective for when sub SCIP was created */
71 };
72 typedef struct SubscipData SUBSCIPDATA;
73 
74 /** primal heuristic data */
75 struct SCIP_HeurData
76 {
77  SCIP_Longint maxnodes; /**< maximum number of nodes to regard in the subproblem */
78  SCIP_Longint minnodes; /**< minimum number of nodes to regard in the subproblem */
79  SCIP_Longint nodesofs; /**< number of nodes added to the contingent of the total nodes */
80  SCIP_Longint usednodes; /**< nodes already used by lpface in earlier calls */
81  SCIP_Real nodesquot; /**< subproblem nodes in relation to nodes of the original problem */
82 
83  unsigned int nfailures; /**< number of failures since last successful call */
84  SCIP_Longint nextnodenumber; /**< number of nodes at which lpface should be called the next time */
85  SCIP_Real lastlpobjinfeas; /**< last LP objective where the sub-MIP was run to proven infeasibility */
86  SCIP_Real minfixingrate; /**< required percentage of fixed integer variables in sub-MIP to run */
87  SCIP_Real nodelimit; /**< the nodelimit employed in the current sub-SCIP, for the event handler*/
88  SCIP_Real lplimfac; /**< factor by which the limit on the number of LP depends on the node limit */
89  SCIP_Bool uselprows; /**< should subproblem be created out of the rows in the LP rows? */
90  SCIP_Bool copycuts; /**< if uselprows == FALSE, should all active cuts from cutpool be copied
91  * to constraints in subproblem? */
92  SCIP_Bool dualbasisequations; /**< should the dually nonbasic rows be turned into equations? */
93  SCIP_Bool keepsubscip; /**< should the heuristic continue solving the same sub-SCIP? */
94  char subscipobjective; /**< objective function in the sub-SCIP: (z)ero, (r)oot-LP-difference,
95  * (i)nference, LP (f)ractionality, (o)riginal */
96 
97  SCIP_STATUS submipstatus; /**< return status of the sub-MIP */
98  SCIP_Longint submipnlpiters; /**< number of LP iterations of the sub-MIP */
99  SCIP_Real submippresoltime; /**< time required to presolve the sub-MIP */
100  int nvarsfixed; /**< the number of fixed variables by the heuristic */
101  int minpathlen; /**< the minimum active search tree path length along which the lower bound
102  * hasn't changed before heuristic becomes active */
103  SUBSCIPDATA* subscipdata; /**< sub-SCIP data structure */
104 };
105 
106 /*
107  * Local methods
108  */
109 
110 /** fixes variables of the subproblem considering their reduced costs */
111 static
113  SCIP* scip, /**< original SCIP data structure */
114  SCIP* subscip, /**< SCIP data structure for the subproblem */
115  SCIP_VAR** subvars, /**< the variables of the subproblem */
116  SCIP_HEURDATA* heurdata, /**< primal heuristic data */
117  SCIP_Bool* success /**< pointer to store whether enough integer variables were fixed */
118  )
119 {
120  SCIP_VAR** vars; /* original scip variables */
121  SCIP_Real fixingrate; /* percentage of variables that are fixed */
122  int nvars;
123  int nbinvars;
124  int nintvars;
125  int i;
126  int fixingcounter;
127 
128  /* get required data of the main scip problem */
129  SCIP_CALL( SCIPgetVarsData(scip, &vars, &nvars, &nbinvars, &nintvars, NULL, NULL) );
130 
131  fixingcounter = 0;
132 
133  assert(nvars >= nbinvars + nintvars);
134 
135  /* loop over problem variables and fix all with nonzero reduced costs to their solution value */
136  for( i = 0; i < nvars; i++ )
137  {
138  SCIP_Real solval;
139  SCIP_COL* col;
140  SCIP_Real redcost;
141  SCIP_Real lbglobal;
142  SCIP_Real ubglobal;
143  SCIP_VAR* var;
144 
145  var = vars[i];
146 
147  /* skip non-column variables */
149  continue;
150 
151  solval = SCIPgetSolVal(scip, NULL, var);
152  col = SCIPvarGetCol(vars[i]);
153  assert(col != NULL);
154  redcost = SCIPgetColRedcost(scip, col);
155  lbglobal = SCIPvarGetLbGlobal(var);
156  ubglobal = SCIPvarGetUbGlobal(var);
157 
158  /* fix the variable to its solution value if variable is nonbasic (i.e., at one of its bounds)
159  * with nonzero reduced costs
160  */
161  if( ! SCIPisDualfeasZero(scip, redcost) )
162  {
163  /* fix variable based on reduced cost information, respecting global bounds */
164  if( (redcost > 0 && SCIPisFeasEQ(scip, solval, lbglobal)) ||
165  (redcost < 0 && SCIPisFeasEQ(scip, solval, ubglobal)) )
166  {
167  SCIPdebugMsg(scip, "Fixing variable <%s> (obj: %g), local bounds [%.1g, %.1g], redcost %9.5g, LP sol val %9.5g\n",
168  SCIPvarGetName(var), SCIPvarGetObj(var), SCIPvarGetLbLocal(var), SCIPvarGetUbLocal(var), redcost, solval);
169  assert(! SCIPisInfinity(scip, solval));
170  assert(! SCIPisInfinity(scip, -solval));
171  SCIP_CALL( SCIPchgVarLbGlobal(subscip, subvars[i], solval) );
172  SCIP_CALL( SCIPchgVarUbGlobal(subscip, subvars[i], solval) );
173  if( SCIPvarIsIntegral(var) )
174  ++fixingcounter;
175  }
176 
177  }
178  }
179 
180  fixingrate = (SCIP_Real)fixingcounter / (SCIP_Real)(MAX(nbinvars + nintvars, 1));
181  heurdata->nvarsfixed = fixingcounter;
182 
183  /* if all variables were fixed or amount of fixed variables is insufficient, skip residual part of
184  * subproblem creation and abort immediately
185  */
186  *success = (fixingcounter < nvars && fixingrate >= heurdata->minfixingrate);
187 
188  SCIPdebugMsg(scip, " LP face heuristic fixed %senough variables (%d out of %d)\n",
189  *success ? "": "not ", fixingcounter, nvars);
190 
191  return SCIP_OKAY;
192 }
193 
194 /** creates the rows of the subproblem */
195 static
197  SCIP* scip, /**< original SCIP data structure */
198  SCIP* subscip, /**< SCIP data structure for the subproblem */
199  SCIP_VAR** subvars, /**< the variables of the subproblem */
200  SCIP_Bool dualbasisequations /**< should the dually nonbasic rows be turned into equations? */
201  )
202 {
203  SCIP_ROW** rows; /* original scip rows */
204 
205  int nrows;
206  int i;
207 
208  /* get the rows and their number */
209  SCIP_CALL( SCIPgetLPRowsData(scip, &rows, &nrows) );
210 
211  /* copy all rows to linear constraints */
212  for( i = 0; i < nrows; i++ )
213  {
214  SCIP_VAR** consvars; /* new constraint's variables */
215  SCIP_COL** cols; /* original row's columns */
216  SCIP_CONS* cons; /* new constraint */
217 
218  SCIP_Real* vals; /* variables' coefficient values of the row */
219  SCIP_Real constant; /* constant added to the row */
220  SCIP_Real lhs; /* left hand side of the row */
221  SCIP_Real rhs; /* left right side of the row */
222  SCIP_Real dualsol;
223  SCIP_Real rowsolactivity;
224  int j;
225  int nnonz;
226 
227  /* ignore rows that are only locally valid */
228  if( SCIProwIsLocal(rows[i]) )
229  continue;
230 
231  /* get the row's data */
232  constant = SCIProwGetConstant(rows[i]);
233  vals = SCIProwGetVals(rows[i]);
234  nnonz = SCIProwGetNNonz(rows[i]);
235  cols = SCIProwGetCols(rows[i]);
236 
237  /* only subtract constant if left hand side is not infinite */
238  lhs = SCIProwGetLhs(rows[i]);
239  if( ! SCIPisInfinity(scip, -lhs) )
240  lhs -= constant;
241 
242  /* only subtract constant if right hand side is not infinite */
243  rhs = SCIProwGetRhs(rows[i]);
244  if( ! SCIPisInfinity(scip, rhs) )
245  rhs -= constant;
246 
247  assert(lhs <= rhs);
248 
249  /* allocate memory array to be filled with the corresponding subproblem variables */
250  SCIP_CALL( SCIPallocBufferArray(scip, &consvars, nnonz) );
251  for( j = 0; j < nnonz; j++ )
252  consvars[j] = subvars[SCIPvarGetProbindex(SCIPcolGetVar(cols[j]))];
253 
254  dualsol = SCIProwGetDualsol(rows[i]);
255  rowsolactivity = SCIPgetRowActivity(scip, rows[i]);
256 
257  /* transform into equation if the row is sharp and has a nonzero dual solution */
258  if( dualbasisequations && ! SCIPisDualfeasZero(scip, dualsol) )
259  {
260  if( dualsol > 0.0 && SCIPisFeasEQ(scip, rowsolactivity, lhs) )
261  rhs = lhs;
262  else if( dualsol < 0.0 && SCIPisFeasEQ(scip, rowsolactivity, rhs) )
263  lhs = rhs;
264  }
265 
266  /* create a new linear constraint and add it to the subproblem */
267  SCIP_CALL( SCIPcreateConsLinear(subscip, &cons, SCIProwGetName(rows[i]), nnonz, consvars, vals, lhs, rhs,
268  TRUE, TRUE, TRUE, TRUE, TRUE, FALSE, FALSE, TRUE, TRUE, FALSE) );
269  SCIP_CALL( SCIPaddCons(subscip, cons) );
270  SCIP_CALL( SCIPreleaseCons(subscip, &cons) );
271 
272  /* free temporary memory */
273  SCIPfreeBufferArray(scip, &consvars);
274  }
275 
276  return SCIP_OKAY;
277 }
278 
279 /** creates the LP face subproblem by fixing nonbasic variables with nonzero reduced costs */
280 static
282  SCIP* scip, /**< original SCIP data structure */
283  SCIP* subscip, /**< SCIP data structure for the subproblem */
284  SCIP_VAR** subvars, /**< the variables of the subproblem */
285  SCIP_HEURDATA* heurdata, /**< primal heuristic data */
286  SCIP_Bool* success /**< pointer to store whether the problem was created successfully */
287  )
288 {
289  SCIP_VAR** vars = SCIPgetVars(scip);
290  int nvars = SCIPgetNVars(scip);
291  SCIP_Real lowerbound;
292  SCIP_CONS* origobjcons;
293  int i;
294 #ifndef NDEBUG
295  int nobjvars = 0;
296 #endif
297 
298  /* fix variables in subproblem with nonzero reduced costs */
299  SCIP_CALL( fixVariables(scip, subscip, subvars, heurdata, success) );
300 
301  if( ! (*success) )
302  return SCIP_OKAY;
303 
304  /* we copy the rows of the LP, if enough variables could be fixed and we work on the MIP relaxation of the problem */
305  if( *success && heurdata->uselprows )
306  {
307  SCIP_CALL( createRows(scip, subscip, subvars, heurdata->dualbasisequations) );
308  }
309 
310  /* add an equation that the objective function must be equal to the lower bound */
311  lowerbound = SCIPgetLowerbound(scip);
312 
313  SCIP_CALL( SCIPcreateConsLinear(subscip, &origobjcons, "objbound_of_origscip", 0, NULL, NULL, lowerbound, lowerbound,
315 
316  for( i = 0; i < nvars; ++i)
317  {
318  if( ! SCIPisZero(subscip, SCIPvarGetObj(vars[i])) )
319  {
320  SCIP_CALL( SCIPaddCoefLinear(subscip, origobjcons, subvars[i], SCIPvarGetObj(vars[i])) );
321 #ifndef NDEBUG
322  nobjvars++;
323 #endif
324  }
325  }
326  assert(nobjvars == SCIPgetNObjVars(scip));
327 
328  SCIP_CALL( SCIPaddCons(subscip, origobjcons) );
329  SCIP_CALL( SCIPreleaseCons(subscip, &origobjcons) );
330 
331  return SCIP_OKAY;
332 }
333 
334 /** creates a new solution for the original problem by copying the solution of the subproblem */
335 static
337  SCIP* scip, /**< original SCIP data structure */
338  SCIP* subscip, /**< SCIP structure of the subproblem */
339  SCIP_VAR** subvars, /**< the variables of the subproblem */
340  SCIP_HEUR* heur, /**< lpface heuristic structure */
341  SCIP_SOL* subsol, /**< solution of the subproblem */
342  int* solindex, /**< pointer to store index of the solution */
343  SCIP_Bool* success /**< pointer to store whether new solution was found or not */
344  )
345 {
346  SCIP_VAR** vars; /* the original problem's variables */
347  int nvars;
348  SCIP_SOL* newsol; /* solution to be created for the original problem */
349  SCIP_Real* subsolvals; /* solution values of the subproblem */
350  SCIP_Bool printreason;
351  SCIP_Bool completely;
352 
353  assert(scip != NULL);
354  assert(subscip != NULL);
355  assert(subvars != NULL);
356  assert(subsol != NULL);
357 
358  /* get variables' data */
359  SCIP_CALL( SCIPgetVarsData(scip, &vars, &nvars, NULL, NULL, NULL, NULL) );
360 
361  /* sub-SCIP may have more variables than the number of active (transformed) variables in the main SCIP
362  * since constraint copying may have required the copy of variables that are fixed in the main SCIP
363  */
364  assert(nvars <= SCIPgetNOrigVars(subscip));
365 
366  SCIP_CALL( SCIPallocBufferArray(scip, &subsolvals, nvars) );
367 
368  /* copy the solution */
369  SCIP_CALL( SCIPgetSolVals(subscip, subsol, nvars, subvars, subsolvals) );
370 
371  /* create new solution for the original problem */
372  SCIP_CALL( SCIPcreateSol(scip, &newsol, heur) );
373  SCIP_CALL( SCIPsetSolVals(scip, newsol, nvars, vars, subsolvals) );
374  *solindex = SCIPsolGetIndex(newsol);
375 
376 #ifdef SCIP_DEBUG
377  printreason = TRUE;
378  completely = TRUE;
379  SCIPdebugMsg(scip, "trying to transfer LP face solution with solution value %16.9g to main problem\n",
380  SCIPretransformObj(scip, SCIPgetSolTransObj(scip, newsol)));
381 #else
382  printreason = FALSE;
383  completely = FALSE;
384 #endif
385 
386  /* try to add new solution to scip and free it immediately */
387  *success = FALSE;
388  SCIP_CALL( SCIPtrySolFree(scip, &newsol, printreason, completely, TRUE, TRUE, TRUE, success) );
389 
390  SCIPdebugMsg(scip, "Transfer was %s successful\n", *success ? "" : "not");
391 
392  SCIPfreeBufferArray(scip, &subsolvals);
393 
394  return SCIP_OKAY;
395 }
396 
397 /** updates heurdata after an unsuccessful run of lpface */
398 static
400  SCIP* scip, /**< original SCIP data structure */
401  SCIP_HEURDATA* heurdata /**< primal heuristic data */
402  )
403 {
404  /* increase number of failures, calculate next node at which lpface should be called and update actual solutions */
405  heurdata->nfailures++;
406  heurdata->nextnodenumber = (heurdata->nfailures <= 25
407  ? SCIPgetNNodes(scip) + 100*(2LL << heurdata->nfailures) /*lint !e703*/
408  : SCIP_LONGINT_MAX);
409 }
410 
411 /** calculate a node limit based on node limiting parameters of the heuristic */
412 static
414  SCIP* scip, /**< (original) SCIP data structure */
415  SCIP_HEUR* heur, /**< LP face heuristic */
416  SCIP_HEURDATA* heurdata /**< primal heuristic data */
417  )
418 {
419  SCIP_Longint nodelimit;
420 
421  /* calculate the maximal number of branching nodes until heuristic is aborted */
422  nodelimit = (SCIP_Longint)(heurdata->nodesquot * SCIPgetNNodes(scip));
423 
424  /* count the setup costs for the sub-MIP as 100 nodes */
425  nodelimit -= 100 * SCIPheurGetNCalls(heur);
426 
427  /* add the offset */
428  nodelimit += heurdata->nodesofs;
429 
430  /* subtract previously used nodes */
431  nodelimit -= heurdata->usednodes;
432 
433  /* do not use more than the maximum number of allowed nodes in one run */
434  nodelimit = MIN(nodelimit, heurdata->maxnodes);
435 
436  /* if the subscip has been kept from a previous run, add the number of already processed nodes */
437  if( heurdata->subscipdata->subscip != NULL )
438  nodelimit += SCIPgetNNodes(heurdata->subscipdata->subscip);
439 
440  return nodelimit;
441 }
442 
443 /** sets node, time, and memory limit according to the parameter settings of the heuristic */
444 static
446  SCIP* scip, /**< original SCIP data structure */
447  SCIP* subscip, /**< data structure of the sub-problem */
448  SCIP_HEUR* heur, /**< LP face heuristic */
449  SCIP_HEURDATA* heurdata, /**< heuristic data structure */
450  SCIP_Bool* success /**< did we successfully set all parameters up? */
451  )
452 {
453  SCIP_Real timelimit;
454  SCIP_Real memorylimit;
455  SCIP_Longint nodelimit;
456 
457  *success = TRUE;
458 
459  /* check whether there is enough time and memory left */
460  SCIP_CALL( SCIPgetRealParam(scip, "limits/time", &timelimit) );
461  SCIP_CALL( SCIPgetRealParam(scip, "limits/memory", &memorylimit) );
462 
463  if( ! SCIPisInfinity(scip, timelimit) )
464  timelimit -= SCIPgetSolvingTime(scip);
465 
466  /* substract the memory already used by the main SCIP and the estimated memory usage of external software */
467  if( ! SCIPisInfinity(scip, memorylimit) )
468  {
469  memorylimit -= SCIPgetMemUsed(scip)/1048576.0;
470  memorylimit -= SCIPgetMemExternEstim(scip)/1048576.0;
471  }
472 
473  /* abort if no time is left or not enough memory to create a copy of SCIP, including external memory usage */
474  if( timelimit <= 0.0 || memorylimit <= 2.0 * SCIPgetMemExternEstim(scip) / 1048576.0 )
475  {
476  *success = FALSE;
477  return SCIP_OKAY;
478  }
479 
480  /* calculate node limit for the subproblem */
481  nodelimit = calcNodeLimit(scip, heur, heurdata);
482 
483  /* we should have aborted the sub-SCIP procedure earlier if no additional nodes are allowed
484  * with the current parameter settings
485  */
486  assert(nodelimit > SCIPgetNNodes(subscip));
487 
488  SCIP_CALL( SCIPsetLongintParam(subscip, "limits/nodes", nodelimit) );
489  heurdata->nodelimit = nodelimit;
490 
491  /* set also the other two limits */
492  SCIP_CALL( SCIPsetRealParam(subscip, "limits/time", timelimit) );
493  SCIP_CALL( SCIPsetRealParam(subscip, "limits/memory", memorylimit) );
494 
495  return SCIP_OKAY;
496 }
497 
498 /** sets all one-time parameter settings like search strategy, but no limits */
499 static
501  SCIP* scip, /**< original SCIP data structure */
502  SCIP* subscip /**< data structure of the sub-problem */
503  )
504 {
505 
506  /* do not abort subproblem on CTRL-C */
507  SCIP_CALL( SCIPsetBoolParam(subscip, "misc/catchctrlc", FALSE) );
508 
509  /* for debugging lpface, enable MIP output */
510 #ifdef SCIP_DEBUG
511  SCIP_CALL( SCIPsetIntParam(subscip, "display/verblevel", 5) );
512  SCIP_CALL( SCIPsetIntParam(subscip, "display/freq", 1) );
513 #endif
514 
515  /* disable statistic timing inside sub SCIP */
516  SCIP_CALL( SCIPsetBoolParam(subscip, "timing/statistictiming", FALSE) );
517 
518  /* forbid recursive call of heuristics and separators solving subMIPs */
519  SCIP_CALL( SCIPsetSubscipsOff(subscip, TRUE) );
520 
521  /* disable expensive cutting plane separation */
523 
524  /* disable expensive presolving */
526 
527  /* use restart depth first node selection */
528  if( SCIPfindNodesel(subscip, "restartdfs") != NULL && ! SCIPisParamFixed(subscip, "nodeselection/restartdfs/stdpriority") )
529  {
530  SCIP_CALL( SCIPsetIntParam(subscip, "nodeselection/restartdfs/stdpriority", INT_MAX/4) );
531  }
532 
533  /* use inference branching */
534  if( SCIPfindBranchrule(subscip, "inference") != NULL && ! SCIPisParamFixed(subscip, "branching/inference/priority") )
535  {
536  SCIP_CALL( SCIPsetIntParam(subscip, "branching/inference/priority", INT_MAX/4) );
537  }
538 
539  /* employ a limit on the number of enforcement rounds in the quadratic constraint handler; this fixes the issue that
540  * sometimes the quadratic constraint handler needs hundreds or thousands of enforcement rounds to determine the
541  * feasibility status of a single node without fractional branching candidates by separation (namely for uflquad
542  * instances); however, the solution status of the sub-SCIP might get corrupted by this; hence no deductions shall be
543  * made for the original SCIP
544  */
545  if( SCIPfindConshdlr(subscip, "quadratic") != NULL && ! SCIPisParamFixed(subscip, "constraints/quadratic/enfolplimit") )
546  {
547  SCIP_CALL( SCIPsetIntParam(subscip, "constraints/quadratic/enfolplimit", 500) );
548  }
549 
550  /* enable conflict analysis, disable analysis of boundexceeding LPs, and restrict conflict pool */
551  if( !SCIPisParamFixed(subscip, "conflict/enable") )
552  {
553  SCIP_CALL( SCIPsetBoolParam(subscip, "conflict/enable", TRUE) );
554  }
555  if( !SCIPisParamFixed(subscip, "conflict/useboundlp") )
556  {
557  SCIP_CALL( SCIPsetCharParam(subscip, "conflict/useboundlp", 'o') );
558  }
559  if( !SCIPisParamFixed(subscip, "conflict/maxstoresize") )
560  {
561  SCIP_CALL( SCIPsetIntParam(subscip, "conflict/maxstoresize", 100) );
562  }
563 
564  return SCIP_OKAY;
565 }
566 
567 /** reset the sub-SCIP data to its default values */
568 static
569 void subscipdataReset(
570  SUBSCIPDATA* subscipdata /**< data structure of the sub-problem */
571  )
572 {
573  subscipdata->subscip = NULL;
574  subscipdata->subvars = NULL;
575  subscipdata->nsubvars = 0;
576  subscipdata->objbound = SCIP_INVALID;
577 }
578 
579 /** free the stored sub-SCIP information */
580 static
582  SCIP* scip, /**< original SCIP data structure */
583  SUBSCIPDATA* subscipdata /**< data structure of the sub-problem */
584  )
585 {
586  assert(subscipdata != NULL);
587 
588  /* free the subscipdata's scip */
589  if( subscipdata->subscip != NULL )
590  {
591  SCIP_CALL( SCIPfree(&subscipdata->subscip) );
592  }
593 
594  subscipdata->subscip = NULL;
595 
596  /* free the subscip variables */
597  if( subscipdata->subvars != NULL )
598  {
599  assert(subscipdata->nsubvars > 0);
600  SCIPfreeBlockMemoryArray(scip, &subscipdata->subvars, subscipdata->nsubvars);
601  }
602 
603  subscipdataReset(subscipdata);
604 
605  return SCIP_OKAY;
606 }
607 
608 /** store the sub-SCIP to the data structure */
609 static
611  SCIP* scip, /**< original SCIP data structure */
612  SUBSCIPDATA* subscipdata, /**< data structure of the sub-problem */
613  SCIP* subscip, /**< sub scip data structure to keep */
614  SCIP_VAR** subvars, /**< sub scip variable array in the order of the main SCIP variables */
615  int nvars /**< number of sub SCIP variables */
616  )
617 {
618  assert(scip != NULL);
619  assert(subscipdata != NULL);
620  assert(subscip != NULL);
621  assert(subvars != NULL);
622  assert(nvars == SCIPgetNVars(scip));
623 
624  assert(subscipdata->subscip == NULL);
625  assert(subscipdata->subvars == NULL);
626 
627  subscipdata->subscip = subscip;
628  SCIP_CALL( SCIPduplicateBlockMemoryArray(scip, &subscipdata->subvars, subvars, nvars) );
629  subscipdata->nsubvars = nvars;
630 
631  subscipdata->objbound = SCIPgetNodeLowerbound(scip, SCIPgetCurrentNode(scip));
632 
633  return SCIP_OKAY;
634 }
635 
636 #ifdef SCIP_DEBUG
637 /** print debug message listing solving time, nodes, and status of sub-SCIP */
638 static
639 SCIP_RETCODE subscipGetInfo(
640  SCIP* scip, /**< SCIP data structure */
641  SCIP* subscip /**< sub SCIP data */
642  )
643 {
644  SCIP_Real timelimit;
645  SCIP_Real memorylimit;
646  SCIP_Longint nodelimit;
647  SCIP_Real time;
648  SCIP_Longint nodes;
649  SCIP_STATUS status;
650 
651  SCIP_CALL( SCIPgetRealParam(subscip, "limits/time", &timelimit) );
652  SCIP_CALL( SCIPgetRealParam(subscip, "limits/memory", &memorylimit) );
653  SCIP_CALL( SCIPgetLongintParam(subscip, "limits/nodes", &nodelimit) );
654 
655  time = SCIPgetSolvingTime(subscip);
656  nodes = SCIPgetNNodes(subscip);
657  status = SCIPgetStatus(subscip);
658 
659  SCIPdebugMsg(scip, "SCIP info: Time: %.1f (Limit: %.1f) Nodes: %"SCIP_LONGINT_FORMAT" (Limit: %"SCIP_LONGINT_FORMAT") Status: %d\n",
660  time, timelimit, nodes, nodelimit, status);
661 
662  return SCIP_OKAY;
663 }
664 #endif
665 
666 /** create the objective function based on the user selection */
667 static
669  SCIP* scip, /**< SCIP data structure */
670  SCIP* subscip, /**< sub-SCIP data structure */
671  SCIP_VAR* var, /**< SCIP variable */
672  SCIP_VAR* subvar, /**< sub-SCIP variable whose objective coefficient is changed */
673  SCIP_HEURDATA* heurdata /**< heuristic data structure to control how the objective is changed */
674  )
675 {
676  SCIP_Real objcoeff;
677  SCIP_Real upfrac;
678  SCIP_Real downfrac;
679  SCIP_Real lpsolval;
680  SCIP_Real rootlpsolval;
681 
682  /* create the objective value based on the choice of the sub-SCIP objective */
683  switch( heurdata->subscipobjective )
684  {
685  /* use zero as objective function */
686  case 'z':
687  objcoeff = 0.0;
688  break;
689 
690  /* use current LP fractionality as objective */
691  case 'f':
692  lpsolval = SCIPvarGetLPSol(var);
693  downfrac = SCIPfrac(scip, lpsolval);
694  upfrac = 1.0 - downfrac;
695 
696  objcoeff = downfrac - upfrac;
697  break;
698 
699  /* use root LP solution difference */
700  case 'r':
701  lpsolval = SCIPvarGetLPSol(var);
702  rootlpsolval = SCIPvarGetRootSol(var);
703  objcoeff = rootlpsolval - lpsolval;
704  break;
705 
706  /* use average inferences */
707  case 'i':
710  break;
711 
712  /* use original objective function */
713  case 'o':
714  objcoeff = SCIPvarGetObj(var);
715  break;
716  default:
717  objcoeff = 0.0;
718  break;
719  }
720 
721  SCIP_CALL( SCIPchgVarObj(subscip, subvar, objcoeff) );
722 
723  return SCIP_OKAY;
724 }
725 
726 /* ---------------- Callback methods of event handler ---------------- */
727 
728 /** execution callback of the event handler for Lpface sub-SCIP
729  *
730  * we interrupt the solution process if we hit the LP iteration limit per node
731  */
732 static
733 SCIP_DECL_EVENTEXEC(eventExecLpface)
734 {
735  SCIP_HEURDATA* heurdata;
737  assert(eventhdlr != NULL);
738  assert(eventdata != NULL);
739  assert(strcmp(SCIPeventhdlrGetName(eventhdlr), EVENTHDLR_NAME) == 0);
740  assert(event != NULL);
741  assert(SCIPeventGetType(event) & SCIP_EVENTTYPE_LPSOLVED);
742 
743  heurdata = (SCIP_HEURDATA*)eventdata;
744  assert(heurdata != NULL);
745 
746  /* interrupt solution process of sub-SCIP */
747  if( SCIPgetNLPs(scip) > heurdata->lplimfac * heurdata->nodelimit )
748  {
749  SCIPdebugMsg(scip, "interrupt after %" SCIP_LONGINT_FORMAT " LPs\n",SCIPgetNLPs(scip));
750  SCIP_CALL( SCIPinterruptSolve(scip) );
751  }
752 
753  return SCIP_OKAY;
754 }
755 
756 /** setup and solve the subproblem and catch the return code */
757 static
759  SCIP* scip, /**< SCIP data structure */
760  SCIP* subscip, /**< sub-SCIP data structure */
761  SCIP_HEURDATA* heurdata, /**< heuristics data */
762  SCIP_VAR** subvars, /**< subproblem's variables */
763  SCIP_VAR** vars, /**< original problem's variables */
764  SCIP_RESULT* result, /**< pointer to store the result */
765  SCIP_Bool* keepthisscip, /**< should the subscip be kept or deleted? */
766  int nvars /**< number of original problem's variables */
767  )
768 {
769  SCIP_HASHMAP* varmapfw = NULL; /* mapping of SCIP variables to sub-SCIP variables */
770  SCIP_Bool success;
771  int i;
772 
773  assert( subscip != NULL );
774  assert( heurdata!= NULL );
775  assert( vars != NULL );
776 
777  /* create the variable hash map */
778  SCIP_CALL( SCIPhashmapCreate(&varmapfw, SCIPblkmem(subscip), nvars) );
779  success = FALSE;
780 
781  if( heurdata->uselprows )
782  {
783  char probname[SCIP_MAXSTRLEN];
784 
785  /* copy all plugins */
787 
788  /* get name of the original problem and add the string "_lpfacesub" */
789  (void) SCIPsnprintf(probname, SCIP_MAXSTRLEN, "%s_lpfacesub", SCIPgetProbName(scip));
790 
791  /* create the subproblem */
792  SCIP_CALL( SCIPcreateProbBasic(subscip, probname) );
793 
794  /* copy all variables */
795  SCIP_CALL( SCIPcopyVars(scip, subscip, varmapfw, NULL, NULL, NULL, 0, TRUE) );
796 
797  SCIP_CALL( SCIPcopyParamSettings(scip, subscip) );
798  }
799  else
800  {
801  SCIP_CALL( SCIPcopy(scip, subscip, varmapfw, NULL, "lpface", TRUE, FALSE, TRUE, &success) );
802 
803  if( heurdata->copycuts )
804  {
805  /* copies all active cuts from cutpool of sourcescip to linear constraints in targetscip */
806  SCIP_CALL( SCIPcopyCuts(scip, subscip, varmapfw, NULL, TRUE, NULL) );
807  }
808  }
809 
810  /* fill subvars array with mapping from original variables and set the objective coefficient to the desired value */
811  for( i = 0; i < nvars; i++ )
812  {
813  subvars[i] = (SCIP_VAR*) SCIPhashmapGetImage(varmapfw, vars[i]);
814 
815  SCIP_CALL( changeSubvariableObjective(scip, subscip, vars[i], subvars[i], heurdata) );
816 
817  }
818  /* free hash map */
819  SCIPhashmapFree(&varmapfw);
820 
821  success = FALSE;
822 
823  /* disable output to console */
824  SCIP_CALL( SCIPsetIntParam(subscip, "display/verblevel", 0) );
825 
826  /* fix variables that are at their bounds and have nonzero reduced costs */
827  SCIP_CALL( setupSubproblem(scip, subscip, subvars, heurdata, &success) );
828 
829  /* if creation of sub-SCIP was aborted (e.g. due to number of fixings), free sub-SCIP and abort */
830  if( ! success )
831  {
832  *result = SCIP_DIDNOTRUN;
833 
834  /* this run will be counted as a failure since no new solution tuple could be generated or the neighborhood of the
835  * solution was not fruitful in the sense that it was too big
836  */
837  updateFailureStatistic(scip, heurdata);
838 
839  /* we do not want to keep this SCIP */
840  *keepthisscip = FALSE;
841 
842  return SCIP_OKAY;
843  }
844  /* set up sub-SCIP parameters */
845  SCIP_CALL( setSubscipParameters(scip, subscip) );
846 
847  return SCIP_OKAY;
848 }
849 
850 /** setup and solve the subproblem and catch the return code */
851 static
853  SCIP* scip, /**< SCIP data structure */
854  SCIP* subscip, /**< sub-SCIP data structure */
855  SCIP_HEUR* heur, /**< mutation heuristic */
856  SCIP_HEURDATA* heurdata, /**< heuristics data */
857  SCIP_VAR** subvars, /**< subproblem's variables */
858  SCIP_RESULT* result, /**< pointer to store the result */
859  SCIP_Real focusnodelb, /**< lower bound of the focus node */
860  SCIP_Bool* keepthisscip /**< should the subscip be kept or deleted? */
861  )
862 {
863  SCIP_EVENTHDLR* eventhdlr;
864  SCIP_Bool success;
865  int i;
866 
867  assert( scip != NULL );
868  assert( subscip != NULL );
869  assert( heur != NULL );
870  assert( heurdata != NULL );
871  assert( subvars != NULL );
872 
873  /* create event handler for LP events */
874  SCIP_CALL( SCIPincludeEventhdlrBasic(subscip, &eventhdlr, EVENTHDLR_NAME, EVENTHDLR_DESC, eventExecLpface, NULL) );
875  if( eventhdlr == NULL )
876  {
877  SCIPerrorMessage("event handler for " HEUR_NAME " heuristic not found.\n");
878  return SCIP_PLUGINNOTFOUND;
879  }
880 
881  /* determine node, memory, and time limits for the sub-SCIP. Both node and time limit change with every call to
882  * the heuristic
883  */
884  SCIP_CALL( setSubscipLimits(scip, subscip, heur, heurdata, &success) );
885 
886  /* if we did not succeed to set the limits of the subscip to let it run, we won't keep it any longer */
887  if( !success )
888  {
889  *keepthisscip = FALSE;
890 
891  return SCIP_OKAY;
892  }
893 
894  /* catch LP events of sub-SCIP */
895  SCIP_CALL( SCIPtransformProb(subscip) );
896  SCIP_CALL( SCIPcatchEvent(subscip, SCIP_EVENTTYPE_LPSOLVED, eventhdlr, (SCIP_EVENTDATA*) heurdata, NULL) );
897 
898 #ifdef WRITELPFACEPROB
899  {
900  char probfilename[] = "./lpface_prob.mps";
901  char paramfilename[] = "./lpface_prob.set";
902  SCIPinfoMessage(scip, NULL, "Writing problem and parameters to file: <%s> <%s>\n", probfilename, paramfilename);
903  SCIP_CALL( SCIPwriteOrigProblem(subscip, probfilename, NULL, FALSE) );
904  SCIP_CALL( SCIPwriteParams(subscip, paramfilename, TRUE, TRUE) );
905  }
906 #endif
907 
908  /* we must not be infeasible at this stage */
909  assert(SCIPgetStatus(subscip) != SCIP_STATUS_INFEASIBLE);
910 
911  /* solve the subproblem */
912  SCIPdebugMsg(scip, "Solve Lpface subMIP\n");
913  SCIPdebug(
914  SCIP_CALL( subscipGetInfo(scip, subscip) );
915  )
916 
917  /* Errors in solving the subproblem should not kill the overall solving process.
918  * Hence, the return code is caught and a warning is printed, only in debug mode, SCIP will stop.
919  */
920  SCIP_CALL_ABORT( SCIPsolve(subscip) );
921 
922  /* print solving statistics of subproblem if we are in SCIP's debug mode */
923  SCIPdebug( SCIP_CALL( SCIPprintStatistics(subscip, NULL) ) );
924 
925  /* save useful information regarding the subscip runs */
926  heurdata->usednodes += SCIPgetNNodes(subscip);
927  heurdata->submipnlpiters += SCIPgetNLPIterations(subscip);
928  heurdata->submippresoltime += SCIPgetPresolvingTime(subscip);
929  heurdata->submipstatus = SCIPgetStatus(subscip);
930 
931  /* store the focus node lower bound as infeasible to avoid running on this face again */
932  if( heurdata->submipstatus == SCIP_STATUS_INFEASIBLE )
933  {
934  heurdata->lastlpobjinfeas = focusnodelb;
935  *keepthisscip = FALSE;
936  }
937  else if( SCIPgetNSols(subscip) > 0 )
938  {
939  SCIP_SOL** subsols;
940  int nsubsols;
941  int solindex;
942 
943  /* check, whether a solution was found;
944  * due to numerics, it might happen that not all solutions are feasible -> try all solutions until one is accepted
945  */
946  nsubsols = SCIPgetNSols(subscip);
947  subsols = SCIPgetSols(subscip);
948  success = FALSE;
949  solindex = -1;
950  for( i = 0; i < nsubsols && !success; ++i )
951  {
952  SCIP_CALL( createNewSol(scip, subscip, subvars, heur, subsols[i], &solindex, &success) );
953  }
954 
955  /* we found an optimal solution and are done. Thus, we free the subscip immediately */
956  if( success )
957  {
958  *keepthisscip = FALSE;
959  *result = SCIP_FOUNDSOL;
960  }
961 
962  /* if solution could not be added to problem => run is counted as a failure */
963  if( ! success || solindex != SCIPsolGetIndex(SCIPgetBestSol(scip)) )
964  updateFailureStatistic(scip, heurdata);
965  }
966  else
967  {
968  /* if no new solution was found, run was a failure */
969  updateFailureStatistic(scip, heurdata);
970  }
971 
972  return SCIP_OKAY;
973 }
974 
975 /*
976  * Callback methods of primal heuristic
977  */
978 
979 /** copy method for primal heuristic plugins (called when SCIP copies plugins) */
980 static
981 SCIP_DECL_HEURCOPY(heurCopyLpface)
982 { /*lint --e{715}*/
983  assert(scip != NULL);
984  assert(heur != NULL);
985  assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0);
986 
987  /* call inclusion method of primal heuristic */
989 
990  return SCIP_OKAY;
991 }
992 
993 /** destructor of primal heuristic to free user data (called when SCIP is exiting) */
994 static
995 SCIP_DECL_HEURFREE(heurFreeLpface)
996 { /*lint --e{715}*/
997  SCIP_HEURDATA* heurdata;
999  assert(heur != NULL);
1000  assert(scip != NULL);
1001 
1002  /* get heuristic data */
1003  heurdata = SCIPheurGetData(heur);
1004  assert(heurdata != NULL);
1005 
1006  /* free heuristic data */
1007  SCIPfreeBlockMemory(scip, &heurdata);
1008  SCIPheurSetData(heur, NULL);
1009 
1010  return SCIP_OKAY;
1011 }
1012 
1013 /** initialization method of primal heuristic (called after problem was transformed) */
1014 static
1015 SCIP_DECL_HEURINIT(heurInitLpface)
1016 { /*lint --e{715}*/
1017  SCIP_HEURDATA* heurdata;
1019  assert(heur != NULL);
1020  assert(scip != NULL);
1021 
1022  /* get heuristic's data */
1023  heurdata = SCIPheurGetData(heur);
1024  assert(heurdata != NULL);
1025 
1026  /* initialize data */
1027  heurdata->usednodes = 0;
1028  heurdata->nfailures = 0;
1029  heurdata->nextnodenumber = 0;
1030 
1031  heurdata->submipstatus = SCIP_STATUS_UNKNOWN;
1032  heurdata->submipnlpiters = -1;
1033  heurdata->submippresoltime = 0.0;
1034  heurdata->nvarsfixed = -1;
1035 
1036  return SCIP_OKAY;
1037 }
1038 
1039 /** solving process initialization method of primal heuristic (called when branch and bound process is about to begin) */
1040 static
1041 SCIP_DECL_HEURINITSOL(heurInitsolLpface)
1042 { /*lint --e{715}*/
1043  SCIP_HEURDATA* heurdata;
1045  assert(heur != NULL);
1046  assert(scip != NULL);
1047 
1048  /* get heuristic's data */
1049  heurdata = SCIPheurGetData(heur);
1050  assert(heurdata != NULL);
1051 
1052  /* reset the last infeasible objective because it lives in transformed space and must be invalidated at every restart */
1053  heurdata->lastlpobjinfeas = -SCIPinfinity(scip);
1054 
1055  assert(heurdata->subscipdata == NULL);
1056 
1057  /* variable order might have changed since the last run, reinitialize sub-SCIP data */
1058  SCIP_CALL( SCIPallocBlockMemory(scip, &heurdata->subscipdata) );
1059  subscipdataReset(heurdata->subscipdata);
1060 
1061  return SCIP_OKAY;
1062 }
1063 
1064 /** solving process deinitialization method of primal heuristic (called before branch and bound process is exiting) */
1065 static
1066 SCIP_DECL_HEUREXITSOL(heurExitsolLpface)
1067 { /*lint --e{715}*/
1068  SCIP_HEURDATA* heurdata;
1070  assert(heur != NULL);
1071  assert(scip != NULL);
1072 
1073  /* get heuristic's data */
1074  heurdata = SCIPheurGetData(heur);
1075  assert(heurdata != NULL);
1076 
1077  /* variable order might change after restart, free the heuristic subscipdata */
1078  assert(heurdata->keepsubscip || heurdata->subscipdata->subscip == NULL);
1079  if( heurdata->subscipdata->subscip != NULL )
1080  {
1081  /* free kept data structures first */
1082  SCIP_CALL( subscipdataFreeSubscip(scip, heurdata->subscipdata) );
1083 
1084  }
1085 
1086  /* free the sub-SCIP data structure */
1087  SCIPfreeBlockMemory(scip, &heurdata->subscipdata);
1088 
1089  return SCIP_OKAY;
1090 }
1091 
1092 #ifdef SCIP_STATISTIC
1093 /** deinitialization method of primal heuristic (called before transformed problem is freed) */
1094 static
1096 { /*lint --e{715}*/
1097  SCIP_HEURDATA* heurdata;
1098 
1099  assert(heur != NULL);
1100  assert(scip != NULL);
1101 
1102  /* get heuristic's data */
1103  heurdata = SCIPheurGetData(heur);
1104  assert(heurdata != NULL);
1105 
1107  "LP Face heuristic stats: Status: %d Nodes: %d LP iters: %d Fixed: %d Presolving time: %.2f\n",
1108  heurdata->submipstatus, heurdata->usednodes, heurdata->submipnlpiters, heurdata->nvarsfixed, heurdata->submippresoltime);
1109 
1110  return SCIP_OKAY;
1111 }
1112 #else
1113 #define heurExitLpface NULL
1114 #endif
1115 
1116 /** execution method of primal heuristic */
1117 static
1118 SCIP_DECL_HEUREXEC(heurExecLpface)
1119 { /*lint --e{715}*/
1120  SCIP* subscip; /* the subproblem created by lpface */
1121  SCIP_HEURDATA* heurdata; /* primal heuristic data */
1122  SCIP_VAR** vars; /* original problem's variables */
1123  SCIP_VAR** subvars; /* subproblem's variables */
1124  SCIP_RETCODE retcode;
1125  SCIP_Bool keepthisscip;
1126  SCIP_Real focusnodelb;
1127  SCIP_Real rootlb;
1128  SCIP_Longint nodelimit; /* node limit for the subproblem */
1129  int nvars; /* number of original problem's variables */
1130  int nbinvars;
1131  int nintvars;
1132 
1133  assert(heur != NULL);
1134  assert(scip != NULL);
1135  assert(result != NULL);
1136 
1137  /* get heuristic's data */
1138  heurdata = SCIPheurGetData(heur);
1139  assert(heurdata != NULL);
1140 
1141  *result = SCIP_DELAYED;
1142 
1143  /* we skip infeasible nodes */
1144  if( nodeinfeasible )
1145  return SCIP_OKAY;
1146 
1147  /* the node number to run the heuristic again was not yet reached */
1148  if( SCIPgetNNodes(scip) < heurdata->nextnodenumber )
1149  return SCIP_OKAY;
1150 
1151  /* do not run heuristic on nodes that were not solved to optimality */
1153  return SCIP_OKAY;
1154 
1155  /* LP face requires that the LP defines a valid lower bound for the current node */
1156  if( ! SCIPisLPRelax(scip) || ! SCIPallColsInLP(scip) )
1157  return SCIP_OKAY;
1158 
1159  assert(SCIPgetCurrentNode(scip) != NULL);
1160  focusnodelb = SCIPgetNodeLowerbound(scip, SCIPgetCurrentNode(scip));
1161 
1162  /* from the checked conditions, the LP objective should be a valid lower bound for the current node */
1163  assert(SCIPisGE(scip, focusnodelb, SCIPgetLPObjval(scip)));
1164 
1165  /* do not run if the current focus node already has a lower bound higher than the LP value at the node,
1166  * for example, due to strong branching
1167  */
1168  if( SCIPisGT(scip, focusnodelb, SCIPgetLPObjval(scip)) )
1169  return SCIP_OKAY;
1170 
1171  /* delay heuristic if the active search tree path is not deep enough */
1172  if( SCIPgetDepth(scip) < heurdata->minpathlen - 1 )
1173  return SCIP_OKAY;
1174 
1175  /* only run at lower bound defining nodes */
1176  if( SCIPisGT(scip, focusnodelb, SCIPgetLowerbound(scip)) )
1177  return SCIP_OKAY;
1178 
1179  /* only run if lower bound has increased since last LP objective where the sub-MIP was solved to infeasibility */
1180  if( SCIPisEQ(scip, heurdata->lastlpobjinfeas, focusnodelb) )
1181  return SCIP_OKAY;
1182 
1183  /* make the reasoning stronger if the objective value must be integral */
1184  if( SCIPisObjIntegral(scip)
1185  && (! SCIPisIntegral(scip, focusnodelb) || SCIPisLT(scip, focusnodelb, heurdata->lastlpobjinfeas + 1.0)) )
1186  return SCIP_OKAY;
1187 
1188  rootlb = SCIPgetLowerboundRoot(scip);
1189  assert(SCIPisLE(scip, rootlb, focusnodelb));
1190 
1191  /* if the lower bound hasn't changed since the root node, we want to run anyway, otherwise we base our decision on the
1192  * total path length of the active search tree along which the lower bound did not change anymore.
1193  */
1194  if( SCIPisLT(scip, rootlb, focusnodelb) )
1195  {
1196  SCIP_NODE* parent;
1197  int nonimprovingpathlen = 0; /* the length of the current path (in edges) along which the lower bound stayed the same */
1198 
1199  parent = SCIPnodeGetParent(SCIPgetCurrentNode(scip));
1200 
1201  /* count the path length along which the dual bound has not changed */
1202  while( SCIPisEQ(scip, SCIPnodeGetLowerbound(parent), focusnodelb) && nonimprovingpathlen < heurdata->minpathlen )
1203  {
1204  ++nonimprovingpathlen;
1205 
1206  /* we cannot hit the root node because the root lower bound is strictly smaller */
1207  assert(SCIPnodeGetParent(parent) != NULL);
1208  parent = SCIPnodeGetParent(parent);
1209  }
1210 
1211  /* we return if the nonimproving path is too short measured by the heuristic frequency */
1212  if( nonimprovingpathlen < heurdata->minpathlen )
1213  {
1214  /* we do not delay the heuristic if the path has length zero, otherwise it may be called at children so that
1215  * the path length is sufficient
1216  */
1217  if( nonimprovingpathlen == 0 )
1218  *result = SCIP_DIDNOTRUN;
1219 
1220  return SCIP_OKAY;
1221  }
1222  }
1223 
1224  *result = SCIP_DIDNOTRUN;
1225 
1226  /* calculate the maximal number of branching nodes until heuristic is aborted */
1227  nodelimit = calcNodeLimit(scip, heur, heurdata);
1228 
1229  /* check whether we have enough nodes left to call subproblem solving */
1230  if( nodelimit < heurdata->minnodes )
1231  return SCIP_OKAY;
1232 
1233  if( SCIPisStopped(scip) )
1234  return SCIP_OKAY;
1235 
1236  SCIP_CALL( SCIPgetVarsData(scip, &vars, &nvars, &nbinvars, &nintvars, NULL, NULL) );
1237  assert(nvars > 0);
1238 
1239  /* check whether discrete variables are present */
1240  if( nbinvars == 0 && nintvars == 0 )
1241  return SCIP_OKAY;
1242 
1243  *result = SCIP_DIDNOTFIND;
1244 
1245  keepthisscip = heurdata->keepsubscip;
1246 
1247  /* check if variable number increased since last call to the sub-SCIP */
1248  if( heurdata->subscipdata->subscip != NULL && heurdata->subscipdata->nsubvars != nvars )
1249  {
1250  SCIPdebugMsg(scip, "Free subscip of LP face heuristic because variable number %d changed since last call (was %d)\n",
1251  nvars, heurdata->subscipdata->nsubvars);
1252 
1253  SCIP_CALL( subscipdataFreeSubscip(scip, heurdata->subscipdata) );
1254  }
1255  else if( heurdata->subscipdata->subscip != NULL && SCIPisGT(scip, focusnodelb, heurdata->subscipdata->objbound) )
1256  {
1257  SCIPdebugMsg(scip, "Free subscip of LP face heuristic because of different dual bound: %16.9g > %16.9g\n",
1258  SCIPretransformObj(scip, focusnodelb), SCIPretransformObj(scip, heurdata->subscipdata->objbound));
1259 
1260  SCIP_CALL( subscipdataFreeSubscip(scip, heurdata->subscipdata) );
1261  }
1262 
1263 
1264  /* retrieve the sub-SCIP from the heuristic data structure */
1265  if( heurdata->subscipdata->subscip != NULL )
1266  {
1267  subscip = heurdata->subscipdata->subscip;
1268  subvars = heurdata->subscipdata->subvars;
1269  nvars = heurdata->subscipdata->nsubvars;
1270 
1271  SCIPdebug(
1272  SCIPdebugMsg(scip, "Loaded sub-SCIP from previous run:\n");
1273  SCIP_CALL( subscipGetInfo(scip, subscip) );
1274  )
1275  }
1276  else
1277  {
1278  assert(heurdata->subscipdata->subscip == NULL);
1279  SCIPdebugMsg(scip, "Creating new sub-Problem for LP face heuristic\n");
1280 
1281  /* allocate memory to hold sub-SCIP variables */
1282  SCIP_CALL( SCIPallocBufferArray(scip, &subvars, nvars) );
1283 
1284  /* initialize the subproblem */
1285  SCIP_CALL( SCIPcreate(&subscip) );
1286 
1287  retcode = setupSubscipLpface(scip, subscip, heurdata, subvars, vars, result, &keepthisscip, nvars);
1288 
1289  SCIP_CALL( retcode );
1290 
1291  if( *result == SCIP_DIDNOTRUN )
1292  goto TERMINATE;
1293  }
1294 
1295  retcode = solveSubscipLpface(scip, subscip, heur, heurdata, subvars, result, focusnodelb, &keepthisscip);
1296 
1297  SCIP_CALL( retcode );
1298 
1299 TERMINATE:
1300  /* free subproblem or store it for the next run of the heuristic */
1301  if( ! keepthisscip )
1302  {
1303  /* we only allocated buffer memory if no previous subscip was reinstalled */
1304  if( heurdata->subscipdata->subscip == NULL )
1305  {
1306  SCIPfreeBufferArray(scip, &subvars);
1307  SCIP_CALL( SCIPfree(&subscip) );
1308  }
1309  else
1310  SCIP_CALL( subscipdataFreeSubscip(scip, heurdata->subscipdata) );
1311 
1312  subscipdataReset(heurdata->subscipdata);
1313  }
1314  else
1315  {
1316  /* if the subscip has not yet been stored, we copy the subscip into the heuristic data to keep it for the next run */
1317  if( heurdata->subscipdata->subscip == NULL )
1318  {
1319  SCIP_CALL( subscipdataCopySubscip(scip, heurdata->subscipdata, subscip, subvars, nvars) );
1320  SCIPfreeBufferArray(scip, &subvars);
1321  }
1322  else
1323  {
1324  assert(heurdata->subscipdata->subscip == subscip);
1325  assert(heurdata->subscipdata->subvars == subvars);
1326  assert(heurdata->subscipdata->nsubvars == nvars);
1327  }
1328  }
1329 
1330  return SCIP_OKAY;
1331 }
1332 
1333 /*
1334  * primal heuristic specific interface methods
1335  */
1336 
1337 /** creates the lpface primal heuristic and includes it in SCIP */
1339  SCIP* scip /**< SCIP data structure */
1340  )
1342  SCIP_HEURDATA* heurdata;
1343  SCIP_HEUR* heur;
1344 
1345  /* create Lpface primal heuristic data */
1346  SCIP_CALL( SCIPallocBlockMemory(scip, &heurdata) );
1347 
1348  heurdata->subscipdata = NULL;
1349 
1350  /* include primal heuristic */
1351  SCIP_CALL( SCIPincludeHeurBasic(scip, &heur,
1353  HEUR_MAXDEPTH, HEUR_TIMING, HEUR_USESSUBSCIP, heurExecLpface, heurdata) );
1354 
1355  assert(heur != NULL);
1356 
1357  /* set non-NULL pointers to callback methods */
1358  SCIP_CALL( SCIPsetHeurCopy(scip, heur, heurCopyLpface) );
1359  SCIP_CALL( SCIPsetHeurFree(scip, heur, heurFreeLpface) );
1360  SCIP_CALL( SCIPsetHeurInit(scip, heur, heurInitLpface) );
1361  SCIP_CALL( SCIPsetHeurInitsol(scip, heur, heurInitsolLpface) );
1362  SCIP_CALL( SCIPsetHeurExitsol(scip, heur, heurExitsolLpface) );
1363  SCIP_CALL( SCIPsetHeurExit(scip, heur, heurExitLpface) );
1364 
1365  /* add lpface primal heuristic parameters */
1366  SCIP_CALL( SCIPaddLongintParam(scip, "heuristics/" HEUR_NAME "/nodesofs",
1367  "number of nodes added to the contingent of the total nodes",
1368  &heurdata->nodesofs, FALSE, DEFAULT_NODESOFS, 0LL, SCIP_LONGINT_MAX, NULL, NULL) );
1369 
1370  SCIP_CALL( SCIPaddLongintParam(scip, "heuristics/" HEUR_NAME "/maxnodes",
1371  "maximum number of nodes to regard in the subproblem",
1372  &heurdata->maxnodes, TRUE, DEFAULT_MAXNODES, 0LL, SCIP_LONGINT_MAX, NULL, NULL) );
1373 
1374  SCIP_CALL( SCIPaddLongintParam(scip, "heuristics/" HEUR_NAME "/minnodes",
1375  "minimum number of nodes required to start the subproblem",
1376  &heurdata->minnodes, TRUE, DEFAULT_MINNODES, 0LL, SCIP_LONGINT_MAX, NULL, NULL) );
1377 
1378  SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/nodesquot",
1379  "contingent of sub problem nodes in relation to the number of nodes of the original problem",
1380  &heurdata->nodesquot, FALSE, DEFAULT_NODESQUOT, 0.0, 1.0, NULL, NULL) );
1381 
1382  SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/minfixingrate",
1383  "required percentage of fixed integer variables in sub-MIP to run",
1384  &heurdata->minfixingrate, FALSE, DEFAULT_MINFIXINGRATE, 0.0, 1.0, NULL, NULL) );
1385 
1386  SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/lplimfac",
1387  "factor by which the limit on the number of LP depends on the node limit",
1388  &heurdata->lplimfac, TRUE, DEFAULT_LPLIMFAC, 1.0, SCIP_REAL_MAX, NULL, NULL) );
1389 
1390  SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/uselprows",
1391  "should subproblem be created out of the rows in the LP rows?",
1392  &heurdata->uselprows, TRUE, DEFAULT_USELPROWS, NULL, NULL) );
1393 
1394  SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/dualbasisequations",
1395  "should dually nonbasic rows be turned into equations?",
1396  &heurdata->dualbasisequations, TRUE, DEFAULT_DUALBASISEQUATIONS, NULL, NULL) );
1397 
1398  SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/keepsubscip",
1399  "should the heuristic continue solving the same sub-SCIP?",
1400  &heurdata->keepsubscip, TRUE, DEFAULT_KEEPSUBSCIP, NULL, NULL) );
1401 
1402  SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/copycuts",
1403  "if uselprows == FALSE, should all active cuts from cutpool be copied to constraints in subproblem?",
1404  &heurdata->copycuts, TRUE, DEFAULT_COPYCUTS, NULL, NULL) );
1405 
1406  SCIP_CALL( SCIPaddCharParam(scip, "heuristics/" HEUR_NAME "/subscipobjective",
1407  "objective function in the sub-SCIP: (z)ero, (r)oot-LP-difference, (i)nference, LP (f)ractionality, (o)riginal",
1408  &heurdata->subscipobjective, TRUE, 'z', "forzi", NULL, NULL) );
1409 
1410  SCIP_CALL( SCIPaddIntParam(scip, "heuristics/" HEUR_NAME "/minpathlen",
1411  "the minimum active search tree path length along which lower bound hasn't changed before heuristic becomes active",
1412  &heurdata->minpathlen, TRUE, DEFAULT_MINPATHLEN, 0, 65531, NULL, NULL) );
1413 
1414  return SCIP_OKAY;
1415 }
enum SCIP_Result SCIP_RESULT
Definition: type_result.h:52
SCIP_RETCODE SCIPsetHeurExitsol(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEUREXITSOL((*heurexitsol)))
Definition: scip.c:8209
#define SCIPfreeBlockMemoryArray(scip, ptr, num)
Definition: scip.h:22604
SCIP_RETCODE SCIPchgVarLbGlobal(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound)
Definition: scip.c:22276
SCIP_Real SCIPgetSolvingTime(SCIP *scip)
Definition: scip.c:46300
#define SCIP_EVENTTYPE_LPSOLVED
Definition: type_event.h:84
SCIP_RETCODE SCIPsetSeparating(SCIP *scip, SCIP_PARAMSETTING paramsetting, SCIP_Bool quiet)
Definition: scip.c:5158
SCIP_Real SCIPgetVarAvgInferences(SCIP *scip, SCIP_VAR *var, SCIP_BRANCHDIR dir)
Definition: scip.c:26630
SCIP_Bool SCIPisFeasEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip.c:47292
SCIP_NODE * SCIPgetCurrentNode(SCIP *scip)
Definition: scip.c:41398
#define DEFAULT_USELPROWS
Definition: heur_lpface.c:48
SCIP_Longint SCIPgetNLPIterations(SCIP *scip)
Definition: scip.c:42327
#define EVENTHDLR_DESC
Definition: heur_lpface.c:61
#define DEFAULT_NODESOFS
Definition: heur_lpface.c:45
SCIP_CONSHDLR * SCIPfindConshdlr(SCIP *scip, const char *name)
Definition: scip.c:6604
SCIP_Real SCIPnodeGetLowerbound(SCIP_NODE *node)
Definition: tree.c:7360
SCIP_Real SCIPvarGetLbGlobal(SCIP_VAR *var)
Definition: var.c:17276
SCIP_RETCODE SCIPgetRealParam(SCIP *scip, const char *name, SCIP_Real *value)
Definition: scip.c:4489
#define SCIP_MAXSTRLEN
Definition: def.h:259
#define HEUR_FREQOFS
Definition: heur_lpface.c:37
static SCIP_RETCODE createNewSol(SCIP *scip, SCIP *subscip, SCIP_VAR **subvars, SCIP_HEUR *heur, SCIP_SOL *subsol, int *solindex, SCIP_Bool *success)
Definition: heur_lpface.c:339
SCIP_RETCODE SCIPsetHeurExit(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEUREXIT((*heurexit)))
Definition: scip.c:8177
int SCIProwGetNNonz(SCIP_ROW *row)
Definition: lp.c:16402
int SCIPgetNOrigVars(SCIP *scip)
Definition: scip.c:12246
SCIP_Real SCIPvarGetLbLocal(SCIP_VAR *var)
Definition: var.c:17332
SCIP_Real SCIPgetColRedcost(SCIP *scip, SCIP_COL *col)
Definition: scip.c:30194
SCIP_Bool SCIPisGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip.c:47009
#define HEUR_PRIORITY
Definition: heur_lpface.c:35
SCIP_RETCODE SCIPincludeEventhdlrBasic(SCIP *scip, SCIP_EVENTHDLR **eventhdlrptr, const char *name, const char *desc, SCIP_DECL_EVENTEXEC((*eventexec)), SCIP_EVENTHDLRDATA *eventhdlrdata)
Definition: scip.c:8611
const char * SCIProwGetName(SCIP_ROW *row)
Definition: lp.c:16540
SCIP_NODE * SCIPnodeGetParent(SCIP_NODE *node)
Definition: tree.c:7620
static SCIP_Longint calcNodeLimit(SCIP *scip, SCIP_HEUR *heur, SCIP_HEURDATA *heurdata)
Definition: heur_lpface.c:416
#define heurExitLpface
Definition: heur_lpface.c:1116
#define DEFAULT_MAXNODES
Definition: heur_lpface.c:42
SCIP_Real SCIPvarGetRootSol(SCIP_VAR *var)
Definition: var.c:12758
SCIP_RETCODE SCIPgetVarsData(SCIP *scip, SCIP_VAR ***vars, int *nvars, int *nbinvars, int *nintvars, int *nimplvars, int *ncontvars)
Definition: scip.c:11680
SCIP_SOL ** SCIPgetSols(SCIP *scip)
Definition: scip.c:39826
static SCIP_RETCODE createRows(SCIP *scip, SCIP *subscip, SCIP_VAR **subvars, SCIP_Bool dualbasisequations)
Definition: heur_lpface.c:199
SCIP_Real SCIProwGetLhs(SCIP_ROW *row)
Definition: lp.c:16481
#define FALSE
Definition: def.h:64
SCIP_RETCODE SCIPhashmapCreate(SCIP_HASHMAP **hashmap, BMS_BLKMEM *blkmem, int mapsize)
Definition: misc.c:2793
const char * SCIPeventhdlrGetName(SCIP_EVENTHDLR *eventhdlr)
Definition: event.c:278
SCIP_RETCODE SCIPincludeHeurLpface(SCIP *scip)
Definition: heur_lpface.c:1341
SCIP_RETCODE SCIPaddLongintParam(SCIP *scip, const char *name, const char *desc, SCIP_Longint *valueptr, SCIP_Bool isadvanced, SCIP_Longint defaultvalue, SCIP_Longint minvalue, SCIP_Longint maxvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition: scip.c:4293
SCIP_Real SCIPinfinity(SCIP *scip)
Definition: scip.c:47022
int SCIPsnprintf(char *t, int len, const char *s,...)
Definition: misc.c:10011
#define TRUE
Definition: def.h:63
#define SCIPdebug(x)
Definition: pub_message.h:74
#define HEUR_MAXDEPTH
Definition: heur_lpface.c:38
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:53
SCIP_RETCODE SCIPwriteOrigProblem(SCIP *scip, const char *filename, const char *extension, SCIP_Bool genericnames)
Definition: scip.c:10426
SCIP_RETCODE SCIPsetPresolving(SCIP *scip, SCIP_PARAMSETTING paramsetting, SCIP_Bool quiet)
Definition: scip.c:5132
SCIP_BRANCHRULE * SCIPfindBranchrule(SCIP *scip, const char *name)
Definition: scip.c:9269
int SCIPvarGetProbindex(SCIP_VAR *var)
Definition: var.c:16969
SCIP_Bool SCIPisDualfeasZero(SCIP *scip, SCIP_Real val)
Definition: scip.c:47530
struct SCIP_HeurData SCIP_HEURDATA
Definition: type_heur.h:51
#define SCIPfreeBlockMemory(scip, ptr)
Definition: scip.h:22602
SCIP_RETCODE SCIPincludeHeurBasic(SCIP *scip, SCIP_HEUR **heur, const char *name, const char *desc, char dispchar, int priority, int freq, int freqofs, int maxdepth, SCIP_HEURTIMING timingmask, SCIP_Bool usessubscip, SCIP_DECL_HEUREXEC((*heurexec)), SCIP_HEURDATA *heurdata)
Definition: scip.c:8084
#define DEFAULT_KEEPSUBSCIP
Definition: heur_lpface.c:55
#define DEFAULT_NODESQUOT
Definition: heur_lpface.c:46
#define HEUR_DISPCHAR
Definition: heur_lpface.c:34
void * SCIPhashmapGetImage(SCIP_HASHMAP *hashmap, void *origin)
Definition: misc.c:2931
SCIP_Bool SCIPisEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip.c:46957
#define SCIP_LONGINT_MAX
Definition: def.h:135
#define SCIPfreeBufferArray(scip, ptr)
Definition: scip.h:22632
SCIP_RETCODE SCIPcreate(SCIP **scip)
Definition: scip.c:748
void SCIPheurSetData(SCIP_HEUR *heur, SCIP_HEURDATA *heurdata)
Definition: heur.c:1119
#define SCIPallocBlockMemory(scip, ptr)
Definition: scip.h:22585
SCIP_RETCODE SCIPsetRealParam(SCIP *scip, const char *name, SCIP_Real value)
Definition: scip.c:4804
SCIP_Real SCIProwGetDualsol(SCIP_ROW *row)
Definition: lp.c:16501
SCIP_RETCODE SCIPchgVarUbGlobal(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound)
Definition: scip.c:22363
#define SCIPdebugMsg
Definition: scip.h:455
SCIP_RETCODE SCIPaddIntParam(SCIP *scip, const char *name, const char *desc, int *valueptr, SCIP_Bool isadvanced, int defaultvalue, int minvalue, int maxvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition: scip.c:4265
SCIP_RETCODE SCIPcopyParamSettings(SCIP *sourcescip, SCIP *targetscip)
Definition: scip.c:3501
static SCIP_DECL_HEUREXITSOL(heurExitsolLpface)
Definition: heur_lpface.c:1069
SCIP_Real SCIPgetPresolvingTime(SCIP *scip)
Definition: scip.c:46364
SCIP_RETCODE SCIPprintStatistics(SCIP *scip, FILE *file)
Definition: scip.c:45645
SCIP_RETCODE SCIPaddCoefLinear(SCIP *scip, SCIP_CONS *cons, SCIP_VAR *var, SCIP_Real val)
void SCIPinfoMessage(SCIP *scip, FILE *file, const char *formatstr,...)
Definition: scip.c:1343
SCIP_RETCODE SCIPcreateProbBasic(SCIP *scip, const char *name)
Definition: scip.c:9997
SCIP_Real SCIPgetLowerboundRoot(SCIP *scip)
Definition: scip.c:43316
const char * SCIPgetProbName(SCIP *scip)
Definition: scip.c:10885
SCIP_Bool SCIPisLPRelax(SCIP *scip)
Definition: scip.c:29344
static SCIP_RETCODE subscipdataFreeSubscip(SCIP *scip, SUBSCIPDATA *subscipdata)
Definition: heur_lpface.c:584
SCIP_Real SCIPvarGetUbGlobal(SCIP_VAR *var)
Definition: var.c:17286
#define SCIPduplicateBlockMemoryArray(scip, ptr, source, num)
Definition: scip.h:22599
static SCIP_DECL_HEURINITSOL(heurInitsolLpface)
Definition: heur_lpface.c:1044
#define DEFAULT_LPLIMFAC
Definition: heur_lpface.c:47
static SCIP_RETCODE setupSubscipLpface(SCIP *scip, SCIP *subscip, SCIP_HEURDATA *heurdata, SCIP_VAR **subvars, SCIP_VAR **vars, SCIP_RESULT *result, SCIP_Bool *keepthisscip, int nvars)
Definition: heur_lpface.c:761
SCIP_RETCODE SCIPsetHeurInitsol(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURINITSOL((*heurinitsol)))
Definition: scip.c:8193
SCIP_RETCODE SCIPsolve(SCIP *scip)
Definition: scip.c:16109
const char * SCIPheurGetName(SCIP_HEUR *heur)
Definition: heur.c:1198
static SCIP_DECL_HEUREXEC(heurExecLpface)
Definition: heur_lpface.c:1121
#define SCIPerrorMessage
Definition: pub_message.h:45
SCIP_Bool SCIPisParamFixed(SCIP *scip, const char *name)
Definition: scip.c:4401
SCIP_RETCODE SCIPaddCons(SCIP *scip, SCIP_CONS *cons)
Definition: scip.c:12585
SCIP_RETCODE SCIPsetHeurFree(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURFREE((*heurfree)))
Definition: scip.c:8145
SCIP_Bool SCIPisLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip.c:46970
SCIP_RETCODE SCIPgetSolVals(SCIP *scip, SCIP_SOL *sol, int nvars, SCIP_VAR **vars, SCIP_Real *vals)
Definition: scip.c:38942
SCIP_Bool SCIProwIsLocal(SCIP_ROW *row)
Definition: lp.c:16590
SCIP_RETCODE SCIPcopyVars(SCIP *sourcescip, SCIP *targetscip, SCIP_HASHMAP *varmap, SCIP_HASHMAP *consmap, SCIP_VAR **fixedvars, SCIP_Real *fixedvals, int nfixedvars, SCIP_Bool global)
Definition: scip.c:2341
SCIP_RETCODE SCIPsetBoolParam(SCIP *scip, const char *name, SCIP_Bool value)
Definition: scip.c:4630
SCIP_STATUS SCIPgetStatus(SCIP *scip)
Definition: scip.c:928
SCIP_RETCODE SCIPcopyCuts(SCIP *sourcescip, SCIP *targetscip, SCIP_HASHMAP *varmap, SCIP_HASHMAP *consmap, SCIP_Bool global, int *ncutsadded)
Definition: scip.c:3065
BMS_BLKMEM * SCIPblkmem(SCIP *scip)
Definition: scip.c:46725
struct SCIP_EventData SCIP_EVENTDATA
Definition: type_event.h:155
const char * SCIPvarGetName(SCIP_VAR *var)
Definition: var.c:16662
#define DEFAULT_MINFIXINGRATE
Definition: heur_lpface.c:44
void SCIPhashmapFree(SCIP_HASHMAP **hashmap)
Definition: misc.c:2826
static SCIP_RETCODE setupSubproblem(SCIP *scip, SCIP *subscip, SCIP_VAR **subvars, SCIP_HEURDATA *heurdata, SCIP_Bool *success)
Definition: heur_lpface.c:284
static void subscipdataReset(SUBSCIPDATA *subscipdata)
Definition: heur_lpface.c:572
SCIP_Real SCIPgetSolTransObj(SCIP *scip, SCIP_SOL *sol)
Definition: scip.c:39035
SCIP_Real SCIPvarGetLPSol(SCIP_VAR *var)
Definition: var.c:17650
#define SCIP_CALL(x)
Definition: def.h:350
SCIP_Real SCIPgetLowerbound(SCIP *scip)
Definition: scip.c:43271
SCIP_Real SCIProwGetRhs(SCIP_ROW *row)
Definition: lp.c:16491
void SCIPverbMessage(SCIP *scip, SCIP_VERBLEVEL msgverblevel, FILE *file, const char *formatstr,...)
Definition: scip.c:1360
#define DEFAULT_DUALBASISEQUATIONS
Definition: heur_lpface.c:54
SCIP_Longint SCIPheurGetNCalls(SCIP_HEUR *heur)
Definition: heur.c:1324
SCIP_RETCODE SCIPgetLongintParam(SCIP *scip, const char *name, SCIP_Longint *value)
Definition: scip.c:4470
SCIP_COL ** SCIProwGetCols(SCIP_ROW *row)
Definition: lp.c:16427
static SCIP_RETCODE fixVariables(SCIP *scip, SCIP *subscip, SCIP_VAR **subvars, SCIP_HEURDATA *heurdata, SCIP_Bool *success)
Definition: heur_lpface.c:115
SCIP_RETCODE SCIPchgVarObj(SCIP *scip, SCIP_VAR *var, SCIP_Real newobj)
Definition: scip.c:21847
#define SCIPallocBufferArray(scip, ptr, num)
Definition: scip.h:22620
SCIP_Real * SCIProwGetVals(SCIP_ROW *row)
Definition: lp.c:16437
#define HEUR_FREQ
Definition: heur_lpface.c:36
SCIP * subscip
Definition: heur_lpface.c:70
public data structures and miscellaneous methods
#define DEFAULT_COPYCUTS
Definition: heur_lpface.c:51
#define SCIP_Bool
Definition: def.h:61
SCIP_RETCODE SCIPincludeDefaultPlugins(SCIP *scip)
SCIP_RETCODE SCIPcatchEvent(SCIP *scip, SCIP_EVENTTYPE eventtype, SCIP_EVENTHDLR *eventhdlr, SCIP_EVENTDATA *eventdata, int *filterpos)
Definition: scip.c:41152
static SCIP_DECL_HEURFREE(heurFreeLpface)
Definition: heur_lpface.c:998
SCIP_LPSOLSTAT SCIPgetLPSolstat(SCIP *scip)
Definition: scip.c:29287
SCIP_EVENTTYPE SCIPeventGetType(SCIP_EVENT *event)
Definition: event.c:959
enum SCIP_Status SCIP_STATUS
Definition: type_stat.h:57
static SCIP_RETCODE changeSubvariableObjective(SCIP *scip, SCIP *subscip, SCIP_VAR *var, SCIP_VAR *subvar, SCIP_HEURDATA *heurdata)
Definition: heur_lpface.c:671
int SCIPgetDepth(SCIP *scip)
Definition: scip.c:43039
#define MAX(x, y)
Definition: tclique_def.h:75
SCIP_RETCODE SCIPtrySolFree(SCIP *scip, SCIP_SOL **sol, SCIP_Bool printreason, SCIP_Bool completely, SCIP_Bool checkbounds, SCIP_Bool checkintegrality, SCIP_Bool checklprows, SCIP_Bool *stored)
Definition: scip.c:40788
SCIP_RETCODE SCIPsetIntParam(SCIP *scip, const char *name, int value)
Definition: scip.c:4688
SCIP_Real SCIPvarGetObj(SCIP_VAR *var)
Definition: var.c:17124
int SCIPgetNSols(SCIP *scip)
Definition: scip.c:39777
#define HEUR_NAME
Definition: heur_lpface.c:32
static SCIP_RETCODE setSubscipLimits(SCIP *scip, SCIP *subscip, SCIP_HEUR *heur, SCIP_HEURDATA *heurdata, SCIP_Bool *success)
Definition: heur_lpface.c:448
SCIP_COL * SCIPvarGetCol(SCIP_VAR *var)
Definition: var.c:16990
Constraint handler for linear constraints in their most general form, .
int SCIPgetNObjVars(SCIP *scip)
Definition: scip.c:12034
SCIP_Bool SCIPisInfinity(SCIP *scip, SCIP_Real val)
Definition: scip.c:47033
SCIP_Real objbound
Definition: heur_lpface.c:73
static SCIP_DECL_EVENTEXEC(eventExecLpface)
Definition: heur_lpface.c:736
SCIP_RETCODE SCIPsetCharParam(SCIP *scip, const char *name, char value)
Definition: scip.c:4862
#define HEUR_DESC
Definition: heur_lpface.c:33
int SCIPgetNVars(SCIP *scip)
Definition: scip.c:11806
static void updateFailureStatistic(SCIP *scip, SCIP_HEURDATA *heurdata)
Definition: heur_lpface.c:402
#define SCIP_REAL_MAX
Definition: def.h:150
SCIP_RETCODE SCIPcreateConsLinear(SCIP *scip, SCIP_CONS **cons, const char *name, int nvars, SCIP_VAR **vars, SCIP_Real *vals, SCIP_Real lhs, SCIP_Real rhs, SCIP_Bool initial, SCIP_Bool separate, SCIP_Bool enforce, SCIP_Bool check, SCIP_Bool propagate, SCIP_Bool local, SCIP_Bool modifiable, SCIP_Bool dynamic, SCIP_Bool removable, SCIP_Bool stickingatnode)
SCIP_Real SCIProwGetConstant(SCIP_ROW *row)
Definition: lp.c:16447
SCIP_Bool SCIPisObjIntegral(SCIP *scip)
Definition: scip.c:11380
SCIP_Real SCIPgetLPObjval(SCIP *scip)
Definition: scip.c:29366
SCIP_SOL * SCIPgetBestSol(SCIP *scip)
Definition: scip.c:39876
SCIP_Bool SCIPisGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip.c:46996
SCIP_Bool SCIPisIntegral(SCIP *scip, SCIP_Real val)
Definition: scip.c:47106
SCIP_RETCODE SCIPaddCharParam(SCIP *scip, const char *name, const char *desc, char *valueptr, SCIP_Bool isadvanced, char defaultvalue, const char *allowedvalues, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition: scip.c:4349
SCIP_VAR ** subvars
Definition: heur_lpface.c:71
SCIP_VAR * SCIPcolGetVar(SCIP_COL *col)
Definition: lp.c:16251
SCIP_Longint SCIPgetMemUsed(SCIP *scip)
Definition: scip.c:46768
SCIP_RETCODE SCIPreleaseCons(SCIP *scip, SCIP_CONS **cons)
Definition: scip.c:27755
#define SCIP_DECL_HEUREXIT(x)
Definition: type_heur.h:86
static SCIP_RETCODE setSubscipParameters(SCIP *scip, SCIP *subscip)
Definition: heur_lpface.c:503
SCIP_RETCODE SCIPcopy(SCIP *sourcescip, SCIP *targetscip, SCIP_HASHMAP *varmap, SCIP_HASHMAP *consmap, const char *suffix, SCIP_Bool global, SCIP_Bool enablepricing, SCIP_Bool passmessagehdlr, SCIP_Bool *valid)
Definition: scip.c:3795
#define DEFAULT_MINPATHLEN
Definition: heur_lpface.c:56
SCIP_RETCODE SCIPsetHeurInit(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURINIT((*heurinit)))
Definition: scip.c:8161
SCIP_Real SCIPretransformObj(SCIP *scip, SCIP_Real obj)
Definition: scip.c:39120
SCIP_Longint SCIPgetMemExternEstim(SCIP *scip)
Definition: scip.c:46794
SCIP_NODESEL * SCIPfindNodesel(SCIP *scip, const char *name)
Definition: scip.c:8957
#define HEUR_TIMING
Definition: heur_lpface.c:39
SCIP_VAR ** SCIPgetVars(SCIP *scip)
Definition: scip.c:11761
SCIP_VARSTATUS SCIPvarGetStatus(SCIP_VAR *var)
Definition: var.c:16781
#define EVENTHDLR_NAME
Definition: heur_lpface.c:60
#define SCIP_Real
Definition: def.h:149
static SCIP_RETCODE solveSubscipLpface(SCIP *scip, SCIP *subscip, SCIP_HEUR *heur, SCIP_HEURDATA *heurdata, SCIP_VAR **subvars, SCIP_RESULT *result, SCIP_Real focusnodelb, SCIP_Bool *keepthisscip)
Definition: heur_lpface.c:855
SCIP_Bool SCIPisStopped(SCIP *scip)
Definition: scip.c:1145
#define SCIP_INVALID
Definition: def.h:169
#define HEUR_USESSUBSCIP
Definition: heur_lpface.c:40
#define SCIP_Longint
Definition: def.h:134
SCIP_Bool SCIPallColsInLP(SCIP *scip)
Definition: scip.c:29713
SCIP_Real SCIPfrac(SCIP *scip, SCIP_Real val)
Definition: scip.c:47179
static SCIP_RETCODE subscipdataCopySubscip(SCIP *scip, SUBSCIPDATA *subscipdata, SCIP *subscip, SCIP_VAR **subvars, int nvars)
Definition: heur_lpface.c:613
SCIP_RETCODE SCIPsetSolVals(SCIP *scip, SCIP_SOL *sol, int nvars, SCIP_VAR **vars, SCIP_Real *vals)
Definition: scip.c:38807
SCIP_Real SCIPgetNodeLowerbound(SCIP *scip, SCIP_NODE *node)
Definition: scip.c:13439
SCIP_RETCODE SCIPtransformProb(SCIP *scip)
Definition: scip.c:13929
SCIP_Bool SCIPisZero(SCIP *scip, SCIP_Real val)
Definition: scip.c:47070
SCIP_Bool SCIPisLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip.c:46983
SCIP_RETCODE SCIPsetHeurCopy(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURCOPY((*heurcopy)))
Definition: scip.c:8129
SCIP_Real SCIPvarGetUbLocal(SCIP_VAR *var)
Definition: var.c:17342
SCIP_RETCODE SCIPwriteParams(SCIP *scip, const char *filename, SCIP_Bool comments, SCIP_Bool onlychanged)
Definition: scip.c:4993
SCIP_RETCODE SCIPinterruptSolve(SCIP *scip)
Definition: scip.c:17318
SCIP_RETCODE SCIPgetLPRowsData(SCIP *scip, SCIP_ROW ***rows, int *nrows)
Definition: scip.c:29634
#define SCIP_CALL_ABORT(x)
Definition: def.h:329
SCIP_HEURDATA * SCIPheurGetData(SCIP_HEUR *heur)
Definition: heur.c:1109
static SCIP_DECL_HEURINIT(heurInitLpface)
Definition: heur_lpface.c:1018
SCIP_Longint SCIPgetNNodes(SCIP *scip)
Definition: scip.c:42127
SCIP_Longint SCIPgetNLPs(SCIP *scip)
Definition: scip.c:42308
SCIP_Bool SCIPvarIsIntegral(SCIP_VAR *var)
Definition: var.c:16853
#define DEFAULT_MINNODES
Definition: heur_lpface.c:43
SCIP_Real SCIPgetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var)
Definition: scip.c:38905
default SCIP plugins
int SCIPsolGetIndex(SCIP_SOL *sol)
Definition: sol.c:2579
SCIP_RETCODE SCIPaddRealParam(SCIP *scip, const char *name, const char *desc, SCIP_Real *valueptr, SCIP_Bool isadvanced, SCIP_Real defaultvalue, SCIP_Real minvalue, SCIP_Real maxvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition: scip.c:4321
SCIP_RETCODE SCIPsetSubscipsOff(SCIP *scip, SCIP_Bool quiet)
Definition: scip.c:5083
SCIP_RETCODE SCIPsetLongintParam(SCIP *scip, const char *name, SCIP_Longint value)
Definition: scip.c:4746
SCIP callable library.
SCIP_RETCODE SCIPaddBoolParam(SCIP *scip, const char *name, const char *desc, SCIP_Bool *valueptr, SCIP_Bool isadvanced, SCIP_Bool defaultvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition: scip.c:4239
LNS heuristic that tries to compute integral solution on optimal LP face.
SCIP_Real SCIPgetRowActivity(SCIP *scip, SCIP_ROW *row)
Definition: scip.c:31065
SCIP_RETCODE SCIPfree(SCIP **scip)
Definition: scip.c:780
SCIP_RETCODE SCIPcreateSol(SCIP *scip, SCIP_SOL **sol, SCIP_HEUR *heur)
Definition: scip.c:37872
static SCIP_DECL_HEURCOPY(heurCopyLpface)
Definition: heur_lpface.c:984