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