Scippy

SCIP

Solving Constraint Integer Programs

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