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