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