Scippy

SCIP

Solving Constraint Integer Programs

heur_rootsoldiving.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-2022 Konrad-Zuse-Zentrum */
7 /* fuer Informationstechnik Berlin */
8 /* */
9 /* SCIP is distributed under the terms of the ZIB Academic License. */
10 /* */
11 /* You should have received a copy of the ZIB Academic License */
12 /* along with SCIP; see the file COPYING. If not visit scipopt.org. */
13 /* */
14 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
15 
16 /**@file heur_rootsoldiving.c
17  * @ingroup DEFPLUGINS_HEUR
18  * @brief LP diving heuristic that changes variable's objective values using root LP solution as guide
19  * @author Kati Wolter
20  */
21 
22 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
23 
24 #include "blockmemshell/memory.h"
26 #include "scip/pub_heur.h"
27 #include "scip/pub_message.h"
28 #include "scip/pub_var.h"
29 #include "scip/scip_branch.h"
30 #include "scip/scip_general.h"
31 #include "scip/scip_heur.h"
32 #include "scip/scip_lp.h"
33 #include "scip/scip_mem.h"
34 #include "scip/scip_message.h"
35 #include "scip/scip_numerics.h"
36 #include "scip/scip_param.h"
37 #include "scip/scip_prob.h"
38 #include "scip/scip_sol.h"
39 #include "scip/scip_solvingstats.h"
40 #include "scip/scip_tree.h"
41 #include <string.h>
42 
43 #define HEUR_NAME "rootsoldiving"
44 #define HEUR_DESC "LP diving heuristic that changes variable's objective values using root LP solution as guide"
45 #define HEUR_DISPCHAR SCIP_HEURDISPCHAR_OBJDIVING
46 #define HEUR_PRIORITY -1005000
47 #define HEUR_FREQ 20
48 #define HEUR_FREQOFS 5
49 #define HEUR_MAXDEPTH -1
50 #define HEUR_TIMING SCIP_HEURTIMING_AFTERLPPLUNGE
51 #define HEUR_USESSUBSCIP FALSE /**< does the heuristic use a secondary SCIP instance? */
52 
53 
54 /*
55  * Default parameter settings
56  */
57 
58 #define DEFAULT_MINRELDEPTH 0.0 /**< minimal relative depth to start diving */
59 #define DEFAULT_MAXRELDEPTH 1.0 /**< maximal relative depth to start diving */
60 #define DEFAULT_MAXLPITERQUOT 0.01 /**< maximal fraction of diving LP iterations compared to node LP iterations */
61 #define DEFAULT_MAXLPITEROFS 1000 /**< additional number of allowed LP iterations */
62 #define DEFAULT_MAXSOLS -1 /**< total number of feasible solutions found up to which heuristic is called
63  * (-1: no limit) */
64 #define DEFAULT_DEPTHFAC 0.5 /**< maximal diving depth: number of binary/integer variables times depthfac */
65 #define DEFAULT_DEPTHFACNOSOL 2.0 /**< maximal diving depth factor if no feasible solution was found yet */
66 
67 #define MINLPITER 10000 /**< minimal number of LP iterations allowed in each LP solving call */
68 #define DEFAULT_ALPHA 0.9 /**< soft rounding factor to fade out objective coefficients */
69 
70 
71 /* locally defined heuristic data */
72 struct SCIP_HeurData
73 {
74  SCIP_SOL* sol; /**< working solution */
75  SCIP_Real minreldepth; /**< minimal relative depth to start diving */
76  SCIP_Real maxreldepth; /**< maximal relative depth to start diving */
77  SCIP_Real maxlpiterquot; /**< maximal fraction of diving LP iterations compared to node LP iterations */
78  int maxlpiterofs; /**< additional number of allowed LP iterations */
79  int maxsols; /**< total number of feasible solutions found up to which heuristic is called
80  * (-1: no limit) */
81  SCIP_Real depthfac; /**< maximal diving depth: number of binary/integer variables times depthfac */
82  SCIP_Real depthfacnosol; /**< maximal diving depth factor if no feasible solution was found yet */
83  SCIP_Real alpha; /**< soft rounding factor to fade out objective coefficients */
84  SCIP_Longint nlpiterations; /**< LP iterations used in this heuristic */
85  int nsuccess; /**< number of runs that produced at least one feasible solution */
86 };
87 
88 
89 /*
90  * Callback methods
91  */
92 
93 /** copy method for primal heuristic plugins (called when SCIP copies plugins) */
94 static
95 SCIP_DECL_HEURCOPY(heurCopyRootsoldiving)
96 { /*lint --e{715}*/
97  assert(scip != NULL);
98  assert(heur != NULL);
99  assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0);
100 
101  /* call inclusion method of primal heuristic */
103 
104  return SCIP_OKAY;
105 }
106 
107 /** destructor of primal heuristic to free user data (called when SCIP is exiting) */
108 static
109 SCIP_DECL_HEURFREE(heurFreeRootsoldiving) /*lint --e{715}*/
110 { /*lint --e{715}*/
111  SCIP_HEURDATA* heurdata;
112 
113  assert(heur != NULL);
114  assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0);
115  assert(scip != NULL);
116 
117  /* free heuristic data */
118  heurdata = SCIPheurGetData(heur);
119  assert(heurdata != NULL);
120  SCIPfreeBlockMemory(scip, &heurdata);
121  SCIPheurSetData(heur, NULL);
122 
123  return SCIP_OKAY;
124 }
125 
126 
127 /** initialization method of primal heuristic (called after problem was transformed) */
128 static
129 SCIP_DECL_HEURINIT(heurInitRootsoldiving) /*lint --e{715}*/
130 { /*lint --e{715}*/
131  SCIP_HEURDATA* heurdata;
132 
133  assert(heur != NULL);
134  assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0);
135 
136  /* get heuristic data */
137  heurdata = SCIPheurGetData(heur);
138  assert(heurdata != NULL);
139 
140  /* create working solution */
141  SCIP_CALL( SCIPcreateSol(scip, &heurdata->sol, heur) );
142 
143  /* initialize data */
144  heurdata->nlpiterations = 0;
145  heurdata->nsuccess = 0;
146 
147  return SCIP_OKAY;
148 }
149 
150 
151 /** deinitialization method of primal heuristic (called before transformed problem is freed) */
152 static
153 SCIP_DECL_HEUREXIT(heurExitRootsoldiving) /*lint --e{715}*/
154 { /*lint --e{715}*/
155  SCIP_HEURDATA* heurdata;
156 
157  assert(heur != NULL);
158  assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0);
159 
160  /* get heuristic data */
161  heurdata = SCIPheurGetData(heur);
162  assert(heurdata != NULL);
163 
164  /* free working solution */
165  SCIP_CALL( SCIPfreeSol(scip, &heurdata->sol) );
166 
167  return SCIP_OKAY;
168 }
169 
170 
171 /** execution method of primal heuristic */
172 static
173 SCIP_DECL_HEUREXEC(heurExecRootsoldiving) /*lint --e{715}*/
174 { /*lint --e{715}*/
175  SCIP_HEURDATA* heurdata;
176  SCIP_VAR** vars;
177  SCIP_Real* rootsol;
178  SCIP_Real* objchgvals;
179  int* softroundings;
180  int* intvalrounds;
181  int nvars;
182  int nbinvars;
183  int nintvars;
184  int nlpcands;
185  SCIP_LPSOLSTAT lpsolstat;
186  SCIP_Real absstartobjval;
187  SCIP_Real objstep;
188  SCIP_Real alpha;
189  SCIP_Real oldobj;
190  SCIP_Real newobj;
191  SCIP_Bool lperror;
192  SCIP_Bool lpsolchanged;
193  SCIP_Longint nsolsfound;
194  SCIP_Longint ncalls;
195  SCIP_Longint nlpiterations;
196  SCIP_Longint maxnlpiterations;
197  int depth;
198  int maxdepth;
199  int maxdivedepth;
200  int divedepth;
201  int startnlpcands;
202  int ncycles;
203  int i;
204 
205  assert(heur != NULL);
206  assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0);
207  assert(scip != NULL);
208  assert(result != NULL);
209  assert(SCIPhasCurrentNodeLP(scip));
210 
211  *result = SCIP_DELAYED;
212 
213  /* do not call heuristic of node was already detected to be infeasible */
214  if( nodeinfeasible )
215  return SCIP_OKAY;
216 
217  /* only call heuristic, if an optimal LP solution is at hand */
219  return SCIP_OKAY;
220 
221  /* only call heuristic, if the LP objective value is smaller than the cutoff bound */
223  return SCIP_OKAY;
224 
225  /* only call heuristic, if the LP solution is basic (which allows fast resolve in diving) */
226  if( !SCIPisLPSolBasic(scip) )
227  return SCIP_OKAY;
228 
229  /* don't dive two times at the same node */
231  return SCIP_OKAY;
232 
233  *result = SCIP_DIDNOTRUN;
234 
235  /* get heuristic's data */
236  heurdata = SCIPheurGetData(heur);
237  assert(heurdata != NULL);
238 
239  /* only apply heuristic, if only a few solutions have been found */
240  if( heurdata->maxsols >= 0 && SCIPgetNSolsFound(scip) >= heurdata->maxsols )
241  return SCIP_OKAY;
242 
243  /* only try to dive, if we are in the correct part of the tree, given by minreldepth and maxreldepth */
244  depth = SCIPgetDepth(scip);
245  maxdepth = SCIPgetMaxDepth(scip);
246  maxdepth = MAX(maxdepth, 30);
247  if( depth < heurdata->minreldepth*maxdepth || depth > heurdata->maxreldepth*maxdepth )
248  return SCIP_OKAY;
249 
250  /* calculate the maximal number of LP iterations until heuristic is aborted */
251  nlpiterations = SCIPgetNNodeLPIterations(scip);
252  ncalls = SCIPheurGetNCalls(heur);
253  nsolsfound = 10*SCIPheurGetNBestSolsFound(heur) + heurdata->nsuccess;
254  maxnlpiterations = (SCIP_Longint)((1.0 + 10.0*(nsolsfound+1.0)/(ncalls+1.0)) * heurdata->maxlpiterquot * nlpiterations);
255  maxnlpiterations += heurdata->maxlpiterofs;
256 
257  /* don't try to dive, if we took too many LP iterations during diving */
258  if( heurdata->nlpiterations >= maxnlpiterations )
259  return SCIP_OKAY;
260 
261  /* allow at least a certain number of LP iterations in this dive */
262  maxnlpiterations = MAX(maxnlpiterations, heurdata->nlpiterations + MINLPITER);
263 
264  /* get number of fractional variables, that should be integral */
265  nlpcands = SCIPgetNLPBranchCands(scip);
266 
267  /* don't try to dive, if there are no fractional variables */
268  if( nlpcands == 0 )
269  return SCIP_OKAY;
270 
271  /* calculate the maximal diving depth */
273  if( SCIPgetNSolsFound(scip) == 0 )
274  maxdivedepth = (int)(heurdata->depthfacnosol * nvars);
275  else
276  maxdivedepth = (int)(heurdata->depthfac * nvars);
277  maxdivedepth = MAX(maxdivedepth, 10);
278 
279  *result = SCIP_DIDNOTFIND;
280 
281  /* get all variables of LP */
282  SCIP_CALL( SCIPgetVarsData(scip, &vars, &nvars, &nbinvars, &nintvars, NULL, NULL) );
283 
284  /* get root solution value of all binary and integer variables */
285  SCIP_CALL( SCIPallocBufferArray(scip, &rootsol, nbinvars + nintvars) );
286  for( i = 0; i < nbinvars + nintvars; i++ )
287  rootsol[i] = SCIPvarGetRootSol(vars[i]);
288 
289  /* get current LP objective value, and calculate length of a single step in an objective coefficient */
290  absstartobjval = SCIPgetLPObjval(scip);
291  absstartobjval = ABS(absstartobjval);
292  absstartobjval = MAX(absstartobjval, 1.0);
293  objstep = absstartobjval / 10.0;
294 
295  /* initialize array storing the preferred soft rounding directions and counting the integral value rounds */
296  SCIP_CALL( SCIPallocBufferArray(scip, &softroundings, nbinvars + nintvars) );
297  BMSclearMemoryArray(softroundings, nbinvars + nintvars);
298  SCIP_CALL( SCIPallocBufferArray(scip, &intvalrounds, nbinvars + nintvars) );
299  BMSclearMemoryArray(intvalrounds, nbinvars + nintvars);
300 
301  /* allocate temporary memory for buffering objective changes */
302  SCIP_CALL( SCIPallocBufferArray(scip, &objchgvals, nbinvars + nintvars) );
303 
304  /* start diving */
306 
307  SCIPdebugMsg(scip, "(node %" SCIP_LONGINT_FORMAT ") executing rootsoldiving heuristic: depth=%d, %d fractionals, dualbound=%g, maxnlpiterations=%" SCIP_LONGINT_FORMAT ", maxdivedepth=%d, LPobj=%g, objstep=%g\n",
308  SCIPgetNNodes(scip), SCIPgetDepth(scip), nlpcands, SCIPgetDualbound(scip), maxnlpiterations, maxdivedepth,
309  SCIPgetLPObjval(scip), objstep);
310 
311  lperror = FALSE;
312  divedepth = 0;
313  lpsolstat = SCIP_LPSOLSTAT_OPTIMAL;
314  alpha = heurdata->alpha;
315  ncycles = 0;
316  lpsolchanged = TRUE;
317  startnlpcands = nlpcands;
318  while( !lperror && lpsolstat == SCIP_LPSOLSTAT_OPTIMAL && nlpcands > 0 && ncycles < 10
319  && (divedepth < 10
320  || nlpcands <= startnlpcands - divedepth/2
321  || (divedepth < maxdivedepth && heurdata->nlpiterations < maxnlpiterations))
322  && !SCIPisStopped(scip) )
323  {
324  SCIP_Bool success;
325  int hardroundingidx;
326  int hardroundingdir;
327  SCIP_Real hardroundingoldbd;
328  SCIP_Real hardroundingnewbd;
329  SCIP_Bool boundschanged;
330 
331  SCIP_RETCODE retcode;
332 
333  /* create solution from diving LP and try to round it */
334  SCIP_CALL( SCIPlinkLPSol(scip, heurdata->sol) );
335  SCIP_CALL( SCIProundSol(scip, heurdata->sol, &success) );
336 
337  if( success )
338  {
339  SCIPdebugMsg(scip, "rootsoldiving found roundable primal solution: obj=%g\n", SCIPgetSolOrigObj(scip, heurdata->sol));
340 
341  /* try to add solution to SCIP */
342  SCIP_CALL( SCIPtrySol(scip, heurdata->sol, FALSE, FALSE, FALSE, FALSE, FALSE, &success) );
343 
344  /* check, if solution was feasible and good enough */
345  if( success )
346  {
347  SCIPdebugMsg(scip, " -> solution was feasible and good enough\n");
348  *result = SCIP_FOUNDSOL;
349  }
350  }
351 
352  divedepth++;
353  hardroundingidx = -1;
354  hardroundingdir = 0;
355  hardroundingoldbd = 0.0;
356  hardroundingnewbd = 0.0;
357  boundschanged = FALSE;
358 
359  SCIPdebugMsg(scip, "dive %d/%d, LP iter %" SCIP_LONGINT_FORMAT "/%" SCIP_LONGINT_FORMAT ":\n", divedepth, maxdivedepth, heurdata->nlpiterations, maxnlpiterations);
360 
361  /* round solution x* from diving LP:
362  * - x~_j = down(x*_j) if x*_j is integer or binary variable and x*_j <= root solution_j
363  * - x~_j = up(x*_j) if x*_j is integer or binary variable and x*_j > root solution_j
364  * - x~_j = x*_j if x*_j is continuous variable
365  * change objective function in diving LP:
366  * - if x*_j is integral, or j is a continuous variable, set obj'_j = alpha * obj_j
367  * - otherwise, set obj'_j = alpha * obj_j + sign(x*_j - x~_j)
368  */
369  for( i = 0; i < nbinvars + nintvars; i++ )
370  {
371  SCIP_VAR* var;
372  SCIP_Real solval;
373 
374  var = vars[i];
375  oldobj = SCIPgetVarObjDive(scip, var);
376  newobj = oldobj;
377 
378  solval = SCIPvarGetLPSol(var);
379  if( SCIPisFeasIntegral(scip, solval) )
380  {
381  /* if the variable became integral after a soft rounding, count the rounds; after a while, fix it to its
382  * current integral value;
383  * otherwise, fade out the objective value
384  */
385  if( softroundings[i] != 0 && lpsolchanged )
386  {
387  intvalrounds[i]++;
388  if( intvalrounds[i] == 5 && SCIPgetVarLbDive(scip, var) < SCIPgetVarUbDive(scip, var) - 0.5 )
389  {
390  /* use exact integral value, if the variable is only integral within numerical tolerances */
391  solval = SCIPfloor(scip, solval+0.5);
392  SCIPdebugMsg(scip, " -> fixing <%s> = %g\n", SCIPvarGetName(var), solval);
393  SCIP_CALL( SCIPchgVarLbDive(scip, var, solval) );
394  SCIP_CALL( SCIPchgVarUbDive(scip, var, solval) );
395  boundschanged = TRUE;
396  }
397  }
398  else
399  newobj = alpha * oldobj;
400  }
401  else if( solval <= rootsol[i] )
402  {
403  /* if the variable was soft rounded most of the time downwards, round it downwards by changing the bounds;
404  * otherwise, apply soft rounding by changing the objective value
405  */
406  softroundings[i]--;
407  if( softroundings[i] <= -10 && hardroundingidx == -1 )
408  {
409  SCIPdebugMsg(scip, " -> hard rounding <%s>[%g] <= %g\n",
410  SCIPvarGetName(var), solval, SCIPfeasFloor(scip, solval));
411  hardroundingidx = i;
412  hardroundingdir = -1;
413  hardroundingoldbd = SCIPgetVarUbDive(scip, var);
414  hardroundingnewbd = SCIPfeasFloor(scip, solval);
415  SCIP_CALL( SCIPchgVarUbDive(scip, var, hardroundingnewbd) );
416  boundschanged = TRUE;
417  }
418  else
419  newobj = alpha * oldobj + objstep;
420  }
421  else
422  {
423  /* if the variable was soft rounded most of the time upwards, round it upwards by changing the bounds;
424  * otherwise, apply soft rounding by changing the objective value
425  */
426  softroundings[i]++;
427  if( softroundings[i] >= +10 && hardroundingidx == -1 )
428  {
429  SCIPdebugMsg(scip, " -> hard rounding <%s>[%g] >= %g\n",
430  SCIPvarGetName(var), solval, SCIPfeasCeil(scip, solval));
431  hardroundingidx = i;
432  hardroundingdir = +1;
433  hardroundingoldbd = SCIPgetVarLbDive(scip, var);
434  hardroundingnewbd = SCIPfeasCeil(scip, solval);
435  SCIP_CALL( SCIPchgVarLbDive(scip, var, hardroundingnewbd) );
436  boundschanged = TRUE;
437  }
438  else
439  newobj = alpha * oldobj - objstep;
440  }
441 
442  /* remember the objective change */
443  objchgvals[i] = newobj;
444  }
445 
446  /* apply objective changes if there was no bound change */
447  if( !boundschanged )
448  {
449  /* apply cached changes on integer variables */
450  for( i = 0; i < nbinvars + nintvars; ++i )
451  {
452  SCIP_VAR* var;
453 
454  var = vars[i];
455  SCIPdebugMsg(scip, " -> i=%d var <%s>, solval=%g, rootsol=%g, oldobj=%g, newobj=%g\n",
456  i, SCIPvarGetName(var), SCIPvarGetLPSol(var), rootsol[i], SCIPgetVarObjDive(scip, var), objchgvals[i]);
457 
458  SCIP_CALL( SCIPchgVarObjDive(scip, var, objchgvals[i]) );
459  }
460 
461  /* fade out the objective values of the continuous variables */
462  for( i = nbinvars + nintvars; i < nvars; i++ )
463  {
464  SCIP_VAR* var;
465 
466  var = vars[i];
467  oldobj = SCIPgetVarObjDive(scip, var);
468  newobj = alpha * oldobj;
469 
470  SCIPdebugMsg(scip, " -> i=%d var <%s>, solval=%g, oldobj=%g, newobj=%g\n",
471  i, SCIPvarGetName(var), SCIPvarGetLPSol(var), oldobj, newobj);
472 
473  SCIP_CALL( SCIPchgVarObjDive(scip, var, newobj) );
474  }
475  }
476 
477  SOLVEAGAIN:
478  /* resolve the diving LP */
479  nlpiterations = SCIPgetNLPIterations(scip);
480 
481  retcode = SCIPsolveDiveLP(scip, MAX((int)(maxnlpiterations - heurdata->nlpiterations), MINLPITER), &lperror, NULL);
482  lpsolstat = SCIPgetLPSolstat(scip);
483 
484  /* Errors in the LP solver should not kill the overall solving process, if the LP is just needed for a heuristic.
485  * Hence in optimized mode, the return code is caught and a warning is printed, only in debug mode, SCIP will stop.
486  */
487  if( retcode != SCIP_OKAY )
488  {
489 #ifndef NDEBUG
490  if( lpsolstat != SCIP_LPSOLSTAT_UNBOUNDEDRAY )
491  {
492  SCIP_CALL( retcode );
493  }
494 #endif
495  SCIPwarningMessage(scip, "Error while solving LP in Rootsoldiving heuristic; LP solve terminated with code <%d>\n", retcode);
496  SCIPwarningMessage(scip, "This does not affect the remaining solution procedure --> continue\n");
497  }
498 
499  if( lperror )
500  break;
501 
502  /* update iteration count */
503  heurdata->nlpiterations += SCIPgetNLPIterations(scip) - nlpiterations;
504 
505  /* if no LP iterations were performed, we stayed at the same solution -> count this cycling */
506  lpsolchanged = (SCIPgetNLPIterations(scip) != nlpiterations);
507  if( lpsolchanged )
508  ncycles = 0;
509  else if( !boundschanged ) /* do not count if integral variables have been fixed */
510  ncycles++;
511 
512  /* get LP solution status and number of fractional variables, that should be integral */
513  if( lpsolstat == SCIP_LPSOLSTAT_INFEASIBLE && hardroundingidx != -1 )
514  {
515  SCIP_VAR* var;
516 
517  var = vars[hardroundingidx];
518 
519  /* round the hard rounded variable to the opposite direction and resolve the LP */
520  if( hardroundingdir == -1 )
521  {
522  SCIPdebugMsg(scip, " -> opposite hard rounding <%s> >= %g\n", SCIPvarGetName(var), hardroundingnewbd + 1.0);
523  SCIP_CALL( SCIPchgVarUbDive(scip, var, hardroundingoldbd) );
524  SCIP_CALL( SCIPchgVarLbDive(scip, var, hardroundingnewbd + 1.0) );
525  }
526  else
527  {
528  SCIPdebugMsg(scip, " -> opposite hard rounding <%s> <= %g\n", SCIPvarGetName(var), hardroundingnewbd - 1.0);
529  SCIP_CALL( SCIPchgVarLbDive(scip, var, hardroundingoldbd) );
530  SCIP_CALL( SCIPchgVarUbDive(scip, var, hardroundingnewbd - 1.0) );
531  }
532  hardroundingidx = -1;
533  goto SOLVEAGAIN;
534  }
535  if( lpsolstat == SCIP_LPSOLSTAT_OPTIMAL )
536  nlpcands = SCIPgetNLPBranchCands(scip);
537  SCIPdebugMsg(scip, " -> lpsolstat=%d, nfrac=%d\n", lpsolstat, nlpcands);
538  }
539 
540  SCIPdebugMsg(scip, "---> diving finished: lpsolstat = %d, depth %d/%d, LP iter %" SCIP_LONGINT_FORMAT "/%" SCIP_LONGINT_FORMAT "\n",
541  lpsolstat, divedepth, maxdivedepth, heurdata->nlpiterations, maxnlpiterations);
542 
543  /* check if a solution has been found */
544  if( nlpcands == 0 && !lperror && lpsolstat == SCIP_LPSOLSTAT_OPTIMAL )
545  {
546  SCIP_Bool success;
547 
548  /* create solution from diving LP */
549  SCIP_CALL( SCIPlinkLPSol(scip, heurdata->sol) );
550  SCIPdebugMsg(scip, "rootsoldiving found primal solution: obj=%g\n", SCIPgetSolOrigObj(scip, heurdata->sol));
551 
552  /* try to add solution to SCIP */
553  SCIP_CALL( SCIPtrySol(scip, heurdata->sol, FALSE, FALSE, FALSE, FALSE, FALSE, &success) );
554 
555  /* check, if solution was feasible and good enough */
556  if( success )
557  {
558  SCIPdebugMsg(scip, " -> solution was feasible and good enough\n");
559  *result = SCIP_FOUNDSOL;
560  }
561  }
562 
563  /* end diving */
565 
566  if( *result == SCIP_FOUNDSOL )
567  heurdata->nsuccess++;
568 
569  /* free temporary memory */
570  SCIPfreeBufferArray(scip, &objchgvals);
571  SCIPfreeBufferArray(scip, &intvalrounds);
572  SCIPfreeBufferArray(scip, &softroundings);
573  SCIPfreeBufferArray(scip, &rootsol);
574 
575  SCIPdebugMsg(scip, "rootsoldiving heuristic finished\n");
576 
577  return SCIP_OKAY;
578 }
579 
580 
581 /*
582  * heuristic specific interface methods
583  */
584 
585 /** creates the rootsoldiving heuristic and includes it in SCIP */
587  SCIP* scip /**< SCIP data structure */
588  )
589 {
590  SCIP_HEURDATA* heurdata;
591  SCIP_HEUR* heur;
592 
593  /* create Rootsoldiving primal heuristic data */
594  SCIP_CALL( SCIPallocBlockMemory(scip, &heurdata) );
595 
596  /* include primal heuristic */
597  SCIP_CALL( SCIPincludeHeurBasic(scip, &heur,
599  HEUR_MAXDEPTH, HEUR_TIMING, HEUR_USESSUBSCIP, heurExecRootsoldiving, heurdata) );
600 
601  assert(heur != NULL);
602 
603  /* set non-NULL pointers to callback methods */
604  SCIP_CALL( SCIPsetHeurCopy(scip, heur, heurCopyRootsoldiving) );
605  SCIP_CALL( SCIPsetHeurFree(scip, heur, heurFreeRootsoldiving) );
606  SCIP_CALL( SCIPsetHeurInit(scip, heur, heurInitRootsoldiving) );
607  SCIP_CALL( SCIPsetHeurExit(scip, heur, heurExitRootsoldiving) );
608 
609  /* rootsoldiving heuristic parameters */
611  "heuristics/rootsoldiving/minreldepth",
612  "minimal relative depth to start diving",
613  &heurdata->minreldepth, TRUE, DEFAULT_MINRELDEPTH, 0.0, 1.0, NULL, NULL) );
615  "heuristics/rootsoldiving/maxreldepth",
616  "maximal relative depth to start diving",
617  &heurdata->maxreldepth, TRUE, DEFAULT_MAXRELDEPTH, 0.0, 1.0, NULL, NULL) );
619  "heuristics/rootsoldiving/maxlpiterquot",
620  "maximal fraction of diving LP iterations compared to node LP iterations",
621  &heurdata->maxlpiterquot, FALSE, DEFAULT_MAXLPITERQUOT, 0.0, SCIP_REAL_MAX, NULL, NULL) );
623  "heuristics/rootsoldiving/maxlpiterofs",
624  "additional number of allowed LP iterations",
625  &heurdata->maxlpiterofs, FALSE, DEFAULT_MAXLPITEROFS, 0, INT_MAX, NULL, NULL) );
627  "heuristics/rootsoldiving/maxsols",
628  "total number of feasible solutions found up to which heuristic is called (-1: no limit)",
629  &heurdata->maxsols, TRUE, DEFAULT_MAXSOLS, -1, INT_MAX, NULL, NULL) );
631  "heuristics/rootsoldiving/depthfac",
632  "maximal diving depth: number of binary/integer variables times depthfac",
633  &heurdata->depthfac, TRUE, DEFAULT_DEPTHFAC, 0.0, SCIP_REAL_MAX, NULL, NULL) );
635  "heuristics/rootsoldiving/depthfacnosol",
636  "maximal diving depth factor if no feasible solution was found yet",
637  &heurdata->depthfacnosol, TRUE, DEFAULT_DEPTHFACNOSOL, 0.0, SCIP_REAL_MAX, NULL, NULL) );
639  "heuristics/rootsoldiving/alpha",
640  "soft rounding factor to fade out objective coefficients",
641  &heurdata->alpha, TRUE, DEFAULT_ALPHA, 0.0, 1.0, NULL, NULL) );
642 
643  return SCIP_OKAY;
644 }
645 
int SCIPgetNIntVars(SCIP *scip)
Definition: scip_prob.c:2081
SCIP_RETCODE SCIPlinkLPSol(SCIP *scip, SCIP_SOL *sol)
Definition: scip_sol.c:1017
#define HEUR_NAME
public methods for SCIP parameter handling
SCIP_Longint SCIPgetNLPIterations(SCIP *scip)
public methods for memory management
SCIP_Real SCIPgetCutoffbound(SCIP *scip)
SCIP_Longint SCIPheurGetNBestSolsFound(SCIP_HEUR *heur)
Definition: heur.c:1587
SCIP_Longint SCIPgetNSolsFound(SCIP *scip)
#define DEFAULT_MAXRELDEPTH
SCIP_RETCODE SCIPsetHeurExit(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEUREXIT((*heurexit)))
Definition: scip_heur.c:201
SCIP_Bool SCIPisGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
#define HEUR_DISPCHAR
SCIP_RETCODE SCIPincludeHeurRootsoldiving(SCIP *scip)
#define HEUR_FREQ
SCIP_Real SCIPvarGetRootSol(SCIP_VAR *var)
Definition: var.c:13349
int SCIPgetMaxDepth(SCIP *scip)
SCIP_RETCODE SCIPgetVarsData(SCIP *scip, SCIP_VAR ***vars, int *nvars, int *nbinvars, int *nintvars, int *nimplvars, int *ncontvars)
Definition: scip_prob.c:1865
#define FALSE
Definition: def.h:87
#define TRUE
Definition: def.h:86
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:54
SCIP_RETCODE SCIPchgVarLbDive(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound)
Definition: scip_lp.c:2404
#define DEFAULT_ALPHA
struct SCIP_HeurData SCIP_HEURDATA
Definition: type_heur.h:67
public methods for problem variables
#define SCIPfreeBlockMemory(scip, ptr)
Definition: scip_mem.h:99
SCIP_RETCODE SCIPincludeHeurBasic(SCIP *scip, SCIP_HEUR **heur, const char *name, const char *desc, char dispchar, int priority, int freq, int freqofs, int maxdepth, SCIP_HEURTIMING timingmask, SCIP_Bool usessubscip, SCIP_DECL_HEUREXEC((*heurexec)), SCIP_HEURDATA *heurdata)
Definition: scip_heur.c:108
#define SCIPfreeBufferArray(scip, ptr)
Definition: scip_mem.h:127
enum SCIP_LPSolStat SCIP_LPSOLSTAT
Definition: type_lp.h:42
void SCIPheurSetData(SCIP_HEUR *heur, SCIP_HEURDATA *heurdata)
Definition: heur.c:1362
int SCIPgetNLPBranchCands(SCIP *scip)
Definition: scip_branch.c:419
void SCIPwarningMessage(SCIP *scip, const char *formatstr,...)
Definition: scip_message.c:111
#define SCIPdebugMsg
Definition: scip_message.h:69
SCIP_RETCODE SCIPaddIntParam(SCIP *scip, const char *name, const char *desc, int *valueptr, SCIP_Bool isadvanced, int defaultvalue, int minvalue, int maxvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition: scip_param.c:74
SCIP_Real SCIPfeasCeil(SCIP *scip, SCIP_Real val)
public methods for numerical tolerances
SCIP_Real SCIPfeasFloor(SCIP *scip, SCIP_Real val)
#define DEFAULT_MAXLPITEROFS
public methods for querying solving statistics
public methods for the branch-and-bound tree
SCIP_Bool SCIPisLPSolBasic(SCIP *scip)
Definition: scip_lp.c:658
SCIP_Real SCIPgetVarUbDive(SCIP *scip, SCIP_VAR *var)
Definition: scip_lp.c:2630
static SCIP_DECL_HEUREXEC(heurExecRootsoldiving)
const char * SCIPheurGetName(SCIP_HEUR *heur)
Definition: heur.c:1441
SCIP_RETCODE SCIPsolveDiveLP(SCIP *scip, int itlim, SCIP_Bool *lperror, SCIP_Bool *cutoff)
Definition: scip_lp.c:2663
SCIP_RETCODE SCIPsetHeurFree(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURFREE((*heurfree)))
Definition: scip_heur.c:169
SCIP_Real SCIPgetDualbound(SCIP *scip)
#define DEFAULT_MAXSOLS
const char * SCIPvarGetName(SCIP_VAR *var)
Definition: var.c:17251
#define HEUR_MAXDEPTH
#define NULL
Definition: lpi_spx1.cpp:155
SCIP_Real SCIPvarGetLPSol(SCIP_VAR *var)
Definition: var.c:18284
#define HEUR_TIMING
#define SCIP_CALL(x)
Definition: def.h:384
#define HEUR_PRIORITY
SCIP_Longint SCIPheurGetNCalls(SCIP_HEUR *heur)
Definition: heur.c:1567
SCIP_Bool SCIPhasCurrentNodeLP(SCIP *scip)
Definition: scip_lp.c:74
#define DEFAULT_MINRELDEPTH
public methods for primal heuristic plugins and divesets
SCIP_Longint SCIPgetLastDivenode(SCIP *scip)
Definition: scip_lp.c:2730
SCIP_Longint SCIPgetNNodeLPIterations(SCIP *scip)
#define SCIPallocBufferArray(scip, ptr, num)
Definition: scip_mem.h:115
LP diving heuristic that changes variables&#39; objective values using root LP solution as guide...
#define SCIP_Bool
Definition: def.h:84
#define DEFAULT_DEPTHFAC
SCIP_LPSOLSTAT SCIPgetLPSolstat(SCIP *scip)
Definition: scip_lp.c:159
static SCIP_DECL_HEURFREE(heurFreeRootsoldiving)
SCIP_RETCODE SCIProundSol(SCIP *scip, SCIP_SOL *sol, SCIP_Bool *success)
Definition: scip_sol.c:2446
int SCIPgetDepth(SCIP *scip)
Definition: scip_tree.c:661
SCIP_RETCODE SCIPchgVarUbDive(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound)
Definition: scip_lp.c:2436
#define HEUR_USESSUBSCIP
#define MAX(x, y)
Definition: tclique_def.h:83
static SCIP_DECL_HEUREXIT(heurExitRootsoldiving)
SCIP_RETCODE SCIPfreeSol(SCIP *scip, SCIP_SOL **sol)
Definition: scip_sol.c:976
SCIP_Real SCIPgetSolOrigObj(SCIP *scip, SCIP_SOL *sol)
Definition: scip_sol.c:1435
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_sol.c:3125
int SCIPgetNBinVars(SCIP *scip)
Definition: scip_prob.c:2036
public methods for the LP relaxation, rows and columns
#define SCIP_REAL_MAX
Definition: def.h:178
public methods for branching rule plugins and branching
general public methods
SCIP_Real SCIPgetLPObjval(SCIP *scip)
Definition: scip_lp.c:238
SCIP_RETCODE SCIPchgVarObjDive(SCIP *scip, SCIP_VAR *var, SCIP_Real newobj)
Definition: scip_lp.c:2363
#define DEFAULT_MAXLPITERQUOT
public methods for solutions
public methods for message output
SCIP_RETCODE SCIPsetHeurInit(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURINIT((*heurinit)))
Definition: scip_heur.c:185
#define SCIP_Real
Definition: def.h:177
SCIP_Bool SCIPisStopped(SCIP *scip)
Definition: scip_general.c:694
public methods for message handling
#define HEUR_DESC
#define MINLPITER
#define SCIP_Longint
Definition: def.h:162
SCIP_Real SCIPgetVarLbDive(SCIP *scip, SCIP_VAR *var)
Definition: scip_lp.c:2601
SCIP_RETCODE SCIPstartDive(SCIP *scip)
Definition: scip_lp.c:2227
static SCIP_DECL_HEURCOPY(heurCopyRootsoldiving)
SCIP_RETCODE SCIPsetHeurCopy(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURCOPY((*heurcopy)))
Definition: scip_heur.c:153
SCIP_Bool SCIPisFeasIntegral(SCIP *scip, SCIP_Real val)
#define BMSclearMemoryArray(ptr, num)
Definition: memory.h:123
#define HEUR_FREQOFS
public methods for primal heuristics
SCIPallocBlockMemory(scip, subsol))
SCIP_RETCODE SCIPendDive(SCIP *scip)
Definition: scip_lp.c:2276
SCIP_HEURDATA * SCIPheurGetData(SCIP_HEUR *heur)
Definition: heur.c:1352
SCIP_Longint SCIPgetNNodes(SCIP *scip)
public methods for global and local (sub)problems
SCIP_Real SCIPgetVarObjDive(SCIP *scip, SCIP_VAR *var)
Definition: scip_lp.c:2572
SCIP_RETCODE SCIPaddRealParam(SCIP *scip, const char *name, const char *desc, SCIP_Real *valueptr, SCIP_Bool isadvanced, SCIP_Real defaultvalue, SCIP_Real minvalue, SCIP_Real maxvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition: scip_param.c:130
SCIP_Real SCIPfloor(SCIP *scip, SCIP_Real val)
static SCIP_DECL_HEURINIT(heurInitRootsoldiving)
#define DEFAULT_DEPTHFACNOSOL
SCIP_RETCODE SCIPcreateSol(SCIP *scip, SCIP_SOL **sol, SCIP_HEUR *heur)
Definition: scip_sol.c:319
memory allocation routines