Scippy

SCIP

Solving Constraint Integer Programs

heur_guideddiving.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-2014 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_guideddiving.c
17  * @brief LP diving heuristic that chooses fixings in direction of incumbent solutions
18  * @author Tobias Achterberg
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 
26 #include "scip/heur_guideddiving.h"
27 
28 
29 #define HEUR_NAME "guideddiving"
30 #define HEUR_DESC "LP diving heuristic that chooses fixings in direction of incumbent solutions"
31 #define HEUR_DISPCHAR 'g'
32 #define HEUR_PRIORITY -1007000
33 #define HEUR_FREQ 10
34 #define HEUR_FREQOFS 7
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.05 /**< 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_MAXDIVEUBQUOT 0.8 /**< maximal quotient (curlowerbound - lowerbound)/(cutoffbound - lowerbound)
49  * where diving is performed (0.0: no limit) */
50 #define DEFAULT_MAXDIVEAVGQUOT 0.0 /**< maximal quotient (curlowerbound - lowerbound)/(avglowerbound - lowerbound)
51  * where diving is performed (0.0: no limit) */
52 #define DEFAULT_BACKTRACK TRUE /**< use one level of backtracking if infeasibility is encountered? */
53 
54 #define MINLPITER 10000 /**< minimal number of LP iterations allowed in each LP solving call */
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  SCIP_Real maxdiveubquot; /**< maximal quotient (curlowerbound - lowerbound)/(cutoffbound - lowerbound)
66  * where diving is performed (0.0: no limit) */
67  SCIP_Real maxdiveavgquot; /**< maximal quotient (curlowerbound - lowerbound)/(avglowerbound - lowerbound)
68  * where diving is performed (0.0: no limit) */
69  SCIP_Bool backtrack; /**< use one level of backtracking if infeasibility is encountered? */
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  * local methods
77  */
78 
79 
80 /*
81  * Callback methods
82  */
83 
84 /** copy method for primal heuristic plugins (called when SCIP copies plugins) */
85 static
86 SCIP_DECL_HEURCOPY(heurCopyGuideddiving)
87 { /*lint --e{715}*/
88  assert(scip != NULL);
89  assert(heur != NULL);
90  assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0);
91 
92  /* call inclusion method of primal heuristic */
93  SCIP_CALL( SCIPincludeHeurGuideddiving(scip) );
94 
95  return SCIP_OKAY;
96 }
97 
98 /** destructor of primal heuristic to free user data (called when SCIP is exiting) */
99 static
100 SCIP_DECL_HEURFREE(heurFreeGuideddiving) /*lint --e{715}*/
101 { /*lint --e{715}*/
102  SCIP_HEURDATA* heurdata;
103 
104  assert(heur != NULL);
105  assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0);
106  assert(scip != NULL);
107 
108  /* free heuristic data */
109  heurdata = SCIPheurGetData(heur);
110  assert(heurdata != NULL);
111  SCIPfreeMemory(scip, &heurdata);
112  SCIPheurSetData(heur, NULL);
113 
114  return SCIP_OKAY;
115 }
116 
117 
118 /** initialization method of primal heuristic (called after problem was transformed) */
119 static
120 SCIP_DECL_HEURINIT(heurInitGuideddiving) /*lint --e{715}*/
121 { /*lint --e{715}*/
122  SCIP_HEURDATA* heurdata;
123 
124  assert(heur != NULL);
125  assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0);
126 
127  /* get heuristic data */
128  heurdata = SCIPheurGetData(heur);
129  assert(heurdata != NULL);
130 
131  /* create working solution */
132  SCIP_CALL( SCIPcreateSol(scip, &heurdata->sol, heur) );
133 
134  /* initialize data */
135  heurdata->nlpiterations = 0;
136  heurdata->nsuccess = 0;
137 
138  return SCIP_OKAY;
139 }
140 
141 
142 /** deinitialization method of primal heuristic (called before transformed problem is freed) */
143 static
144 SCIP_DECL_HEUREXIT(heurExitGuideddiving) /*lint --e{715}*/
145 { /*lint --e{715}*/
146  SCIP_HEURDATA* heurdata;
147 
148  assert(heur != NULL);
149  assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0);
150 
151  /* get heuristic data */
152  heurdata = SCIPheurGetData(heur);
153  assert(heurdata != NULL);
154 
155  /* free working solution */
156  SCIP_CALL( SCIPfreeSol(scip, &heurdata->sol) );
157 
158  return SCIP_OKAY;
159 }
160 
161 
162 /** execution method of primal heuristic */
163 static
164 SCIP_DECL_HEUREXEC(heurExecGuideddiving) /*lint --e{715}*/
165 { /*lint --e{715}*/
166  SCIP_HEURDATA* heurdata;
167  SCIP_LPSOLSTAT lpsolstat;
168  SCIP_SOL* bestsol;
169  SCIP_VAR* var;
170  SCIP_VAR** lpcands;
171  SCIP_Real* lpcandssol;
172  SCIP_Real* lpcandsfrac;
173  SCIP_Real searchubbound;
174  SCIP_Real searchavgbound;
175  SCIP_Real searchbound;
176  SCIP_Real objval;
177  SCIP_Real oldobjval;
178  SCIP_Real obj;
179  SCIP_Real objgain;
180  SCIP_Real bestobjgain;
181  SCIP_Real frac;
182  SCIP_Real bestfrac;
183  SCIP_Real solval;
184  SCIP_Real bestsolval;
185  SCIP_Bool bestcandmayrounddown;
186  SCIP_Bool bestcandmayroundup;
187  SCIP_Bool bestcandroundup;
188  SCIP_Bool mayrounddown;
189  SCIP_Bool mayroundup;
190  SCIP_Bool roundup;
191  SCIP_Bool lperror;
192  SCIP_Bool cutoff;
193  SCIP_Bool backtracked;
194  SCIP_Longint ncalls;
195  SCIP_Longint nsolsfound;
196  SCIP_Longint nlpiterations;
197  SCIP_Longint maxnlpiterations;
198  int nlpcands;
199  int startnlpcands;
200  int depth;
201  int maxdepth;
202  int maxdivedepth;
203  int divedepth;
204  int bestcand;
205  int c;
206 
207  assert(heur != NULL);
208  assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0);
209  assert(scip != NULL);
210  assert(result != NULL);
211  assert(SCIPhasCurrentNodeLP(scip));
212 
213  *result = SCIP_DELAYED;
214 
215  /* do not call heuristic of node was already detected to be infeasible */
216  if( nodeinfeasible )
217  return SCIP_OKAY;
218 
219  /* only call heuristic, if an optimal LP solution is at hand */
220  if( SCIPgetLPSolstat(scip) != SCIP_LPSOLSTAT_OPTIMAL )
221  return SCIP_OKAY;
222 
223  /* only call heuristic, if the LP objective value is smaller than the cutoff bound */
224  if( SCIPisGE(scip, SCIPgetLPObjval(scip), SCIPgetCutoffbound(scip)) )
225  return SCIP_OKAY;
226 
227  /* only call heuristic, if the LP solution is basic (which allows fast resolve in diving) */
228  if( !SCIPisLPSolBasic(scip) )
229  return SCIP_OKAY;
230 
231  /* don't dive two times at the same node */
232  if( SCIPgetLastDivenode(scip) == SCIPgetNNodes(scip) && SCIPgetDepth(scip) > 0 )
233  return SCIP_OKAY;
234 
235  *result = SCIP_DIDNOTRUN;
236 
237  /* don't dive, if no feasible solutions exist */
238  if( SCIPgetNSols(scip) == 0 )
239  return SCIP_OKAY;
240 
241  /* get heuristic's data */
242  heurdata = SCIPheurGetData(heur);
243  assert(heurdata != NULL);
244 
245  /* only try to dive, if we are in the correct part of the tree, given by minreldepth and maxreldepth */
246  depth = SCIPgetDepth(scip);
247  maxdepth = SCIPgetMaxDepth(scip);
248  maxdepth = MAX(maxdepth, 30);
249  if( depth < heurdata->minreldepth*maxdepth || depth > heurdata->maxreldepth*maxdepth )
250  return SCIP_OKAY;
251 
252  /* calculate the maximal number of LP iterations until heuristic is aborted */
253  nlpiterations = SCIPgetNNodeLPIterations(scip);
254  ncalls = SCIPheurGetNCalls(heur);
255  nsolsfound = 10*SCIPheurGetNBestSolsFound(heur) + heurdata->nsuccess;
256  maxnlpiterations = (SCIP_Longint)((1.0 + 10.0*(nsolsfound+1.0)/(ncalls+1.0)) * heurdata->maxlpiterquot * nlpiterations);
257  maxnlpiterations += heurdata->maxlpiterofs;
258 
259  /* don't try to dive, if we took too many LP iterations during diving */
260  if( heurdata->nlpiterations >= maxnlpiterations )
261  return SCIP_OKAY;
262 
263  /* allow at least a certain number of LP iterations in this dive */
264  maxnlpiterations = MAX(maxnlpiterations, heurdata->nlpiterations + MINLPITER);
265 
266  /* get fractional variables that should be integral */
267  SCIP_CALL( SCIPgetLPBranchCands(scip, &lpcands, &lpcandssol, &lpcandsfrac, &nlpcands, NULL, NULL) );
268 
269  /* don't try to dive, if there are no fractional variables */
270  if( nlpcands == 0 )
271  return SCIP_OKAY;
272 
273  /* calculate the objective search bound */
274  if( heurdata->maxdiveubquot > 0.0 )
275  searchubbound = SCIPgetLowerbound(scip)
276  + heurdata->maxdiveubquot * (SCIPgetCutoffbound(scip) - SCIPgetLowerbound(scip));
277  else
278  searchubbound = SCIPinfinity(scip);
279  if( heurdata->maxdiveavgquot > 0.0 )
280  searchavgbound = SCIPgetLowerbound(scip)
281  + heurdata->maxdiveavgquot * (SCIPgetAvgLowerbound(scip) - SCIPgetLowerbound(scip));
282  else
283  searchavgbound = SCIPinfinity(scip);
284  searchbound = MIN(searchubbound, searchavgbound);
285  if( SCIPisObjIntegral(scip) )
286  searchbound = SCIPceil(scip, searchbound);
287 
288  /* calculate the maximal diving depth: 10 * min{number of integer variables, max depth} */
289  maxdivedepth = SCIPgetNBinVars(scip) + SCIPgetNIntVars(scip);
290  maxdivedepth = MIN(maxdivedepth, maxdepth);
291  maxdivedepth *= 10;
292 
293  /* get best solution that should guide the search; if this solution lives in the original variable space,
294  * we cannot use it since it might violate the global bounds of the current problem
295  */
296  if( SCIPsolIsOriginal(SCIPgetBestSol(scip)) )
297  return SCIP_OKAY;
298 
299  /* store a copy of the best solution */
300  SCIP_CALL( SCIPcreateSolCopy(scip, &bestsol, SCIPgetBestSol(scip)) );
301 
302  *result = SCIP_DIDNOTFIND;
303 
304  /* start diving */
305  SCIP_CALL( SCIPstartProbing(scip) );
306 
307  /* enables collection of variable statistics during probing */
308  SCIPenableVarHistory(scip);
309 
310  /* get LP objective value */
311  lpsolstat = SCIP_LPSOLSTAT_OPTIMAL;
312  objval = SCIPgetLPObjval(scip);
313 
314  SCIPdebugMessage("(node %"SCIP_LONGINT_FORMAT") executing guideddiving heuristic: depth=%d, %d fractionals, dualbound=%g, searchbound=%g\n",
315  SCIPgetNNodes(scip), SCIPgetDepth(scip), nlpcands, SCIPgetDualbound(scip), SCIPretransformObj(scip, searchbound));
316 
317  /* dive as long we are in the given objective, depth and iteration limits and fractional variables exist, but
318  * - if possible, we dive at least with the depth 10
319  * - if the number of fractional variables decreased at least with 1 variable per 2 dive depths, we continue diving
320  */
321  lperror = FALSE;
322  cutoff = FALSE;
323  divedepth = 0;
324  bestcandmayrounddown = FALSE;
325  bestcandmayroundup = FALSE;
326  startnlpcands = nlpcands;
327  while( !lperror && !cutoff && lpsolstat == SCIP_LPSOLSTAT_OPTIMAL && nlpcands > 0
328  && (divedepth < 10
329  || nlpcands <= startnlpcands - divedepth/2
330  || (divedepth < maxdivedepth && heurdata->nlpiterations < maxnlpiterations && objval < searchbound))
331  && !SCIPisStopped(scip) )
332  {
333  SCIP_CALL( SCIPnewProbingNode(scip) );
334  divedepth++;
335 
336  /* choose variable fixing:
337  * - prefer variables that may not be rounded without destroying LP feasibility:
338  * - of these variables, round a variable to its value in direction of incumbent solution, and choose the
339  * variable that is closest to its rounded value
340  * - if all remaining fractional variables may be rounded without destroying LP feasibility:
341  * - round variable in direction that destroys LP feasibility (other direction is checked by SCIProundSol())
342  * - round variable with least increasing objective value
343  */
344  bestcand = -1;
345  bestobjgain = SCIPinfinity(scip);
346  bestfrac = SCIP_INVALID;
347  bestcandmayrounddown = TRUE;
348  bestcandmayroundup = TRUE;
349  bestcandroundup = FALSE;
350  for( c = 0; c < nlpcands; ++c )
351  {
352  var = lpcands[c];
353  mayrounddown = SCIPvarMayRoundDown(var);
354  mayroundup = SCIPvarMayRoundUp(var);
355  solval = lpcandssol[c];
356  frac = lpcandsfrac[c];
357  obj = SCIPvarGetObj(var);
358  bestsolval = SCIPgetSolVal(scip, bestsol, var);
359 
360  /* select default rounding direction */
361  roundup = (solval < bestsolval);
362 
363  if( mayrounddown || mayroundup )
364  {
365  /* the candidate may be rounded: choose this candidate only, if the best candidate may also be rounded */
366  if( bestcandmayrounddown || bestcandmayroundup )
367  {
368  /* choose rounding direction:
369  * - if variable may be rounded in both directions, round corresponding to its value in incumbent solution
370  * - otherwise, round in the infeasible direction, because feasible direction is tried by rounding
371  * the current fractional solution with SCIProundSol()
372  */
373  if( !mayrounddown || !mayroundup )
374  roundup = mayrounddown;
375 
376  if( roundup )
377  {
378  frac = 1.0 - frac;
379  objgain = frac*obj;
380  }
381  else
382  objgain = -frac*obj;
383 
384  /* penalize too small fractions */
385  if( frac < 0.01 )
386  objgain *= 1000.0;
387 
388  /* prefer decisions on binary variables */
389  if( !SCIPvarIsBinary(var) )
390  objgain *= 1000.0;
391 
392  /* check, if candidate is new best candidate */
393  if( SCIPisLT(scip, objgain, bestobjgain) || (SCIPisEQ(scip, objgain, bestobjgain) && frac < bestfrac) )
394  {
395  bestcand = c;
396  bestobjgain = objgain;
397  bestfrac = frac;
398  bestcandmayrounddown = mayrounddown;
399  bestcandmayroundup = mayroundup;
400  bestcandroundup = roundup;
401  }
402  }
403  }
404  else
405  {
406  /* the candidate may not be rounded */
407  if( roundup )
408  frac = 1.0 - frac;
409 
410  /* penalize too small fractions */
411  if( frac < 0.01 )
412  frac += 10.0;
413 
414  /* prefer decisions on binary variables */
415  if( !SCIPvarIsBinary(var) )
416  frac *= 1000.0;
417 
418  /* check, if candidate is new best candidate: prefer unroundable candidates in any case */
419  if( bestcandmayrounddown || bestcandmayroundup || frac < bestfrac )
420  {
421  bestcand = c;
422  bestfrac = frac;
423  bestcandmayrounddown = FALSE;
424  bestcandmayroundup = FALSE;
425  bestcandroundup = roundup;
426  }
427  }
428  }
429  assert(bestcand != -1);
430 
431  /* if all candidates are roundable, try to round the solution */
432  if( bestcandmayrounddown || bestcandmayroundup )
433  {
434  SCIP_Bool success;
435 
436  /* create solution from diving LP and try to round it */
437  SCIP_CALL( SCIPlinkLPSol(scip, heurdata->sol) );
438  SCIP_CALL( SCIProundSol(scip, heurdata->sol, &success) );
439 
440  if( success )
441  {
442  SCIPdebugMessage("guideddiving found roundable primal solution: obj=%g\n", SCIPgetSolOrigObj(scip, heurdata->sol));
443 
444  /* try to add solution to SCIP */
445  SCIP_CALL( SCIPtrySol(scip, heurdata->sol, FALSE, FALSE, FALSE, FALSE, &success) );
446 
447  /* check, if solution was feasible and good enough */
448  if( success )
449  {
450  SCIPdebugMessage(" -> solution was feasible and good enough\n");
451  *result = SCIP_FOUNDSOL;
452  }
453  }
454  }
455 
456  var = lpcands[bestcand];
457 
458  backtracked = FALSE;
459  do
460  {
461  /* if the variable is already fixed or if the solution value is outside the domain, numerical troubles may have
462  * occured or variable was fixed by propagation while backtracking => Abort diving!
463  */
464  if( SCIPvarGetLbLocal(var) >= SCIPvarGetUbLocal(var) - 0.5 )
465  {
466  SCIPdebugMessage("Selected variable <%s> already fixed to [%g,%g] (solval: %.9f), diving aborted \n",
467  SCIPvarGetName(var), SCIPvarGetLbLocal(var), SCIPvarGetUbLocal(var), lpcandssol[bestcand]);
468  cutoff = TRUE;
469  break;
470  }
471  if( SCIPisFeasLT(scip, lpcandssol[bestcand], SCIPvarGetLbLocal(var)) || SCIPisFeasGT(scip, lpcandssol[bestcand], SCIPvarGetUbLocal(var)) )
472  {
473  SCIPdebugMessage("selected variable's <%s> solution value is outside the domain [%g,%g] (solval: %.9f), diving aborted\n",
474  SCIPvarGetName(var), SCIPvarGetLbLocal(var), SCIPvarGetUbLocal(var), lpcandssol[bestcand]);
475  assert(backtracked);
476  break;
477  }
478 
479  /* apply rounding of best candidate */
480  if( bestcandroundup == !backtracked )
481  {
482  /* round variable up */
483  SCIPdebugMessage(" dive %d/%d, LP iter %"SCIP_LONGINT_FORMAT"/%"SCIP_LONGINT_FORMAT": var <%s>, round=%u/%u, sol=%g, bestsol=%g, oldbounds=[%g,%g], newbounds=[%g,%g]\n",
484  divedepth, maxdivedepth, heurdata->nlpiterations, maxnlpiterations,
485  SCIPvarGetName(var), bestcandmayrounddown, bestcandmayroundup,
486  lpcandssol[bestcand], SCIPgetSolVal(scip, bestsol, var),
487  SCIPvarGetLbLocal(var), SCIPvarGetUbLocal(var),
488  SCIPfeasCeil(scip, lpcandssol[bestcand]), SCIPvarGetUbLocal(var));
489  SCIP_CALL( SCIPchgVarLbProbing(scip, var, SCIPfeasCeil(scip, lpcandssol[bestcand])) );
490  }
491  else
492  {
493  /* round variable down */
494  SCIPdebugMessage(" dive %d/%d, LP iter %"SCIP_LONGINT_FORMAT"/%"SCIP_LONGINT_FORMAT": var <%s>, round=%u/%u, sol=%g, bestsol=%g, oldbounds=[%g,%g], newbounds=[%g,%g]\n",
495  divedepth, maxdivedepth, heurdata->nlpiterations, maxnlpiterations,
496  SCIPvarGetName(var), bestcandmayrounddown, bestcandmayroundup,
497  lpcandssol[bestcand], SCIPgetSolVal(scip, bestsol, var),
498  SCIPvarGetLbLocal(var), SCIPvarGetUbLocal(var),
499  SCIPvarGetLbLocal(var), SCIPfeasFloor(scip, lpcandssol[bestcand]));
500  SCIP_CALL( SCIPchgVarUbProbing(scip, var, SCIPfeasFloor(scip, lpcandssol[bestcand])) );
501  }
502 
503  /* apply domain propagation */
504  SCIP_CALL( SCIPpropagateProbing(scip, 0, &cutoff, NULL) );
505  if( !cutoff )
506  {
507  /* resolve the diving LP */
508  /* Errors in the LP solver should not kill the overall solving process, if the LP is just needed for a heuristic.
509  * Hence in optimized mode, the return code is caught and a warning is printed, only in debug mode, SCIP will stop.
510  */
511 #ifdef NDEBUG
512  SCIP_RETCODE retstat;
513  nlpiterations = SCIPgetNLPIterations(scip);
514  retstat = SCIPsolveProbingLP(scip, MAX((int)(maxnlpiterations - heurdata->nlpiterations), MINLPITER), &lperror, &cutoff);
515  if( retstat != SCIP_OKAY )
516  {
517  SCIPwarningMessage(scip, "Error while solving LP in Guideddiving heuristic; LP solve terminated with code <%d>\n",retstat);
518  }
519 #else
520  nlpiterations = SCIPgetNLPIterations(scip);
521  SCIP_CALL( SCIPsolveProbingLP(scip, MAX((int)(maxnlpiterations - heurdata->nlpiterations), MINLPITER), &lperror, &cutoff) );
522 #endif
523 
524  if( lperror )
525  break;
526 
527  /* update iteration count */
528  heurdata->nlpiterations += SCIPgetNLPIterations(scip) - nlpiterations;
529 
530  /* get LP solution status, objective value, and fractional variables, that should be integral */
531  lpsolstat = SCIPgetLPSolstat(scip);
532  assert(cutoff || (lpsolstat != SCIP_LPSOLSTAT_OBJLIMIT && lpsolstat != SCIP_LPSOLSTAT_INFEASIBLE &&
533  (lpsolstat != SCIP_LPSOLSTAT_OPTIMAL || SCIPisLT(scip, SCIPgetLPObjval(scip), SCIPgetCutoffbound(scip)))));
534  }
535 
536  /* perform backtracking if a cutoff was detected */
537  if( cutoff && !backtracked && heurdata->backtrack )
538  {
539  SCIPdebugMessage(" *** cutoff detected at level %d - backtracking\n", SCIPgetProbingDepth(scip));
540  SCIP_CALL( SCIPbacktrackProbing(scip, SCIPgetProbingDepth(scip)-1) );
541  SCIP_CALL( SCIPnewProbingNode(scip) );
542  backtracked = TRUE;
543  }
544  else
545  backtracked = FALSE;
546  }
547  while( backtracked );
548 
549  if( !lperror && !cutoff && lpsolstat == SCIP_LPSOLSTAT_OPTIMAL )
550  {
551  /* get new objective value */
552  oldobjval = objval;
553  objval = SCIPgetLPObjval(scip);
554 
555  /* update pseudo cost values */
556  if( SCIPisGT(scip, objval, oldobjval) )
557  {
558  if( bestcandroundup )
559  {
560  SCIP_CALL( SCIPupdateVarPseudocost(scip, lpcands[bestcand], 1.0-lpcandsfrac[bestcand],
561  objval - oldobjval, 1.0) );
562  }
563  else
564  {
565  SCIP_CALL( SCIPupdateVarPseudocost(scip, lpcands[bestcand], 0.0-lpcandsfrac[bestcand],
566  objval - oldobjval, 1.0) );
567  }
568  }
569 
570  /* get new fractional variables */
571  SCIP_CALL( SCIPgetLPBranchCands(scip, &lpcands, &lpcandssol, &lpcandsfrac, &nlpcands, NULL, NULL) );
572  }
573  SCIPdebugMessage(" -> lpsolstat=%d, objval=%g, nfrac=%d\n", lpsolstat, objval, nlpcands);
574  }
575 
576  /* check if a solution has been found */
577  if( nlpcands == 0 && !lperror && !cutoff && lpsolstat == SCIP_LPSOLSTAT_OPTIMAL )
578  {
579  SCIP_Bool success;
580 
581  /* create solution from diving LP */
582  SCIP_CALL( SCIPlinkLPSol(scip, heurdata->sol) );
583  SCIPdebugMessage("guideddiving found primal solution: obj=%g\n", SCIPgetSolOrigObj(scip, heurdata->sol));
584 
585  /* try to add solution to SCIP */
586  SCIP_CALL( SCIPtrySol(scip, heurdata->sol, FALSE, FALSE, FALSE, FALSE, &success) );
587 
588  /* check, if solution was feasible and good enough */
589  if( success )
590  {
591  SCIPdebugMessage(" -> solution was feasible and good enough\n");
592  *result = SCIP_FOUNDSOL;
593  }
594  }
595 
596  /* end diving */
597  SCIP_CALL( SCIPendProbing(scip) );
598 
599  /* free copied best solution */
600  SCIP_CALL( SCIPfreeSol(scip, &bestsol) );
601 
602  if( *result == SCIP_FOUNDSOL )
603  heurdata->nsuccess++;
604 
605  SCIPdebugMessage("guideddiving heuristic finished\n");
606 
607  return SCIP_OKAY;
608 }
609 
610 
611 /*
612  * heuristic specific interface methods
613  */
614 
615 /** creates the guideddiving heuristic and includes it in SCIP */
616 SCIP_RETCODE SCIPincludeHeurGuideddiving(
617  SCIP* scip /**< SCIP data structure */
618  )
619 {
620  SCIP_HEURDATA* heurdata;
621  SCIP_HEUR* heur;
622 
623  /* create Guideddiving primal heuristic data */
624  SCIP_CALL( SCIPallocMemory(scip, &heurdata) );
625 
626  /* include primal heuristic */
627  SCIP_CALL( SCIPincludeHeurBasic(scip, &heur,
628  HEUR_NAME, HEUR_DESC, HEUR_DISPCHAR, HEUR_PRIORITY, HEUR_FREQ, HEUR_FREQOFS,
629  HEUR_MAXDEPTH, HEUR_TIMING, HEUR_USESSUBSCIP, heurExecGuideddiving, heurdata) );
630 
631  assert(heur != NULL);
632 
633  /* set non-NULL pointers to callback methods */
634  SCIP_CALL( SCIPsetHeurCopy(scip, heur, heurCopyGuideddiving) );
635  SCIP_CALL( SCIPsetHeurFree(scip, heur, heurFreeGuideddiving) );
636  SCIP_CALL( SCIPsetHeurInit(scip, heur, heurInitGuideddiving) );
637  SCIP_CALL( SCIPsetHeurExit(scip, heur, heurExitGuideddiving) );
638 
639  /* guideddiving heuristic parameters */
640  SCIP_CALL( SCIPaddRealParam(scip,
641  "heuristics/guideddiving/minreldepth",
642  "minimal relative depth to start diving",
643  &heurdata->minreldepth, TRUE, DEFAULT_MINRELDEPTH, 0.0, 1.0, NULL, NULL) );
644  SCIP_CALL( SCIPaddRealParam(scip,
645  "heuristics/guideddiving/maxreldepth",
646  "maximal relative depth to start diving",
647  &heurdata->maxreldepth, TRUE, DEFAULT_MAXRELDEPTH, 0.0, 1.0, NULL, NULL) );
648  SCIP_CALL( SCIPaddRealParam(scip,
649  "heuristics/guideddiving/maxlpiterquot",
650  "maximal fraction of diving LP iterations compared to node LP iterations",
651  &heurdata->maxlpiterquot, FALSE, DEFAULT_MAXLPITERQUOT, 0.0, SCIP_REAL_MAX, NULL, NULL) );
652  SCIP_CALL( SCIPaddIntParam(scip,
653  "heuristics/guideddiving/maxlpiterofs",
654  "additional number of allowed LP iterations",
655  &heurdata->maxlpiterofs, FALSE, DEFAULT_MAXLPITEROFS, 0, INT_MAX, NULL, NULL) );
656  SCIP_CALL( SCIPaddRealParam(scip,
657  "heuristics/guideddiving/maxdiveubquot",
658  "maximal quotient (curlowerbound - lowerbound)/(cutoffbound - lowerbound) where diving is performed (0.0: no limit)",
659  &heurdata->maxdiveubquot, TRUE, DEFAULT_MAXDIVEUBQUOT, 0.0, 1.0, NULL, NULL) );
660  SCIP_CALL( SCIPaddRealParam(scip,
661  "heuristics/guideddiving/maxdiveavgquot",
662  "maximal quotient (curlowerbound - lowerbound)/(avglowerbound - lowerbound) where diving is performed (0.0: no limit)",
663  &heurdata->maxdiveavgquot, TRUE, DEFAULT_MAXDIVEAVGQUOT, 0.0, SCIP_REAL_MAX, NULL, NULL) );
664  SCIP_CALL( SCIPaddBoolParam(scip,
665  "heuristics/guideddiving/backtrack",
666  "use one level of backtracking if infeasibility is encountered?",
667  &heurdata->backtrack, FALSE, DEFAULT_BACKTRACK, NULL, NULL) );
668 
669  return SCIP_OKAY;
670 }
671 
672