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