Scippy

SCIP

Solving Constraint Integer Programs

heur_proximity.c
Go to the documentation of this file.
1 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
2 /* */
3 /* This file is part of the program and library */
4 /* SCIP --- Solving Constraint Integer Programs */
5 /* */
6 /* Copyright (C) 2002-2017 Konrad-Zuse-Zentrum */
7 /* fuer Informationstechnik Berlin */
8 /* */
9 /* SCIP is distributed under the terms of the ZIB Academic License. */
10 /* */
11 /* You should have received a copy of the ZIB Academic License */
12 /* along with SCIP; see the file COPYING. If not email to scip@zib.de. */
13 /* */
14 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
15 
16 /**@file heur_proximity.c
17  * @brief improvement heuristic which uses an auxiliary objective instead of the original objective function which
18  * is itself added as a constraint to a sub-SCIP instance. The heuristic was presented by Matteo Fischetti
19  * and Michele Monaci
20  *
21  *
22  * @author Gregor Hendel
23  */
24 
25 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
26 
27 #include <assert.h>
28 #include <string.h>
29 
30 #include "scip/heur_proximity.h"
31 #include "scip/cons_linear.h"
32 
33 #define HEUR_NAME "proximity"
34 #define HEUR_DESC "heuristic trying to improve the incumbent by an auxiliary proximity objective function"
35 #define HEUR_DISPCHAR 'P'
36 #define HEUR_PRIORITY -2000000
37 #define HEUR_FREQ -1
38 #define HEUR_FREQOFS 0
39 #define HEUR_MAXDEPTH -1
40 #define HEUR_TIMING SCIP_HEURTIMING_AFTERNODE
41 #define HEUR_USESSUBSCIP TRUE /**< does the heuristic use a secondary SCIP instance? */
42 
43 /* event handler properties */
44 #define EVENTHDLR_NAME "Proximity"
45 #define EVENTHDLR_DESC "LP event handler for " HEUR_NAME " heuristic"
46 
47 /* default values for proximity-specific parameters */
48 /* todo refine these values */
49 #define DEFAULT_MAXNODES 10000LL /* maximum number of nodes to regard in the subproblem */
50 #define DEFAULT_MINIMPROVE 0.02 /* factor by which proximity should at least improve the incumbent */
51 #define DEFAULT_MINGAP 0.01 /* minimum primal-dual gap for which the heuristic is executed */
52 #define DEFAULT_MINNODES 1LL /* minimum number of nodes to regard in the subproblem */
53 #define DEFAULT_MINLPITERS 200LL /* minimum number of LP iterations to perform in one sub-mip */
54 #define DEFAULT_MAXLPITERS 100000LL /* maximum number of LP iterations to be performed in the subproblem */
55 #define DEFAULT_NODESOFS 50LL /* number of nodes added to the contingent of the total nodes */
56 #define DEFAULT_WAITINGNODES 100LL /* default waiting nodes since last incumbent before heuristic is executed */
57 #define DEFAULT_NODESQUOT 0.1 /* default quotient of sub-MIP nodes with respect to number of processed nodes*/
58 #define DEFAULT_USELPROWS FALSE /* should subproblem be constructed based on LP row information? */
59 #define DEFAULT_BINVARQUOT 0.1 /* default threshold for percentage of binary variables required to start */
60 #define DEFAULT_RESTART TRUE /* should the heuristic immediately run again on its newly found solution? */
61 #define DEFAULT_USEFINALLP FALSE /* should the heuristic solve a final LP in case of continuous objective variables? */
62 #define DEFAULT_LPITERSQUOT 0.2 /* default quotient of sub-MIP LP iterations with respect to LP iterations so far */
63 #define DEFAULT_USEUCT FALSE /* should uct node selection be used at the beginning of the search? */
64 
65 /*
66  * Data structures
67  */
68 
69 /** primal heuristic data */
70 struct SCIP_HeurData
71 {
72  SCIP_Longint maxnodes; /**< maximum number of nodes to regard in the subproblem */
73  SCIP_Longint minnodes; /**< minimum number of nodes to regard in the subproblem */
74  SCIP_Longint maxlpiters; /**< maximum number of LP iterations to be performed in the subproblem */
75  SCIP_Longint nusedlpiters; /**< number of actually performed LP iterations */
76  SCIP_Longint minlpiters; /**< minimum number of LP iterations to perform in one sub-mip */
77  SCIP_Longint nodesofs; /**< number of nodes added to the contingent of the total nodes */
78  SCIP_Longint usednodes; /**< nodes already used by proximity in earlier calls */
79  SCIP_Longint waitingnodes; /**< waiting nodes since last incumbent before heuristic is executed */
80  SCIP_Real lpitersquot; /**< quotient of sub-MIP LP iterations with respect to LP iterations so far */
81  SCIP_Real minimprove; /**< factor by which proximity should at least improve the incumbent */
82  SCIP_Real mingap; /**< minimum primal-dual gap for which the heuristic is executed */
83  SCIP_Real nodesquot; /**< quotient of sub-MIP nodes with respect to number of processed nodes */
84  SCIP_Real binvarquot; /**< threshold for percantage of binary variables required to start */
85 
86  SCIP* subscip; /**< the subscip used by the heuristic */
87  SCIP_HASHMAP* varmapfw; /**< map between scip variables and subscip variables */
88  SCIP_VAR** subvars; /**< variables in subscip */
89  SCIP_CONS* objcons; /**< the objective cutoff constraint of the subproblem */
90 
91  int nsubvars; /**< the number of subvars */
92  int lastsolidx; /**< index of last solution on which the heuristic was processed */
93  int subprobidx; /**< counter for the subproblem index to be solved by proximity */
94 
95  SCIP_Bool uselprows; /**< should subproblem be constructed based on LP row information? */
96  SCIP_Bool restart; /* should the heuristic immediately run again on its newly found solution? */
97  SCIP_Bool usefinallp; /* should the heuristic solve a final LP in case of continuous objective variables? */
98  SCIP_Bool useuct; /**< should uct node selection be used at the beginning of the search? */
99 };
100 
101 
102 /*
103  * Local methods
104  */
105 
106 /** optimizes the continuous variables in an LP diving by fixing all integer variables to the given solution values */
107 static
109  SCIP* scip, /**< SCIP data structure */
110  SCIP_SOL* sol, /**< candidate solution for which continuous variables should be optimized */
111  SCIP_Bool* success /**< was the dive successful? */
112  )
113 {
114  SCIP_VAR** vars;
115  SCIP_RETCODE retstat;
116 
117  int v;
118  int nvars;
119  int ncontvars;
120  int nintvars;
121 
122  SCIP_Bool lperror;
123  SCIP_Bool requiresnlp;
124 
125  assert(success != NULL);
126 
127  SCIP_CALL( SCIPgetVarsData(scip, &vars, &nvars, NULL, NULL, NULL, &ncontvars) );
128 
129  nintvars = nvars - ncontvars;
130 
131  /**@todo in case of an MINLP, if SCIPisNLPConstructed() is TRUE rather solve the NLP instead of the LP */
132  requiresnlp = SCIPisNLPConstructed(scip);
133  if( requiresnlp || ncontvars == 0 )
134  return SCIP_OKAY;
135 
136  /* start diving to calculate the LP relaxation */
137  SCIP_CALL( SCIPstartDive(scip) );
138 
139  /* set the bounds of the variables: fixed for integers, global bounds for continuous */
140  for( v = 0; v < nvars; ++v )
141  {
142  if( SCIPvarGetStatus(vars[v]) == SCIP_VARSTATUS_COLUMN )
143  {
144  SCIP_CALL( SCIPchgVarLbDive(scip, vars[v], SCIPvarGetLbGlobal(vars[v])) );
145  SCIP_CALL( SCIPchgVarUbDive(scip, vars[v], SCIPvarGetUbGlobal(vars[v])) );
146  }
147  }
148  /* apply this after global bounds to not cause an error with intermediate empty domains */
149  for( v = 0; v < nintvars; ++v )
150  {
151  if( SCIPvarGetStatus(vars[v]) == SCIP_VARSTATUS_COLUMN )
152  {
153  SCIP_Real solval;
154 
155  solval = SCIPgetSolVal(scip, sol, vars[v]);
156  SCIP_CALL( SCIPchgVarLbDive(scip, vars[v], solval) );
157  SCIP_CALL( SCIPchgVarUbDive(scip, vars[v], solval) );
158  }
159  }
160 
161  /* solve LP */
162  SCIPdebugMsg(scip, " -> old LP iterations: %" SCIP_LONGINT_FORMAT "\n", SCIPgetNLPIterations(scip));
163 
164  /* Errors in the LP solver should not kill the overall solving process, if the LP is just needed for a heuristic.
165  * Hence in optimized mode, the return code is caught and a warning is printed, only in debug mode, SCIP will stop.
166  */
167  retstat = SCIPsolveDiveLP(scip, -1, &lperror, NULL);
168  if( retstat != SCIP_OKAY )
169  {
170 #ifdef NDEBUG
171  SCIPwarningMessage(scip, "Error while solving LP in Proximity heuristic; LP solve terminated with code <%d>\n",retstat);
172 #else
173  SCIP_CALL( retstat );
174 #endif
175  }
176 
177  SCIPdebugMsg(scip, " -> new LP iterations: %" SCIP_LONGINT_FORMAT "\n", SCIPgetNLPIterations(scip));
178  SCIPdebugMsg(scip, " -> error=%u, status=%d\n", lperror, SCIPgetLPSolstat(scip));
179  if( !lperror && SCIPgetLPSolstat(scip) == SCIP_LPSOLSTAT_OPTIMAL )
180  {
181  SCIP_CALL( SCIPlinkLPSol(scip, sol) );
182  SCIP_CALL( SCIPtrySol(scip, sol, FALSE, FALSE, TRUE, TRUE, TRUE, success) );
183  }
184 
185  /* terminate diving mode */
186  SCIP_CALL( SCIPendDive(scip) );
187 
188  return SCIP_OKAY;
189 }
190 
191 /** creates a new solution for the original problem by copying the solution of the subproblem */
192 static
194  SCIP* scip, /**< original SCIP data structure */
195  SCIP* subscip, /**< SCIP structure of the subproblem */
196  SCIP_VAR** subvars, /**< the variables of the subproblem */
197  SCIP_HEUR* heur, /**< proximity heuristic structure */
198  SCIP_SOL* subsol, /**< solution of the subproblem */
199  SCIP_Bool usefinallp, /**< should continuous variables be optimized by a final LP */
200  SCIP_Bool* success /**< used to store whether new solution was found or not */
201  )
202 {
203  SCIP_VAR** vars; /* the original problem's variables */
204  int nvars; /* the original problem's number of variables */
205  int ncontvars; /* the original problem's number of continuous variables */
206  SCIP_Real* subsolvals; /* solution values of the subproblem */
207  SCIP_SOL* newsol; /* solution to be created for the original problem */
208 
209  assert(scip != NULL);
210  assert(subscip != NULL);
211  assert(subvars != NULL);
212  assert(subsol != NULL);
213  assert(success != NULL);
214 
215  /* get variables' data */
216  SCIP_CALL( SCIPgetVarsData(scip, &vars, &nvars, NULL, NULL, NULL, &ncontvars) );
217 
218  /* sub-SCIP may have more variables than the number of active (transformed) variables in the main SCIP
219  * since constraint copying may have required the copy of variables that are fixed in the main SCIP
220  */
221  assert(nvars <= SCIPgetNOrigVars(subscip));
222 
223  SCIP_CALL( SCIPallocBufferArray(scip, &subsolvals, nvars) );
224 
225  /* copy the solution */
226  SCIP_CALL( SCIPgetSolVals(subscip, subsol, nvars, subvars, subsolvals) );
227 
228  /* create new solution for the original problem */
229  SCIP_CALL( SCIPcreateSol(scip, &newsol, heur) );
230  SCIP_CALL( SCIPsetSolVals(scip, newsol, nvars, vars, subsolvals) );
231 
232  *success = FALSE;
233  /* solve an LP with all integer variables fixed to improve solution quality */
234  if( ncontvars > 0 && usefinallp && SCIPisLPConstructed(scip) )
235  {
236  int v;
237  int ncontobjvars; /* does the problem instance have continuous variables with nonzero objective coefficients? */
238  SCIP_Real sumofobjsquares;
239 
240  /* check if continuous variables with nonzero objective coefficient are present */
241  ncontobjvars = 0;
242  sumofobjsquares = 0.0;
243  for( v = nvars - 1; v >= nvars - ncontvars; --v )
244  {
245  SCIP_VAR* var;
246 
247  var = vars[v];
248  assert(vars[v] != NULL);
249  assert(!SCIPvarIsIntegral(var));
250 
251  if( SCIPvarGetStatus(var) == SCIP_VARSTATUS_COLUMN && !SCIPisZero(scip, SCIPvarGetObj(var)) )
252  {
253  ++ncontobjvars;
254  sumofobjsquares += SCIPvarGetObj(var) * SCIPvarGetObj(var);
255  }
256  }
257 
258  SCIPstatisticMessage(" Continuous Objective variables: %d, Euclidean OBJ: %g total, %g continuous\n", ncontobjvars, SCIPgetObjNorm(scip), sumofobjsquares);
259  /* solve a final LP to optimize solution values of continuous problem variables */
260  SCIPstatisticMessage("Solution Value before LP resolve: %g\n", SCIPgetSolOrigObj(scip, newsol));
261  SCIP_CALL( solveLp(scip, newsol, success) );
262 
263  /* if the LP solve was not successful, reset the solution */
264  if( !*success )
265  {
266  for( v = nvars - 1; v >= nvars - ncontvars; --v )
267  {
268  SCIP_CALL( SCIPsetSolVal(scip, newsol, vars[v], subsolvals[v]) );
269  }
270 
271  }
272  }
273 
274  /* try to add new solution to SCIP and free it immediately */
275  if( !*success )
276  {
277  SCIP_CALL( SCIPtrySol(scip, newsol, FALSE, FALSE, TRUE, TRUE, TRUE, success) );
278  }
279  SCIP_CALL( SCIPfreeSol(scip, &newsol) );
280 
281  SCIPfreeBufferArray(scip, &subsolvals);
282 
283  return SCIP_OKAY;
284 }
285 
286 /** sets solving parameters for the subproblem created by the heuristic */
287 static
289  SCIP_HEURDATA* heurdata, /**< heuristic data structure */
290  SCIP* subscip /**< copied SCIP data structure */
291  )
292 {
293  assert(subscip != NULL);
294 
295  /* do not abort subproblem on CTRL-C */
296  SCIP_CALL( SCIPsetBoolParam(subscip, "misc/catchctrlc", FALSE) );
297 
298 #ifdef SCIP_DEBUG
299  /* for debugging, enable full output */
300  SCIP_CALL( SCIPsetIntParam(subscip, "display/verblevel", 5) );
301  SCIP_CALL( SCIPsetIntParam(subscip, "display/freq", 100000000) );
302 #else
303  /* disable statistic timing inside sub SCIP and output to console */
304  SCIP_CALL( SCIPsetIntParam(subscip, "display/verblevel", 0) );
305  SCIP_CALL( SCIPsetBoolParam(subscip, "timing/statistictiming", FALSE) );
306 #endif
307 
308  /* forbid recursive call of heuristics and separators solving sub-SCIPs */
309  SCIP_CALL( SCIPsetSubscipsOff(subscip, TRUE) );
310 
311  /* use restart dfs node selection */
312  if( SCIPfindNodesel(subscip, "restartdfs") != NULL && !SCIPisParamFixed(subscip, "nodeselection/restartdfs/stdpriority") )
313  {
314  SCIP_CALL( SCIPsetIntParam(subscip, "nodeselection/restartdfs/stdpriority", INT_MAX/4) );
315  }
316 
317  /* activate uct node selection at the top of the tree */
318  if( heurdata->useuct && SCIPfindNodesel(subscip, "uct") != NULL && !SCIPisParamFixed(subscip, "nodeselection/uct/stdpriority") )
319  {
320  SCIP_CALL( SCIPsetIntParam(subscip, "nodeselection/uct/stdpriority", INT_MAX/2) );
321  }
322 
323  /* disable expensive presolving
324  * todo maybe presolving can be entirely turned off here - parameter???
325  */
327 
328  /* SCIP_CALL( SCIPsetPresolving(scip, SCIP_PARAMSETTING_OFF, TRUE) ); */
329  if( !SCIPisParamFixed(subscip, "presolving/maxrounds") )
330  {
331  SCIP_CALL( SCIPsetIntParam(subscip, "presolving/maxrounds", 50) );
332  }
333 
334  /* disable cutting plane separation */
336 
337 
338  /* todo: check branching rule in sub-SCIP */
339  if( SCIPfindBranchrule(subscip, "inference") != NULL && !SCIPisParamFixed(subscip, "branching/inference/priority") )
340  {
341  SCIP_CALL( SCIPsetIntParam(subscip, "branching/inference/priority", INT_MAX/4) );
342  }
343 
344  /* disable feasibility pump and fractional diving */
345  if( !SCIPisParamFixed(subscip, "heuristics/feaspump/freq") )
346  {
347  SCIP_CALL( SCIPsetIntParam(subscip, "heuristics/feaspump/freq", -1) );
348  }
349  if( !SCIPisParamFixed(subscip, "heuristics/fracdiving/freq") )
350  {
351  SCIP_CALL( SCIPsetIntParam(subscip, "heuristics/fracdiving/freq", -1) );
352  }
353 
354  /* employ a limit on the number of enforcement rounds in the quadratic constraint handler; this fixes the issue that
355  * sometimes the quadratic constraint handler needs hundreds or thousands of enforcement rounds to determine the
356  * feasibility status of a single node without fractional branching candidates by separation (namely for uflquad
357  * instances); however, the solution status of the sub-SCIP might get corrupted by this; hence no deductions shall be
358  * made for the original SCIP
359  */
360  if( SCIPfindConshdlr(subscip, "quadratic") != NULL && !SCIPisParamFixed(subscip, "constraints/quadratic/enfolplimit") )
361  {
362  SCIP_CALL( SCIPsetIntParam(subscip, "constraints/quadratic/enfolplimit", 500) );
363  }
364 
365  /* todo check if
366  * SCIP_CALL( SCIPsetEmphasis(subscip, SCIP_PARAMEMPHASIS_FEASIBILITY, TRUE) );
367  * improves performance */
368 
369  return SCIP_OKAY;
370 }
371 
372 /** frees the subproblem */
373 static
375  SCIP* scip, /**< SCIP data structure */
376  SCIP_HEURDATA* heurdata /**< heuristic data */
377  )
378 {
379  /* free remaining memory from heuristic execution */
380  if( heurdata->subscip != NULL )
381  {
382 
383  assert(heurdata->varmapfw != NULL);
384  assert(heurdata->subvars != NULL);
385  assert(heurdata->objcons != NULL);
386 
387  SCIPdebugMsg(scip, "Freeing subproblem of proximity heuristic\n");
388  SCIPfreeBlockMemoryArray(scip, &heurdata->subvars, heurdata->nsubvars);
389  SCIPhashmapFree(&heurdata->varmapfw);
390  SCIP_CALL( SCIPreleaseCons(heurdata->subscip, &heurdata->objcons) );
391  SCIP_CALL( SCIPfree(&heurdata->subscip) );
392 
393  heurdata->subscip = NULL;
394  heurdata->varmapfw = NULL;
395  heurdata->subvars = NULL;
396  heurdata->objcons = NULL;
397  }
398  return SCIP_OKAY;
399 }
400 
401 /* ---------------- Callback methods of event handler ---------------- */
402 
403 /* exec the event handler
404  *
405  * we interrupt the solution process
406  */
407 static
408 SCIP_DECL_EVENTEXEC(eventExecProximity)
409 {
410  SCIP_HEURDATA* heurdata;
411 
412  assert(eventhdlr != NULL);
413  assert(eventdata != NULL);
414  assert(strcmp(SCIPeventhdlrGetName(eventhdlr), EVENTHDLR_NAME) == 0);
415  assert(event != NULL);
417 
418  heurdata = (SCIP_HEURDATA*)eventdata;
419  assert(heurdata != NULL);
420 
421  /* interrupt solution process of sub-SCIP
422  * todo adjust interruption limit */
423  if( SCIPgetLPSolstat(scip) == SCIP_LPSOLSTAT_ITERLIMIT || SCIPgetNLPIterations(scip) >= heurdata->maxlpiters )
424  {
426  }
427 
428  return SCIP_OKAY;
429 }
430 /* ---------------- Callback methods of primal heuristic ---------------- */
431 
432 /** copy method for primal heuristic plugins (called when SCIP copies plugins) */
433 static
434 SCIP_DECL_HEURCOPY(heurCopyProximity)
435 { /*lint --e{715}*/
436  assert(scip != NULL);
437  assert(heur != NULL);
438  assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0);
439 
440  /* call inclusion method of primal heuristic */
442 
443  return SCIP_OKAY;
444 }
445 
446 /** destructor of primal heuristic to free user data (called when SCIP is exiting) */
447 static
448 SCIP_DECL_HEURFREE(heurFreeProximity)
449 { /*lint --e{715}*/
450  SCIP_HEURDATA* heurdata;
451 
452  assert( heur != NULL );
453  assert( scip != NULL );
454 
455  /* get heuristic data */
456  heurdata = SCIPheurGetData(heur);
457  assert( heurdata != NULL );
458 
459  /* free heuristic data */
460  SCIPfreeBlockMemory(scip, &heurdata);
461  SCIPheurSetData(heur, NULL);
462 
463  return SCIP_OKAY;
464 }
465 
466 
467 /** initialization method of primal heuristic (called after problem was transformed) */
468 static
469 SCIP_DECL_HEURINIT(heurInitProximity)
470 { /*lint --e{715}*/
471  SCIP_HEURDATA* heurdata;
472 
473  assert( heur != NULL );
474  assert( scip != NULL );
475 
476  /* get heuristic data */
477  heurdata = SCIPheurGetData(heur);
478  assert( heurdata != NULL );
479 
480  /* initialize data */
481  heurdata->usednodes = 0LL;
482  heurdata->lastsolidx = -1;
483  heurdata->nusedlpiters = 0LL;
484  heurdata->subprobidx = 0;
485 
486  heurdata->subscip = NULL;
487  heurdata->varmapfw = NULL;
488  heurdata->subvars = NULL;
489  heurdata->objcons = NULL;
490 
491  heurdata->nsubvars = 0;
492 
493  return SCIP_OKAY;
494 }
495 
496 /* solution process exiting method of proximity heuristic */
497 static
498 SCIP_DECL_HEUREXITSOL(heurExitsolProximity)
499 {
500  SCIP_HEURDATA* heurdata;
501 
502  assert( heur != NULL );
503  assert( scip != NULL );
504 
505  /* get heuristic data */
506  heurdata = SCIPheurGetData(heur);
507  assert( heurdata != NULL );
508 
509  SCIP_CALL( deleteSubproblem(scip, heurdata) );
510 
511  assert(heurdata->subscip == NULL && heurdata->varmapfw == NULL
512  && heurdata->subvars == NULL && heurdata->objcons == NULL);
513 
514  return SCIP_OKAY;
515 }
516 
517 /** execution method of primal heuristic */
518 static
519 SCIP_DECL_HEUREXEC(heurExecProximity)
520 { /*lint --e{715}*/
521 
522  SCIP_HEURDATA* heurdata; /* heuristic's data */
523  SCIP_Longint nnodes; /* number of stalling nodes for the subproblem */
524  SCIP_Longint nlpiters; /* lp iteration limit for the subproblem */
525  SCIP_Bool foundsol;
526 
527  assert(heur != NULL);
528  assert(scip != NULL);
529  assert(result != NULL);
530 
531  *result = SCIP_DIDNOTRUN;
532 
533  /* get heuristic data */
534  heurdata = SCIPheurGetData(heur);
535  assert(heurdata != NULL);
536 
537  /* do not run heuristic when there are only few binary varables */
538  if( SCIPgetNBinVars(scip) < heurdata->binvarquot * SCIPgetNVars(scip) )
539  return SCIP_OKAY;
540 
541  /* calculate branching node limit for sub problem */
542  /* todo maybe treat root node differently */
543  nnodes = (SCIP_Longint) (heurdata->nodesquot * SCIPgetNNodes(scip));
544  nnodes += heurdata->nodesofs;
545 
546  /* determine the node and LP iteration limit for the solve of the sub-SCIP */
547  nnodes -= heurdata->usednodes;
548  nnodes = MIN(nnodes, heurdata->maxnodes);
549 
550  nlpiters = (SCIP_Longint) heurdata->lpitersquot * SCIPgetNRootFirstLPIterations(scip);
551  nlpiters = MIN(nlpiters, heurdata->maxlpiters);
552 
553  /* check whether we have enough nodes left to call subproblem solving */
554  if( nnodes < heurdata->minnodes )
555  {
556  SCIPdebugMsg(scip, "skipping proximity: nnodes=%" SCIP_LONGINT_FORMAT ", minnodes=%" SCIP_LONGINT_FORMAT "\n", nnodes, heurdata->minnodes);
557  return SCIP_OKAY;
558  }
559 
560  /* do not run proximity, if the problem does not have an objective function anyway */
561  if( SCIPgetNObjVars(scip) == 0 )
562  {
563  SCIPdebugMsg(scip, "skipping proximity: pure feasibility problem anyway\n");
564  return SCIP_OKAY;
565  }
566 
567  foundsol = FALSE;
568 
569  do
570  {
571  /* main loop of proximity: in every iteration, a new subproblem is set up and solved until no improved solution
572  * is found or one of the heuristic limits on nodes or LP iterations is hit
573  * heuristic performs only one iteration if restart parameter is set to FALSE
574  */
575  SCIP_Longint nusednodes;
576  SCIP_Longint nusedlpiters;
577 
578  nusednodes = 0LL;
579  nusedlpiters = 0LL;
580 
581  nlpiters = MAX(nlpiters, heurdata->minlpiters);
582 
583  /* define and solve the proximity subproblem */
584  SCIP_CALL( SCIPapplyProximity(scip, heur, result, heurdata->minimprove, nnodes, nlpiters, &nusednodes, &nusedlpiters, FALSE) );
585 
586  /* adjust node limit and LP iteration limit for future iterations */
587  assert(nusednodes <= nnodes);
588  heurdata->usednodes += nusednodes;
589  nnodes -= nusednodes;
590 
591  nlpiters -= nusedlpiters;
592  heurdata->nusedlpiters += nusedlpiters;
593 
594  /* memorize if a new solution has been found in at least one iteration */
595  if( *result == SCIP_FOUNDSOL )
596  foundsol = TRUE;
597  }
598  while( *result == SCIP_FOUNDSOL && heurdata->restart && !SCIPisStopped(scip) && nnodes > 0 );
599 
600  /* reset result pointer if solution has been found in previous iteration */
601  if( foundsol )
602  *result = SCIP_FOUNDSOL;
603 
604  /* free the occupied memory */
605  if( heurdata->subscip != NULL )
606  {
607 /* just for testing the library method, in debug mode, we call the wrapper method for the actual delete method */
608 #ifndef NDEBUG
610 #else
611  SCIP_CALL( deleteSubproblem(scip, heurdata) );
612 #endif
613  }
614  return SCIP_OKAY;
615 }
616 
617 
618 /*
619  * primal heuristic specific interface methods
620  */
621 
622 /** frees the sub-MIP created by proximity */
624  SCIP* scip /** SCIP data structure */
625  )
626 {
627  SCIP_HEUR* heur;
628  SCIP_HEURDATA* heurdata;
629 
630  assert(scip != NULL);
631 
632  heur = SCIPfindHeur(scip, HEUR_NAME);
633  assert(heur != NULL);
634 
635  heurdata = SCIPheurGetData(heur);
636  if( heurdata != NULL )
637  {
638  SCIP_CALL( deleteSubproblem(scip, heurdata) );
639  }
640 
641  return SCIP_OKAY;
642 }
643 
644 /** main procedure of the proximity heuristic, creates and solves a sub-SCIP
645  *
646  * @note the method can be applied in an iterative way, keeping the same subscip in between. If the @p freesubscip
647  * parameter is set to FALSE, the heuristic will keep the subscip data structures. Always set this parameter
648  * to TRUE, or call SCIPdeleteSubproblemProximity() afterwards
649  */
651  SCIP* scip, /**< original SCIP data structure */
652  SCIP_HEUR* heur, /**< heuristic data structure */
653  SCIP_RESULT* result, /**< result data structure */
654  SCIP_Real minimprove, /**< factor by which proximity should at least improve the incumbent */
655  SCIP_Longint nnodes, /**< node limit for the subproblem */
656  SCIP_Longint nlpiters, /**< LP iteration limit for the subproblem */
657  SCIP_Longint* nusednodes, /**< pointer to store number of used nodes in subscip */
658  SCIP_Longint* nusedlpiters, /**< pointer to store number of used LP iterations in subscip */
659  SCIP_Bool freesubscip /**< should the created sub-MIP be freed at the end of the method? */
660  )
661 {
662  SCIP* subscip; /* the subproblem created by proximity */
663  SCIP_HASHMAP* varmapfw; /* mapping of SCIP variables to sub-SCIP variables */
664  SCIP_VAR** vars; /* original problem's variables */
665  SCIP_VAR** subvars; /* subproblem's variables */
666  SCIP_HEURDATA* heurdata; /* heuristic's private data structure */
667  SCIP_EVENTHDLR* eventhdlr; /* event handler for LP events */
668 
669  SCIP_SOL* incumbent;
670  SCIP_CONS* objcons;
671  SCIP_Longint iterlim;
672 
673  SCIP_Real large;
674  SCIP_Real inf;
675 
676  SCIP_Real bestobj;
677  SCIP_Real objcutoff;
678  SCIP_Real lowerbound;
679 
680  int nvars; /* number of original problem's variables */
681  int nfixedvars;
682  int nsubsols;
683  int solidx;
684  int i;
685 
686  SCIP_Bool valid;
687  SCIP_Bool success;
688 
689  assert(scip != NULL);
690  assert(heur != NULL);
691  assert(result != NULL);
692 
693  assert(nnodes >= 0);
694  assert(0.0 <= minimprove && minimprove <= 1.0);
695 
696  *result = SCIP_DIDNOTRUN;
697 
698  /* get heuristic data */
699  heurdata = SCIPheurGetData(heur);
700  assert(heurdata != NULL);
701 
702  /* only call the heuristic if we have an incumbent */
703  if( SCIPgetNSolsFound(scip) == 0 )
704  return SCIP_OKAY;
705 
706  /* do not use heuristic on problems without binary variables */
707  if( SCIPgetNBinVars(scip) == 0 )
708  return SCIP_OKAY;
709 
710  incumbent = SCIPgetBestSol(scip);
711  assert(incumbent != NULL);
712 
713  /* make sure that the incumbent is valid for the transformed space, otherwise terminate */
714  if( SCIPsolIsOriginal(incumbent) )
715  return SCIP_OKAY;
716 
717  solidx = SCIPsolGetIndex(incumbent);
718 
719  if( heurdata->lastsolidx == solidx )
720  return SCIP_OKAY;
721 
722  /* only call heuristic, if the best solution does not come from trivial heuristic */
723  if( SCIPsolGetHeur(incumbent) != NULL && strcmp(SCIPheurGetName(SCIPsolGetHeur(incumbent)), "trivial") == 0 )
724  return SCIP_OKAY;
725 
726  /* waitingnodes parameter defines the minimum number of nodes to wait before a new incumbent is processed */
727  if( SCIPgetNNodes(scip) > 1 && SCIPgetNNodes(scip) - SCIPsolGetNodenum(incumbent) < heurdata->waitingnodes )
728  return SCIP_OKAY;
729 
730  bestobj = SCIPgetSolTransObj(scip, incumbent);
731  lowerbound = SCIPgetLowerbound(scip);
732 
733  /* use knowledge about integrality of objective to round up lower bound */
734  if( SCIPisObjIntegral(scip) )
735  {
736  SCIPdebugMsg(scip, " Rounding up lower bound: %f --> %f \n", lowerbound, SCIPfeasCeil(scip, lowerbound));
737  lowerbound = SCIPfeasCeil(scip, lowerbound);
738  }
739 
740  /* do not trigger heuristic if primal and dual bound are already close together */
741  if( SCIPisFeasLE(scip, bestobj, lowerbound) || SCIPgetGap(scip) <= heurdata->mingap )
742  return SCIP_OKAY;
743 
744  /* calculate the minimum improvement for a heuristic solution in terms of the distance between incumbent objective
745  * and the lower bound
746  */
747  objcutoff = lowerbound + (1 - minimprove) * (bestobj - lowerbound);
748 
749  /* use integrality of the objective function to round down (and thus strengthen) the objective cutoff */
750  if( SCIPisObjIntegral(scip) )
751  objcutoff = SCIPfeasFloor(scip, objcutoff);
752 
753  if( SCIPisFeasLT(scip, objcutoff, lowerbound) )
754  objcutoff = lowerbound;
755 
756  /* exit execution if the right hand side of the objective constraint does not change (suggests that the heuristic
757  * was not successful in a previous iteration) */
758  if( heurdata->objcons != NULL && SCIPisFeasEQ(scip, SCIPgetRhsLinear(heurdata->subscip, heurdata->objcons), objcutoff) )
759  return SCIP_OKAY;
760 
761  /* check whether there is enough time and memory left */
762  SCIP_CALL( SCIPcheckCopyLimits(scip, &valid) );
763 
764  if( ! valid )
765  return SCIP_OKAY;
766 
767  *result = SCIP_DIDNOTFIND;
768 
769  heurdata->lastsolidx = solidx;
770 
771  /* get variable data */
772  SCIP_CALL( SCIPgetVarsData(scip, &vars, &nvars, NULL, NULL, NULL, NULL) );
773 
774  /* create a subscip and copy the original scip instance into it */
775  if( heurdata->subscip == NULL )
776  {
777  assert(heurdata->varmapfw == NULL);
778  assert(heurdata->objcons == NULL);
779 
780  /* initialize the subproblem */
781  SCIP_CALL( SCIPcreate(&subscip) );
782 
783  /* create the variable mapping hash map */
784  SCIP_CALL( SCIPhashmapCreate(&varmapfw, SCIPblkmem(subscip), nvars) );
785  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &subvars, nvars) );
786 
787  /* copy complete SCIP instance */
788  valid = FALSE;
789 
790  /* create a problem copy as sub SCIP */
791  SCIP_CALL( SCIPcopyLargeNeighborhoodSearch(scip, subscip, varmapfw, "dins", NULL, NULL, 0, heurdata->uselprows, TRUE,
792  &success, &valid) );
793 
794  SCIPdebugMsg(scip, "Copying the SCIP instance was %s complete.\n", valid ? "" : "not ");
795 
796  /* create event handler for LP events */
797  eventhdlr = NULL;
798  SCIP_CALL( SCIPincludeEventhdlrBasic(subscip, &eventhdlr, EVENTHDLR_NAME, EVENTHDLR_DESC, eventExecProximity, NULL) );
799  if( eventhdlr == NULL )
800  {
801  SCIPerrorMessage("event handler for " HEUR_NAME " heuristic not found.\n");
802  return SCIP_PLUGINNOTFOUND;
803  }
804 
805  /* set up parameters for the copied instance */
806  SCIP_CALL( setupSubproblem(heurdata, subscip) );
807 
808  /* create the objective constraint in the sub scip, first without variables and values which will be added later */
809  SCIP_CALL( SCIPcreateConsBasicLinear(subscip, &objcons, "objbound_of_origscip", 0, NULL, NULL, -SCIPinfinity(subscip), SCIPinfinity(subscip)) );
810 
811  /* determine large value to set variable bounds to, safe-guard to avoid fixings to infinite values */
812  large = SCIPinfinity(scip);
813  if( !SCIPisInfinity(scip, 0.1 / SCIPfeastol(scip)) )
814  large = 0.1 / SCIPfeastol(scip);
815  inf = SCIPinfinity(subscip);
816 
817  /* get variable image and change objective to proximity function (Manhattan distance) in sub-SCIP */
818  for( i = 0; i < nvars; i++ )
819  {
820  SCIP_Real adjustedbound;
821  SCIP_Real lb;
822  SCIP_Real ub;
823 
824  subvars[i] = (SCIP_VAR*) SCIPhashmapGetImage(varmapfw, vars[i]);
825 
826  SCIP_CALL( SCIPchgVarObj(subscip, subvars[i], 0.0) );
827 
828  lb = SCIPvarGetLbGlobal(subvars[i]);
829  ub = SCIPvarGetUbGlobal(subvars[i]);
830 
831  /* adjust infinite bounds in order to avoid that variables with non-zero objective
832  * get fixed to infinite value in proximity subproblem
833  */
834  if( SCIPisInfinity(subscip, ub ) )
835  {
836  adjustedbound = MAX(large, lb+large);
837  adjustedbound = MIN(adjustedbound, inf);
838  SCIP_CALL( SCIPchgVarUbGlobal(subscip, subvars[i], adjustedbound) );
839  }
840  if( SCIPisInfinity(subscip, -lb ) )
841  {
842  adjustedbound = MIN(-large, ub-large);
843  adjustedbound = MAX(adjustedbound, -inf);
844  SCIP_CALL( SCIPchgVarLbGlobal(subscip, subvars[i], adjustedbound) );
845  }
846 
847  /* add all nonzero objective coefficients to the objective constraint */
848  if( !SCIPisFeasZero(subscip, SCIPvarGetObj(vars[i])) )
849  {
850  SCIP_CALL( SCIPaddCoefLinear(subscip, objcons, subvars[i], SCIPvarGetObj(vars[i])) );
851  }
852  }
853 
854  /* add objective constraint to the subscip */
855  SCIP_CALL( SCIPaddCons(subscip, objcons) );
856  }
857  else
858  {
859  /* the instance, event handler, hash map and variable array were already copied in a previous iteration
860  * and stored in heuristic data
861  */
862  assert(heurdata->varmapfw != NULL);
863  assert(heurdata->subvars != NULL);
864  assert(heurdata->objcons != NULL);
865 
866  subscip = heurdata->subscip;
867  varmapfw = heurdata->varmapfw;
868  subvars = heurdata->subvars;
869  objcons = heurdata->objcons;
870 
871  eventhdlr = SCIPfindEventhdlr(subscip, EVENTHDLR_NAME);
872  assert(eventhdlr != NULL);
873  }
874 
875  SCIP_CALL( SCIPchgRhsLinear(subscip, objcons, objcutoff) );
876 
877  for( i = 0; i < SCIPgetNBinVars(scip); ++i )
878  {
879  SCIP_Real solval;
880 
881  /* objective coefficients are only set for binary variables of the problem */
882  assert(SCIPvarIsBinary(subvars[i]));
883 
884  solval = SCIPgetSolVal(scip, incumbent, vars[i]);
885  assert(SCIPisFeasEQ(scip, solval, 1.0) || SCIPisFeasEQ(scip, solval, 0.0));
886 
887  if( solval < 0.5 )
888  {
889  SCIP_CALL( SCIPchgVarObj(subscip, subvars[i], 1.0) );
890  }
891  else
892  {
893  SCIP_CALL( SCIPchgVarObj(subscip, subvars[i], -1.0) );
894  }
895  }
896 
897  /* set limits for the subproblem */
898  SCIP_CALL( SCIPcopyLimits(scip, subscip) );
899  SCIP_CALL( SCIPsetLongintParam(subscip, "limits/nodes", nnodes) );
900  SCIP_CALL( SCIPsetIntParam(subscip, "limits/solutions", 1) );
901 
902  /* restrict LP iterations */
903  /*todo set iterations limit depending on the number of iterations of the original problem root */
904  iterlim = nlpiters;
905  SCIP_CALL( SCIPsetLongintParam(subscip, "lp/iterlim", MAX(1, iterlim / MIN(10, nnodes))) );
906  SCIP_CALL( SCIPsetLongintParam(subscip, "lp/rootiterlim", iterlim) );
907 
908  /* catch LP events of sub-SCIP */
909  SCIP_CALL( SCIPtransformProb(subscip) );
910  SCIP_CALL( SCIPcatchEvent(subscip, SCIP_EVENTTYPE_NODESOLVED, eventhdlr, (SCIP_EVENTDATA*) heurdata, NULL) );
911 
912  SCIPstatisticMessage("solving subproblem at Node: %" SCIP_LONGINT_FORMAT " "
913  "nnodes: %" SCIP_LONGINT_FORMAT " "
914  "iterlim: %" SCIP_LONGINT_FORMAT "\n", SCIPgetNNodes(scip), nnodes, iterlim);
915 
916  /* solve the subproblem with all previously adjusted parameters */
917  nfixedvars = SCIPgetNFixedVars(subscip);
918 
919  SCIP_CALL( SCIPpresolve(subscip) );
920 
921  nfixedvars = SCIPgetNFixedVars(subscip) - nfixedvars;
922  assert(nfixedvars >= 0);
923  SCIPstatisticMessage("presolve fixings %d: %d\n", ++(heurdata->subprobidx), nfixedvars);
924 
925  /* errors in solving the subproblem should not kill the overall solving process;
926  * hence, the return code is caught and a warning is printed, only in debug mode, SCIP will stop.
927  */
928  SCIP_CALL_ABORT( SCIPsolve(subscip) );
929 
930  /* print solving statistics of subproblem if we are in SCIP's debug mode */
932  SCIPstatisticMessage("solve of subscip %d:"
933  "usednodes: %" SCIP_LONGINT_FORMAT " "
934  "lp iters: %" SCIP_LONGINT_FORMAT " "
935  "root iters: %" SCIP_LONGINT_FORMAT " "
936  "Presolving Time: %.2f\n", heurdata->subprobidx,
938 
939  SCIPstatisticMessage("Solving Time %d: %.2f\n", heurdata->subprobidx, SCIPgetSolvingTime(subscip) );
940 
941  /* drop LP events of sub-SCIP */
942  SCIP_CALL( SCIPdropEvent(subscip, SCIP_EVENTTYPE_NODESOLVED, eventhdlr, (SCIP_EVENTDATA*) heurdata, -1) );
943 
944  /* keep track of relevant information for future runs of heuristic */
945  if( nusednodes != NULL )
946  *nusednodes = SCIPgetNNodes(subscip);
947  if( nusedlpiters != NULL )
948  *nusedlpiters = SCIPgetNLPIterations(subscip);
949 
950  /* check whether a solution was found */
951  nsubsols = SCIPgetNSols(subscip);
952  incumbent = SCIPgetBestSol(subscip);
953  assert(nsubsols == 0 || incumbent != NULL);
954 
955  SCIPstatisticMessage("primal bound before subproblem %d: %g\n", heurdata->subprobidx, SCIPgetPrimalbound(scip));
956  if( nsubsols > 0 )
957  {
958  /* try to translate the sub problem solution to the original scip instance */
959  success = FALSE;
960  SCIP_CALL( createNewSol(scip, subscip, subvars, heur, incumbent, heurdata->usefinallp, &success) );
961 
962  if( success )
963  *result = SCIP_FOUNDSOL;
964  }
965  SCIPstatisticMessage("primal bound after subproblem %d: %g\n", heurdata->subprobidx, SCIPgetPrimalbound(scip));
966 
967  /* free the transformed subproblem data */
968  SCIP_CALL( SCIPfreeTransform(subscip) );
969 
970  /* save subproblem in heuristic data for subsequent runs if it has been successful, otherwise free subproblem */
971  heurdata->subscip = subscip;
972  heurdata->varmapfw = varmapfw;
973  heurdata->subvars = subvars;
974  heurdata->objcons = objcons;
975  heurdata->nsubvars = nvars;
976 
977  /* delete the sub problem */
978  if( freesubscip )
979  {
980  SCIP_CALL( deleteSubproblem(scip, heurdata) );
981  }
982 
983  return SCIP_OKAY;
984 }
985 
986 
987 /** creates the proximity primal heuristic and includes it in SCIP */
989  SCIP* scip /**< SCIP data structure */
990  )
991 {
992  SCIP_HEURDATA* heurdata;
993  SCIP_HEUR* heur;
994 
995  /* create heuristic data */
996  SCIP_CALL( SCIPallocBlockMemory(scip, &heurdata) );
997 
998  /* include primal heuristic */
999  heur = NULL;
1000  SCIP_CALL( SCIPincludeHeurBasic(scip, &heur,
1002  HEUR_MAXDEPTH, HEUR_TIMING, HEUR_USESSUBSCIP, heurExecProximity, heurdata) );
1003  assert(heur != NULL);
1004 
1005  /* set non-NULL pointers to callback methods */
1006  SCIP_CALL( SCIPsetHeurCopy(scip, heur, heurCopyProximity) );
1007  SCIP_CALL( SCIPsetHeurFree(scip, heur, heurFreeProximity) );
1008  SCIP_CALL( SCIPsetHeurInit(scip, heur, heurInitProximity) );
1009  SCIP_CALL( SCIPsetHeurExitsol(scip, heur, heurExitsolProximity) );
1010 
1011  /* add proximity primal heuristic parameters */
1012  SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/uselprows", "should subproblem be constructed based on LP row information?",
1013  &heurdata->uselprows, TRUE, DEFAULT_USELPROWS, NULL, NULL) );
1014 
1015  SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/restart", "should the heuristic immediately run again on its newly found solution?",
1016  &heurdata->restart, TRUE, DEFAULT_RESTART, NULL, NULL) );
1017 
1018  SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/usefinallp", "should the heuristic solve a final LP in case of continuous objective variables?",
1019  &heurdata->usefinallp, TRUE, DEFAULT_USEFINALLP, NULL, NULL) );
1020 
1021  SCIP_CALL( SCIPaddLongintParam(scip, "heuristics/" HEUR_NAME "/maxnodes",
1022  "maximum number of nodes to regard in the subproblem",
1023  &heurdata->maxnodes, TRUE,DEFAULT_MAXNODES, 0LL, SCIP_LONGINT_MAX, NULL, NULL) );
1024 
1025  SCIP_CALL( SCIPaddLongintParam(scip, "heuristics/" HEUR_NAME "/nodesofs",
1026  "number of nodes added to the contingent of the total nodes",
1027  &heurdata->nodesofs, TRUE, DEFAULT_NODESOFS, 0LL, SCIP_LONGINT_MAX, NULL, NULL) );
1028 
1029  SCIP_CALL( SCIPaddLongintParam(scip, "heuristics/" HEUR_NAME "/minnodes",
1030  "minimum number of nodes required to start the subproblem",
1031  &heurdata->minnodes, TRUE, DEFAULT_MINNODES, 0LL, SCIP_LONGINT_MAX, NULL, NULL) );
1032 
1033  SCIP_CALL( SCIPaddLongintParam(scip, "heuristics/" HEUR_NAME "/maxlpiters",
1034  "maximum number of LP iterations to be performed in the subproblem",
1035  &heurdata->maxlpiters, TRUE, DEFAULT_MAXLPITERS, -1LL, SCIP_LONGINT_MAX, NULL, NULL) );
1036 
1037  SCIP_CALL( SCIPaddLongintParam(scip, "heuristics/" HEUR_NAME "/minlpiters", "minimum number of LP iterations performed in "
1038  "subproblem", &heurdata->minlpiters, TRUE, DEFAULT_MINLPITERS, 0LL, SCIP_LONGINT_MAX, NULL, NULL) );
1039 
1040  SCIP_CALL( SCIPaddLongintParam(scip, "heuristics/" HEUR_NAME "/waitingnodes",
1041  "waiting nodes since last incumbent before heuristic is executed", &heurdata->waitingnodes, TRUE, DEFAULT_WAITINGNODES,
1042  0LL, SCIP_LONGINT_MAX, NULL, NULL) );
1043 
1044  SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/minimprove",
1045  "factor by which proximity should at least improve the incumbent",
1046  &heurdata->minimprove, TRUE, DEFAULT_MINIMPROVE, 0.0, 1.0, NULL, NULL) );
1047 
1048  SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/nodesquot", "sub-MIP node limit w.r.t number of original nodes",
1049  &heurdata->nodesquot, TRUE, DEFAULT_NODESQUOT, 0.0, SCIPinfinity(scip), NULL, NULL) );
1050 
1051  SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/binvarquot",
1052  "threshold for percentage of binary variables required to start",
1053  &heurdata->binvarquot, TRUE, DEFAULT_BINVARQUOT, 0.0, 1.0, NULL, NULL) );
1054 
1055  SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/lpitersquot",
1056  "quotient of sub-MIP LP iterations with respect to LP iterations so far",
1057  &heurdata->lpitersquot, TRUE, DEFAULT_LPITERSQUOT, 0.0, 1.0, NULL, NULL) );
1058 
1059  SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/mingap",
1060  "minimum primal-dual gap for which the heuristic is executed",
1061  &heurdata->mingap, TRUE, DEFAULT_MINGAP, 0.0, SCIPinfinity(scip), NULL, NULL) );
1062 
1063  SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/useuct",
1064  "should uct node selection be used at the beginning of the search?",
1065  &heurdata->useuct, TRUE, DEFAULT_USEUCT, NULL, NULL) );
1066 
1067 
1068  return SCIP_OKAY;
1069 }
enum SCIP_Result SCIP_RESULT
Definition: type_result.h:52
SCIP_Bool SCIPsolIsOriginal(SCIP_SOL *sol)
Definition: sol.c:2299
SCIP_RETCODE SCIPsetHeurExitsol(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEUREXITSOL((*heurexitsol)))
Definition: scip.c:8124
#define SCIPfreeBlockMemoryArray(scip, ptr, num)
Definition: scip.h:21909
SCIP_Bool SCIPisFeasZero(SCIP *scip, SCIP_Real val)
Definition: scip.c:46151
#define DEFAULT_USELPROWS
SCIP_RETCODE SCIPchgVarLbGlobal(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound)
Definition: scip.c:21877
SCIP_RETCODE SCIPlinkLPSol(SCIP *scip, SCIP_SOL *sol)
Definition: scip.c:37672
SCIP_Real SCIPgetSolvingTime(SCIP *scip)
Definition: scip.c:45137
SCIP_Longint SCIPgetNRootLPIterations(SCIP *scip)
Definition: scip.c:41426
SCIP_RETCODE SCIPsetSeparating(SCIP *scip, SCIP_PARAMSETTING paramsetting, SCIP_Bool quiet)
Definition: scip.c:5095
SCIP_Real SCIPfeastol(SCIP *scip)
Definition: scip.c:45274
#define SCIPallocBlockMemoryArray(scip, ptr, num)
Definition: scip.h:21892
SCIP_Bool SCIPisNLPConstructed(SCIP *scip)
Definition: scip.c:30835
#define DEFAULT_MINIMPROVE
SCIP_Bool SCIPisFeasEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip.c:46086
SCIP_Longint SCIPgetNLPIterations(SCIP *scip)
Definition: scip.c:41382
SCIP_RETCODE SCIPcreateConsBasicLinear(SCIP *scip, SCIP_CONS **cons, const char *name, int nvars, SCIP_VAR **vars, SCIP_Real *vals, SCIP_Real lhs, SCIP_Real rhs)
SCIP_Bool SCIPisFeasLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip.c:46099
SCIP_CONSHDLR * SCIPfindConshdlr(SCIP *scip, const char *name)
Definition: scip.c:6541
SCIP_RETCODE SCIPincludeHeurProximity(SCIP *scip)
SCIP_Real SCIPgetPrimalbound(SCIP *scip)
Definition: scip.c:42448
SCIP_Real SCIPvarGetLbGlobal(SCIP_VAR *var)
Definition: var.c:17166
static SCIP_DECL_EVENTEXEC(eventExecProximity)
#define EVENTHDLR_DESC
static SCIP_DECL_HEURCOPY(heurCopyProximity)
SCIP_Longint SCIPgetNSolsFound(SCIP *scip)
Definition: scip.c:42664
static SCIP_RETCODE solveLp(SCIP *scip, SCIP_SOL *sol, SCIP_Bool *success)
int SCIPgetNOrigVars(SCIP *scip)
Definition: scip.c:12071
SCIP_RETCODE SCIPincludeEventhdlrBasic(SCIP *scip, SCIP_EVENTHDLR **eventhdlrptr, const char *name, const char *desc, SCIP_DECL_EVENTEXEC((*eventexec)), SCIP_EVENTHDLRDATA *eventhdlrdata)
Definition: scip.c:8526
SCIP_Bool SCIPvarIsBinary(SCIP_VAR *var)
Definition: var.c:16732
static SCIP_DECL_HEURINIT(heurInitProximity)
#define DEFAULT_BINVARQUOT
SCIP_RETCODE SCIPgetVarsData(SCIP *scip, SCIP_VAR ***vars, int *nvars, int *nbinvars, int *nintvars, int *nimplvars, int *ncontvars)
Definition: scip.c:11505
static SCIP_RETCODE deleteSubproblem(SCIP *scip, SCIP_HEURDATA *heurdata)
#define FALSE
Definition: def.h:64
SCIP_RETCODE SCIPhashmapCreate(SCIP_HASHMAP **hashmap, BMS_BLKMEM *blkmem, int mapsize)
Definition: misc.c:2765
const char * SCIPeventhdlrGetName(SCIP_EVENTHDLR *eventhdlr)
Definition: event.c:278
#define HEUR_MAXDEPTH
SCIP_RETCODE SCIPaddLongintParam(SCIP *scip, const char *name, const char *desc, SCIP_Longint *valueptr, SCIP_Bool isadvanced, SCIP_Longint defaultvalue, SCIP_Longint minvalue, SCIP_Longint maxvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition: scip.c:4230
SCIP_RETCODE SCIPcopyLimits(SCIP *sourcescip, SCIP *targetscip)
Definition: scip.c:4126
#define DEFAULT_USEFINALLP
SCIP_Real SCIPinfinity(SCIP *scip)
Definition: scip.c:45816
#define TRUE
Definition: def.h:63
#define SCIPdebug(x)
Definition: pub_message.h:74
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:53
#define SCIPstatisticMessage
Definition: pub_message.h:104
SCIP_RETCODE SCIPsetPresolving(SCIP *scip, SCIP_PARAMSETTING paramsetting, SCIP_Bool quiet)
Definition: scip.c:5069
SCIP_BRANCHRULE * SCIPfindBranchrule(SCIP *scip, const char *name)
Definition: scip.c:9184
SCIP_RETCODE SCIPchgVarLbDive(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound)
Definition: scip.c:34642
SCIP_Longint SCIPgetNRootFirstLPIterations(SCIP *scip)
Definition: scip.c:41445
struct SCIP_HeurData SCIP_HEURDATA
Definition: type_heur.h:51
#define SCIPfreeBlockMemory(scip, ptr)
Definition: scip.h:21907
SCIP_RETCODE SCIPincludeHeurBasic(SCIP *scip, SCIP_HEUR **heur, const char *name, const char *desc, char dispchar, int priority, int freq, int freqofs, int maxdepth, SCIP_HEURTIMING timingmask, SCIP_Bool usessubscip, SCIP_DECL_HEUREXEC((*heurexec)), SCIP_HEURDATA *heurdata)
Definition: scip.c:7999
SCIP_EVENTHDLR * SCIPfindEventhdlr(SCIP *scip, const char *name)
Definition: scip.c:8656
#define HEUR_FREQ
void * SCIPhashmapGetImage(SCIP_HASHMAP *hashmap, void *origin)
Definition: misc.c:2903
#define SCIP_LONGINT_MAX
Definition: def.h:121
#define SCIPfreeBufferArray(scip, ptr)
Definition: scip.h:21937
SCIP_RETCODE SCIPcreate(SCIP **scip)
Definition: scip.c:696
void SCIPheurSetData(SCIP_HEUR *heur, SCIP_HEURDATA *heurdata)
Definition: heur.c:1102
#define SCIPallocBlockMemory(scip, ptr)
Definition: scip.h:21890
void SCIPwarningMessage(SCIP *scip, const char *formatstr,...)
Definition: scip.c:1260
#define HEUR_PRIORITY
SCIP_RETCODE SCIPchgVarUbGlobal(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound)
Definition: scip.c:21964
#define SCIPdebugMsg
Definition: scip.h:451
SCIP_Real SCIPgetRhsLinear(SCIP *scip, SCIP_CONS *cons)
SCIP_Real SCIPgetPresolvingTime(SCIP *scip)
Definition: scip.c:45201
SCIP_RETCODE SCIPprintStatistics(SCIP *scip, FILE *file)
Definition: scip.c:44425
SCIP_RETCODE SCIPaddCoefLinear(SCIP *scip, SCIP_CONS *cons, SCIP_VAR *var, SCIP_Real val)
SCIP_Real SCIPgetObjNorm(SCIP *scip)
Definition: scip.c:11284
SCIP_Real SCIPfeasCeil(SCIP *scip, SCIP_Real val)
Definition: scip.c:46223
SCIP_Real SCIPfeasFloor(SCIP *scip, SCIP_Real val)
Definition: scip.c:46211
int SCIPgetNFixedVars(SCIP *scip)
Definition: scip.c:11948
SCIP_Bool SCIPisLPConstructed(SCIP *scip)
Definition: scip.c:28787
SCIP_Real SCIPvarGetUbGlobal(SCIP_VAR *var)
Definition: var.c:17176
#define HEUR_NAME
#define DEFAULT_MINLPITERS
SCIP_RETCODE SCIPsolve(SCIP *scip)
Definition: scip.c:15777
const char * SCIPheurGetName(SCIP_HEUR *heur)
Definition: heur.c:1181
SCIP_HEUR * SCIPfindHeur(SCIP *scip, const char *name)
Definition: scip.c:8140
#define DEFAULT_LPITERSQUOT
#define SCIPerrorMessage
Definition: pub_message.h:45
SCIP_Bool SCIPisParamFixed(SCIP *scip, const char *name)
Definition: scip.c:4338
SCIP_RETCODE SCIPdeleteSubproblemProximity(SCIP *scip)
SCIP_RETCODE SCIPaddCons(SCIP *scip, SCIP_CONS *cons)
Definition: scip.c:12410
#define HEUR_FREQOFS
SCIP_RETCODE SCIPsolveDiveLP(SCIP *scip, int itlim, SCIP_Bool *lperror, SCIP_Bool *cutoff)
Definition: scip.c:34901
SCIP_RETCODE SCIPsetHeurFree(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURFREE((*heurfree)))
Definition: scip.c:8060
#define HEUR_TIMING
SCIP_RETCODE SCIPgetSolVals(SCIP *scip, SCIP_SOL *sol, int nvars, SCIP_VAR **vars, SCIP_Real *vals)
Definition: scip.c:38044
SCIP_RETCODE SCIPsetBoolParam(SCIP *scip, const char *name, SCIP_Bool value)
Definition: scip.c:4567
SCIP_RETCODE SCIPpresolve(SCIP *scip)
Definition: scip.c:15616
BMS_BLKMEM * SCIPblkmem(SCIP *scip)
Definition: scip.c:45519
static SCIP_RETCODE createNewSol(SCIP *scip, SCIP *subscip, SCIP_VAR **subvars, SCIP_HEUR *heur, SCIP_SOL *subsol, SCIP_Bool usefinallp, SCIP_Bool *success)
struct SCIP_EventData SCIP_EVENTDATA
Definition: type_event.h:155
void SCIPhashmapFree(SCIP_HASHMAP **hashmap)
Definition: misc.c:2798
#define NULL
Definition: lpi_spx1.cpp:137
SCIP_HEUR * SCIPsolGetHeur(SCIP_SOL *sol)
Definition: sol.c:2382
SCIP_Real SCIPgetSolTransObj(SCIP *scip, SCIP_SOL *sol)
Definition: scip.c:38137
#define DEFAULT_MAXNODES
#define EVENTHDLR_NAME
#define SCIP_CALL(x)
Definition: def.h:306
SCIP_Real SCIPgetLowerbound(SCIP *scip)
Definition: scip.c:42323
static SCIP_DECL_HEUREXEC(heurExecProximity)
#define DEFAULT_NODESOFS
SCIP_Bool SCIPisFeasLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip.c:46112
#define DEFAULT_NODESQUOT
#define DEFAULT_USEUCT
SCIP_RETCODE SCIPchgVarObj(SCIP *scip, SCIP_VAR *var, SCIP_Real newobj)
Definition: scip.c:21448
#define SCIPallocBufferArray(scip, ptr, num)
Definition: scip.h:21925
SCIP_RETCODE SCIPsetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var, SCIP_Real val)
Definition: scip.c:37867
#define DEFAULT_MAXLPITERS
#define DEFAULT_MINGAP
SCIP_RETCODE SCIPfreeTransform(SCIP *scip)
Definition: scip.c:16873
#define SCIP_Bool
Definition: def.h:61
SCIP_RETCODE SCIPcatchEvent(SCIP *scip, SCIP_EVENTTYPE eventtype, SCIP_EVENTHDLR *eventhdlr, SCIP_EVENTDATA *eventdata, int *filterpos)
Definition: scip.c:40207
SCIP_LPSOLSTAT SCIPgetLPSolstat(SCIP *scip)
Definition: scip.c:28854
SCIP_EVENTTYPE SCIPeventGetType(SCIP_EVENT *event)
Definition: event.c:959
SCIP_Longint SCIPsolGetNodenum(SCIP_SOL *sol)
Definition: sol.c:2362
SCIP_Real SCIPgetGap(SCIP *scip)
Definition: scip.c:42581
SCIP_RETCODE SCIPchgVarUbDive(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound)
Definition: scip.c:34674
#define MAX(x, y)
Definition: tclique_def.h:75
SCIP_RETCODE SCIPsetIntParam(SCIP *scip, const char *name, int value)
Definition: scip.c:4625
SCIP_RETCODE SCIPdropEvent(SCIP *scip, SCIP_EVENTTYPE eventtype, SCIP_EVENTHDLR *eventhdlr, SCIP_EVENTDATA *eventdata, int filterpos)
Definition: scip.c:40241
SCIP_RETCODE SCIPfreeSol(SCIP *scip, SCIP_SOL **sol)
Definition: scip.c:37631
SCIP_Real SCIPvarGetObj(SCIP_VAR *var)
Definition: var.c:17014
int SCIPgetNSols(SCIP *scip)
Definition: scip.c:38832
#define DEFAULT_MINNODES
SCIP_Real SCIPgetSolOrigObj(SCIP *scip, SCIP_SOL *sol)
Definition: scip.c:38090
Constraint handler for linear constraints in their most general form, .
int SCIPgetNObjVars(SCIP *scip)
Definition: scip.c:11859
SCIP_RETCODE SCIPchgRhsLinear(SCIP *scip, SCIP_CONS *cons, SCIP_Real rhs)
SCIP_Bool SCIPisInfinity(SCIP *scip, SCIP_Real val)
Definition: scip.c:45827
SCIP_RETCODE SCIPtrySol(SCIP *scip, SCIP_SOL *sol, SCIP_Bool printreason, SCIP_Bool completely, SCIP_Bool checkbounds, SCIP_Bool checkintegrality, SCIP_Bool checklprows, SCIP_Bool *stored)
Definition: scip.c:39749
int SCIPgetNBinVars(SCIP *scip)
Definition: scip.c:11676
#define SCIP_EVENTTYPE_NODESOLVED
Definition: type_event.h:119
int SCIPgetNVars(SCIP *scip)
Definition: scip.c:11631
SCIP_Bool SCIPisObjIntegral(SCIP *scip)
Definition: scip.c:11205
#define HEUR_DESC
SCIP_SOL * SCIPgetBestSol(SCIP *scip)
Definition: scip.c:38931
#define DEFAULT_WAITINGNODES
static SCIP_DECL_HEURFREE(heurFreeProximity)
SCIP_RETCODE SCIPreleaseCons(SCIP *scip, SCIP_CONS **cons)
Definition: scip.c:27323
SCIP_RETCODE SCIPsetHeurInit(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURINIT((*heurinit)))
Definition: scip.c:8076
SCIP_NODESEL * SCIPfindNodesel(SCIP *scip, const char *name)
Definition: scip.c:8872
SCIP_RETCODE SCIPcopyLargeNeighborhoodSearch(SCIP *sourcescip, SCIP *subscip, SCIP_HASHMAP *varmap, const char *suffix, SCIP_VAR **fixedvars, SCIP_Real *fixedvals, int nfixedvars, SCIP_Bool uselprows, SCIP_Bool copycuts, SCIP_Bool *success, SCIP_Bool *valid)
Definition: heuristics.c:899
SCIP_VARSTATUS SCIPvarGetStatus(SCIP_VAR *var)
Definition: var.c:16671
#define SCIP_Real
Definition: def.h:135
SCIP_Bool SCIPisStopped(SCIP *scip)
Definition: scip.c:1138
#define MIN(x, y)
Definition: memory.c:75
static SCIP_DECL_HEUREXITSOL(heurExitsolProximity)
#define SCIP_Longint
Definition: def.h:120
SCIP_RETCODE SCIPcheckCopyLimits(SCIP *sourcescip, SCIP_Bool *success)
Definition: scip.c:4090
SCIP_RETCODE SCIPstartDive(SCIP *scip)
Definition: scip.c:34477
SCIP_RETCODE SCIPsetSolVals(SCIP *scip, SCIP_SOL *sol, int nvars, SCIP_VAR **vars, SCIP_Real *vals)
Definition: scip.c:37909
SCIP_RETCODE SCIPtransformProb(SCIP *scip)
Definition: scip.c:13668
SCIP_Bool SCIPisZero(SCIP *scip, SCIP_Real val)
Definition: scip.c:45864
SCIP_RETCODE SCIPsetHeurCopy(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURCOPY((*heurcopy)))
Definition: scip.c:8044
#define nnodes
Definition: gastrans.c:65
#define HEUR_DISPCHAR
SCIP_RETCODE SCIPinterruptSolve(SCIP *scip)
Definition: scip.c:16942
SCIP_RETCODE SCIPapplyProximity(SCIP *scip, SCIP_HEUR *heur, SCIP_RESULT *result, SCIP_Real minimprove, SCIP_Longint nnodes, SCIP_Longint nlpiters, SCIP_Longint *nusednodes, SCIP_Longint *nusedlpiters, SCIP_Bool freesubscip)
SCIP_RETCODE SCIPendDive(SCIP *scip)
Definition: scip.c:34520
#define SCIP_CALL_ABORT(x)
Definition: def.h:285
SCIP_HEURDATA * SCIPheurGetData(SCIP_HEUR *heur)
Definition: heur.c:1092
SCIP_Longint SCIPgetNNodes(SCIP *scip)
Definition: scip.c:41182
#define HEUR_USESSUBSCIP
SCIP_Bool SCIPvarIsIntegral(SCIP_VAR *var)
Definition: var.c:16743
SCIP_Real SCIPgetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var)
Definition: scip.c:38007
#define DEFAULT_RESTART
int SCIPsolGetIndex(SCIP_SOL *sol)
Definition: sol.c:2413
improvement heuristic which uses an auxiliary objective instead of the original objective function wh...
SCIP_RETCODE SCIPaddRealParam(SCIP *scip, const char *name, const char *desc, SCIP_Real *valueptr, SCIP_Bool isadvanced, SCIP_Real defaultvalue, SCIP_Real minvalue, SCIP_Real maxvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition: scip.c:4258
SCIP_RETCODE SCIPsetSubscipsOff(SCIP *scip, SCIP_Bool quiet)
Definition: scip.c:5020
SCIP_RETCODE SCIPsetLongintParam(SCIP *scip, const char *name, SCIP_Longint value)
Definition: scip.c:4683
SCIP_RETCODE SCIPaddBoolParam(SCIP *scip, const char *name, const char *desc, SCIP_Bool *valueptr, SCIP_Bool isadvanced, SCIP_Bool defaultvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition: scip.c:4176
static SCIP_RETCODE setupSubproblem(SCIP_HEURDATA *heurdata, SCIP *subscip)
SCIP_RETCODE SCIPfree(SCIP **scip)
Definition: scip.c:774
SCIP_RETCODE SCIPcreateSol(SCIP *scip, SCIP_SOL **sol, SCIP_HEUR *heur)
Definition: scip.c:37005