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