Scippy

SCIP

Solving Constraint Integer Programs

heur_intdiving.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-2019 Konrad-Zuse-Zentrum */
7 /* fuer Informationstechnik Berlin */
8 /* */
9 /* SCIP is distributed under the terms of the ZIB Academic License. */
10 /* */
11 /* You should have received a copy of the ZIB Academic License */
12 /* along with SCIP; see the file COPYING. If not visit scip.zib.de. */
13 /* */
14 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
15 
16 /**@file heur_intdiving.c
17  * @brief LP diving heuristic that fixes variables with integral LP value
18  * @author Tobias Achterberg
19  */
20 
21 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
22 
23 #include "blockmemshell/memory.h"
24 #include "scip/heur_intdiving.h"
25 #include "scip/pub_heur.h"
26 #include "scip/pub_lp.h"
27 #include "scip/pub_message.h"
28 #include "scip/pub_var.h"
29 #include "scip/scip_branch.h"
30 #include "scip/scip_general.h"
31 #include "scip/scip_heur.h"
32 #include "scip/scip_lp.h"
33 #include "scip/scip_mem.h"
34 #include "scip/scip_message.h"
35 #include "scip/scip_numerics.h"
36 #include "scip/scip_param.h"
37 #include "scip/scip_prob.h"
38 #include "scip/scip_probing.h"
39 #include "scip/scip_sol.h"
40 #include "scip/scip_solvingstats.h"
41 #include "scip/scip_tree.h"
42 #include "scip/scip_var.h"
43 #include <string.h>
44 
45 #define HEUR_NAME "intdiving"
46 #define HEUR_DESC "LP diving heuristic that fixes binary variables with large LP value to one"
47 #define HEUR_DISPCHAR 'n'
48 #define HEUR_PRIORITY -1003500
49 #define HEUR_FREQ -1
50 #define HEUR_FREQOFS 9
51 #define HEUR_MAXDEPTH -1
52 #define HEUR_TIMING SCIP_HEURTIMING_AFTERLPPLUNGE
53 #define HEUR_USESSUBSCIP FALSE /**< does the heuristic use a secondary SCIP instance? */
54 
55 
56 /*
57  * Default parameter settings
58  */
59 
60 #define DEFAULT_MINRELDEPTH 0.0 /**< minimal relative depth to start diving */
61 #define DEFAULT_MAXRELDEPTH 1.0 /**< maximal relative depth to start diving */
62 #define DEFAULT_MAXLPITERQUOT 0.05 /**< maximal fraction of diving LP iterations compared to node LP iterations */
63 #define DEFAULT_MAXLPITEROFS 1000 /**< additional number of allowed LP iterations */
64 #define DEFAULT_MAXDIVEUBQUOT 0.8 /**< maximal quotient (curlowerbound - lowerbound)/(cutoffbound - lowerbound)
65  * where diving is performed (0.0: no limit) */
66 #define DEFAULT_MAXDIVEAVGQUOT 0.0 /**< maximal quotient (curlowerbound - lowerbound)/(avglowerbound - lowerbound)
67  * where diving is performed (0.0: no limit) */
68 #define DEFAULT_MAXDIVEUBQUOTNOSOL 0.1 /**< maximal UBQUOT when no solution was found yet (0.0: no limit) */
69 #define DEFAULT_MAXDIVEAVGQUOTNOSOL 0.0 /**< maximal AVGQUOT when no solution was found yet (0.0: no limit) */
70 #define DEFAULT_BACKTRACK TRUE /**< use one level of backtracking if infeasibility is encountered? */
71 
72 #define MINLPITER 10000 /**< minimal number of LP iterations allowed in each LP solving call */
73 
74 
75 /* locally defined heuristic data */
76 struct SCIP_HeurData
77 {
78  SCIP_SOL* sol; /**< working solution */
79  SCIP_Real minreldepth; /**< minimal relative depth to start diving */
80  SCIP_Real maxreldepth; /**< maximal relative depth to start diving */
81  SCIP_Real maxlpiterquot; /**< maximal fraction of diving LP iterations compared to node LP iterations */
82  int maxlpiterofs; /**< additional number of allowed LP iterations */
83  SCIP_Real maxdiveubquot; /**< maximal quotient (curlowerbound - lowerbound)/(cutoffbound - lowerbound)
84  * where diving is performed (0.0: no limit) */
85  SCIP_Real maxdiveavgquot; /**< maximal quotient (curlowerbound - lowerbound)/(avglowerbound - lowerbound)
86  * where diving is performed (0.0: no limit) */
87  SCIP_Real maxdiveubquotnosol; /**< maximal UBQUOT when no solution was found yet (0.0: no limit) */
88  SCIP_Real maxdiveavgquotnosol;/**< maximal AVGQUOT when no solution was found yet (0.0: no limit) */
89  SCIP_Bool backtrack; /**< use one level of backtracking if infeasibility is encountered? */
90  SCIP_Longint nlpiterations; /**< LP iterations used in this heuristic */
91  int nsuccess; /**< number of runs that produced at least one feasible solution */
92 };
93 
94 
95 /*
96  * local methods
97  */
98 
99 
100 /*
101  * Callback methods
102  */
103 
104 /** copy method for primal heuristic plugins (called when SCIP copies plugins) */
105 static
106 SCIP_DECL_HEURCOPY(heurCopyIntdiving)
107 { /*lint --e{715}*/
108  assert(scip != NULL);
109  assert(heur != NULL);
110  assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0);
111 
112  /* call inclusion method of primal heuristic */
114 
115  return SCIP_OKAY;
116 }
117 
118 /** destructor of primal heuristic to free user data (called when SCIP is exiting) */
119 static
120 SCIP_DECL_HEURFREE(heurFreeIntdiving) /*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  assert(scip != NULL);
127 
128  /* free heuristic data */
129  heurdata = SCIPheurGetData(heur);
130  assert(heurdata != NULL);
131  SCIPfreeBlockMemory(scip, &heurdata);
132  SCIPheurSetData(heur, NULL);
133 
134  return SCIP_OKAY;
135 }
136 
137 
138 /** initialization method of primal heuristic (called after problem was transformed) */
139 static
140 SCIP_DECL_HEURINIT(heurInitIntdiving) /*lint --e{715}*/
141 { /*lint --e{715}*/
142  SCIP_HEURDATA* heurdata;
143 
144  assert(heur != NULL);
145  assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0);
146 
147  /* get heuristic data */
148  heurdata = SCIPheurGetData(heur);
149  assert(heurdata != NULL);
150 
151  /* create working solution */
152  SCIP_CALL( SCIPcreateSol(scip, &heurdata->sol, heur) );
153 
154  /* initialize data */
155  heurdata->nlpiterations = 0;
156  heurdata->nsuccess = 0;
157 
158  return SCIP_OKAY;
159 }
160 
161 
162 /** deinitialization method of primal heuristic (called before transformed problem is freed) */
163 static
164 SCIP_DECL_HEUREXIT(heurExitIntdiving) /*lint --e{715}*/
165 { /*lint --e{715}*/
166  SCIP_HEURDATA* heurdata;
167 
168  assert(heur != NULL);
169  assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0);
170 
171  /* get heuristic data */
172  heurdata = SCIPheurGetData(heur);
173  assert(heurdata != NULL);
174 
175  /* free working solution */
176  SCIP_CALL( SCIPfreeSol(scip, &heurdata->sol) );
177 
178  return SCIP_OKAY;
179 }
180 
181 
182 /** execution method of primal heuristic */
183 static
184 SCIP_DECL_HEUREXEC(heurExecIntdiving) /*lint --e{715}*/
185 { /*lint --e{715}*/
186  SCIP_HEURDATA* heurdata;
187  SCIP_LPSOLSTAT lpsolstat;
188  SCIP_VAR** pseudocands;
189  SCIP_VAR** fixcands;
190  SCIP_Real* fixcandscores;
191  SCIP_Real searchubbound;
192  SCIP_Real searchavgbound;
193  SCIP_Real searchbound;
194  SCIP_Real objval;
195  SCIP_Bool lperror;
196  SCIP_Bool cutoff;
197  SCIP_Bool backtracked;
198  SCIP_Longint ncalls;
199  SCIP_Longint nsolsfound;
200  SCIP_Longint nlpiterations;
201  SCIP_Longint maxnlpiterations;
202  int nfixcands;
203  int nbinfixcands;
204  int depth;
205  int maxdepth;
206  int maxdivedepth;
207  int divedepth;
208  int nextcand;
209  int c;
210 
211  assert(heur != NULL);
212  assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0);
213  assert(scip != NULL);
214  assert(result != NULL);
215  assert(SCIPhasCurrentNodeLP(scip));
216 
217  *result = SCIP_DELAYED;
218 
219  /* do not call heuristic of node was already detected to be infeasible */
220  if( nodeinfeasible )
221  return SCIP_OKAY;
222 
223  /* only call heuristic, if an optimal LP solution is at hand */
225  return SCIP_OKAY;
226 
227  /* only call heuristic, if the LP objective value is smaller than the cutoff bound */
229  return SCIP_OKAY;
230 
231  /* only call heuristic, if the LP solution is basic (which allows fast resolve in diving) */
232  if( !SCIPisLPSolBasic(scip) )
233  return SCIP_OKAY;
234 
235  /* don't dive two times at the same node */
237  return SCIP_OKAY;
238 
239  *result = SCIP_DIDNOTRUN;
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, 100);
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 unfixed integer variables */
267  SCIP_CALL( SCIPgetPseudoBranchCands(scip, &pseudocands, &nfixcands, NULL) );
268 
269  /* don't try to dive, if there are no fractional variables */
270  if( nfixcands == 0 )
271  return SCIP_OKAY;
272 
273  /* calculate the objective search bound */
274  if( SCIPgetNSolsFound(scip) == 0 )
275  {
276  if( heurdata->maxdiveubquotnosol > 0.0 )
277  searchubbound = SCIPgetLowerbound(scip)
278  + heurdata->maxdiveubquotnosol * (SCIPgetCutoffbound(scip) - SCIPgetLowerbound(scip));
279  else
280  searchubbound = SCIPinfinity(scip);
281  if( heurdata->maxdiveavgquotnosol > 0.0 )
282  searchavgbound = SCIPgetLowerbound(scip)
283  + heurdata->maxdiveavgquotnosol * (SCIPgetAvgLowerbound(scip) - SCIPgetLowerbound(scip));
284  else
285  searchavgbound = SCIPinfinity(scip);
286  }
287  else
288  {
289  if( heurdata->maxdiveubquot > 0.0 )
290  searchubbound = SCIPgetLowerbound(scip)
291  + heurdata->maxdiveubquot * (SCIPgetCutoffbound(scip) - SCIPgetLowerbound(scip));
292  else
293  searchubbound = SCIPinfinity(scip);
294  if( heurdata->maxdiveavgquot > 0.0 )
295  searchavgbound = SCIPgetLowerbound(scip)
296  + heurdata->maxdiveavgquot * (SCIPgetAvgLowerbound(scip) - SCIPgetLowerbound(scip));
297  else
298  searchavgbound = SCIPinfinity(scip);
299  }
300  searchbound = MIN(searchubbound, searchavgbound);
301  if( SCIPisObjIntegral(scip) )
302  searchbound = SCIPceil(scip, searchbound);
303 
304  /* calculate the maximal diving depth: 10 * min{number of integer variables, max depth} */
305  maxdivedepth = SCIPgetNBinVars(scip) + SCIPgetNIntVars(scip);
306  maxdivedepth = MIN(maxdivedepth, maxdepth);
307  maxdivedepth *= 10;
308 
309  *result = SCIP_DIDNOTFIND;
310 
311  /* start diving */
313 
314  /* enables collection of variable statistics during probing */
316 
317  SCIPdebugMsg(scip, "(node %" SCIP_LONGINT_FORMAT ") executing intdiving heuristic: depth=%d, %d non-fixed, dualbound=%g, searchbound=%g\n",
319 
320  /* copy the pseudo candidates into own array, because we want to reorder them */
321  SCIP_CALL( SCIPduplicateBufferArray(scip, &fixcands, pseudocands, nfixcands) );
322 
323  /* sort non-fixed variables by non-increasing inference score, but prefer binaries over integers in any case */
324  SCIP_CALL( SCIPallocBufferArray(scip, &fixcandscores, nfixcands) );
325  nbinfixcands = 0;
326  for( c = 0; c < nfixcands; ++c )
327  {
328  SCIP_VAR* var;
329  SCIP_Real score;
330  int colveclen;
331  int left;
332  int right;
333  int i;
334 
335  assert(c >= nbinfixcands);
336  var = fixcands[c];
337  assert(SCIPvarIsIntegral(var));
338  colveclen = (SCIPvarGetStatus(var) == SCIP_VARSTATUS_COLUMN ? SCIPcolGetNNonz(SCIPvarGetCol(var)) : 0);
339  if( SCIPvarIsBinary(var) )
340  {
341  score = 500.0 * SCIPvarGetNCliques(var, TRUE) + 100.0 * SCIPvarGetNImpls(var, TRUE)
342  + SCIPgetVarAvgInferenceScore(scip, var) + (SCIP_Real)colveclen/100.0;
343 
344  /* shift the non-binary variables one slot to the right */
345  for( i = c; i > nbinfixcands; --i )
346  {
347  fixcands[i] = fixcands[i-1];
348  fixcandscores[i] = fixcandscores[i-1];
349  }
350  /* put the new candidate into the first nbinfixcands slot */
351  left = 0;
352  right = nbinfixcands;
353  nbinfixcands++;
354  }
355  else
356  {
357  score = 5.0 * (SCIPvarGetNCliques(var, FALSE) + SCIPvarGetNCliques(var, TRUE))
359  + (SCIP_Real)colveclen/10000.0;
360 
361  /* put the new candidate in the slots after the binary candidates */
362  left = nbinfixcands;
363  right = c;
364  }
365  for( i = right; i > left && score > fixcandscores[i-1]; --i )
366  {
367  fixcands[i] = fixcands[i-1];
368  fixcandscores[i] = fixcandscores[i-1];
369  }
370  fixcands[i] = var;
371  fixcandscores[i] = score;
372  SCIPdebugMsg(scip, " <%s>: ncliques=%d/%d, nimpls=%d/%d, inferencescore=%g, colveclen=%d -> score=%g\n",
375  colveclen, score);
376  }
377  SCIPfreeBufferArray(scip, &fixcandscores);
378 
379  /* get LP objective value */
380  lpsolstat = SCIP_LPSOLSTAT_OPTIMAL;
381  objval = SCIPgetLPObjval(scip);
382 
383  /* dive as long we are in the given objective, depth and iteration limits, but if possible, we dive at least with
384  * the depth 10
385  */
386  lperror = FALSE;
387  cutoff = FALSE;
388  divedepth = 0;
389  nextcand = 0;
390  while( !lperror && !cutoff && lpsolstat == SCIP_LPSOLSTAT_OPTIMAL
391  && (divedepth < 10
392  || (divedepth < maxdivedepth && heurdata->nlpiterations < maxnlpiterations && objval < searchbound))
393  && !SCIPisStopped(scip) )
394  {
395  SCIP_VAR* var;
396  SCIP_Real bestsolval;
397  SCIP_Real bestfixval;
398  int bestcand;
399  SCIP_Longint nnewlpiterations;
400  SCIP_Longint nnewdomreds;
401 
402  /* open a new probing node if this will not exceed the maximal tree depth, otherwise stop here */
404  {
406  divedepth++;
407  }
408  else
409  break;
410 
411  nnewlpiterations = 0;
412  nnewdomreds = 0;
413 
414  /* fix binary variable that is closest to 1 in the LP solution to 1;
415  * if all binary variables are fixed, fix integer variable with least fractionality in LP solution
416  */
417  bestcand = -1;
418  bestsolval = -1.0;
419  bestfixval = 1.0;
420 
421  /* look in the binary variables for fixing candidates */
422  for( c = nextcand; c < nbinfixcands; ++c )
423  {
424  SCIP_Real solval;
425 
426  var = fixcands[c];
427 
428  /* ignore already fixed variables */
429  if( var == NULL )
430  continue;
431  if( SCIPvarGetLbLocal(var) > 0.5 || SCIPvarGetUbLocal(var) < 0.5 )
432  {
433  fixcands[c] = NULL;
434  continue;
435  }
436 
437  /* get the LP solution value */
438  solval = SCIPvarGetLPSol(var);
439 
440  if( solval > bestsolval )
441  {
442  bestcand = c;
443  bestfixval = 1.0;
444  bestsolval = solval;
445  if( SCIPisGE(scip, bestsolval, 1.0) )
446  {
447  /* we found an unfixed binary variable with LP solution value of 1.0 - there cannot be a better candidate */
448  break;
449  }
450  else if( SCIPisLE(scip, bestsolval, 0.0) )
451  {
452  /* the variable is currently at 0.0 - this is the only situation where we want to fix it to 0.0 */
453  bestfixval = 0.0;
454  }
455  }
456  }
457 
458  /* if all binary variables are fixed, look in the integer variables for a fixing candidate */
459  if( bestcand == -1 )
460  {
461  SCIP_Real bestfrac;
462 
463  bestfrac = SCIP_INVALID;
464  for( c = MAX(nextcand, nbinfixcands); c < nfixcands; ++c )
465  {
466  SCIP_Real solval;
467  SCIP_Real frac;
468 
469  var = fixcands[c];
470 
471  /* ignore already fixed variables */
472  if( var == NULL )
473  continue;
474  if( SCIPvarGetUbLocal(var) - SCIPvarGetLbLocal(var) < 0.5 )
475  {
476  fixcands[c] = NULL;
477  continue;
478  }
479 
480  /* get the LP solution value */
481  solval = SCIPvarGetLPSol(var);
482  frac = SCIPfrac(scip, solval);
483 
484  /* ignore integer variables that are currently integral */
485  if( SCIPisFeasFracIntegral(scip, frac) )
486  continue;
487 
488  if( frac < bestfrac )
489  {
490  bestcand = c;
491  bestsolval = solval;
492  bestfrac = frac;
493  bestfixval = SCIPfloor(scip, bestsolval + 0.5);
494  if( SCIPisZero(scip, bestfrac) )
495  {
496  /* we found an unfixed integer variable with integral LP solution value */
497  break;
498  }
499  }
500  }
501  }
502  assert(-1 <= bestcand && bestcand < nfixcands);
503 
504  /* if there is no unfixed candidate left, we are done */
505  if( bestcand == -1 )
506  break;
507 
508  var = fixcands[bestcand];
509  assert(var != NULL);
510  assert(SCIPvarIsIntegral(var));
511  assert(SCIPvarGetUbLocal(var) - SCIPvarGetLbLocal(var) > 0.5);
512  assert(SCIPisGE(scip, bestfixval, SCIPvarGetLbLocal(var)));
513  assert(SCIPisLE(scip, bestfixval, SCIPvarGetUbLocal(var)));
514 
515  backtracked = FALSE;
516  do
517  {
518  /* if the variable is already fixed or if the solution value is outside the domain, numerical troubles may have
519  * occured or variable was fixed by propagation while backtracking => Abort diving!
520  */
521  if( SCIPvarGetLbLocal(var) >= SCIPvarGetUbLocal(var) - 0.5 )
522  {
523  SCIPdebugMsg(scip, "Selected variable <%s> already fixed to [%g,%g], diving aborted \n",
525  cutoff = TRUE;
526  break;
527  }
528  if( SCIPisFeasLT(scip, bestfixval, SCIPvarGetLbLocal(var)) || SCIPisFeasGT(scip, bestfixval, SCIPvarGetUbLocal(var)) )
529  {
530  SCIPdebugMsg(scip, "selected variable's <%s> solution value is outside the domain [%g,%g] (solval: %.9f), diving aborted\n",
531  SCIPvarGetName(var), SCIPvarGetLbLocal(var), SCIPvarGetUbLocal(var), bestfixval);
532  assert(backtracked);
533  break;
534  }
535 
536  /* apply fixing of best candidate */
537  SCIPdebugMsg(scip, " dive %d/%d, LP iter %" SCIP_LONGINT_FORMAT "/%" SCIP_LONGINT_FORMAT ", %d unfixed: var <%s>, sol=%g, oldbounds=[%g,%g], fixed to %g\n",
538  divedepth, maxdivedepth, heurdata->nlpiterations, maxnlpiterations, SCIPgetNPseudoBranchCands(scip),
539  SCIPvarGetName(var), bestsolval, SCIPvarGetLbLocal(var), SCIPvarGetUbLocal(var), bestfixval);
540  SCIP_CALL( SCIPfixVarProbing(scip, var, bestfixval) );
541 
542  /* apply domain propagation */
543  SCIP_CALL( SCIPpropagateProbing(scip, 0, &cutoff, &nnewdomreds) );
544  if( !cutoff )
545  {
546  /* if the best candidate was just fixed to its LP value and no domain reduction was found, the LP solution
547  * stays valid, and the LP does not need to be resolved
548  */
549  if( nnewdomreds > 0 || !SCIPisEQ(scip, bestsolval, bestfixval) )
550  {
551  /* resolve the diving LP */
552  /* Errors in the LP solver should not kill the overall solving process, if the LP is just needed for a heuristic.
553  * Hence in optimized mode, the return code is caught and a warning is printed, only in debug mode, SCIP will stop.
554  */
555 #ifdef NDEBUG
556  SCIP_RETCODE retstat;
557  nlpiterations = SCIPgetNLPIterations(scip);
558  retstat = SCIPsolveProbingLP(scip, MAX((int)(maxnlpiterations - heurdata->nlpiterations), MINLPITER), &lperror, &cutoff);
559  if( retstat != SCIP_OKAY )
560  {
561  SCIPwarningMessage(scip, "Error while solving LP in Intdiving heuristic; LP solve terminated with code <%d>\n",retstat);
562  }
563 #else
564  nlpiterations = SCIPgetNLPIterations(scip);
565  SCIP_CALL( SCIPsolveProbingLP(scip, MAX((int)(maxnlpiterations - heurdata->nlpiterations), MINLPITER), &lperror, &cutoff) );
566 #endif
567 
568  if( lperror )
569  break;
570 
571  /* update iteration count */
572  nnewlpiterations = SCIPgetNLPIterations(scip) - nlpiterations;
573  heurdata->nlpiterations += nnewlpiterations;
574 
575  /* get LP solution status */
576  lpsolstat = SCIPgetLPSolstat(scip);
577  assert(cutoff || (lpsolstat != SCIP_LPSOLSTAT_OBJLIMIT && lpsolstat != SCIP_LPSOLSTAT_INFEASIBLE &&
579  }
580  }
581 
582  /* perform backtracking if a cutoff was detected */
583  if( cutoff && !backtracked && heurdata->backtrack )
584  {
585  SCIPdebugMsg(scip, " *** cutoff detected at level %d - backtracking\n", SCIPgetProbingDepth(scip));
587 
588  /* after backtracking there has to be at least one open node without exceeding the maximal tree depth */
590 
592 
593  bestfixval = SCIPvarIsBinary(var)
594  ? 1.0 - bestfixval
595  : (SCIPisGT(scip, bestsolval, bestfixval) && SCIPisFeasLE(scip, bestfixval + 1, SCIPvarGetUbLocal(var)) ? bestfixval + 1 : bestfixval - 1);
596 
597  backtracked = TRUE;
598  }
599  else
600  backtracked = FALSE;
601  }
602  while( backtracked );
603 
604  if( !lperror && !cutoff && lpsolstat == SCIP_LPSOLSTAT_OPTIMAL )
605  {
606  SCIP_Bool success;
607 
608  /* get new objective value */
609  objval = SCIPgetLPObjval(scip);
610 
611  if( nnewlpiterations > 0 || !SCIPisEQ(scip, bestsolval, bestfixval) )
612  {
613  /* we must start again with the first candidate, since the LP solution changed */
614  nextcand = 0;
615 
616  /* create solution from diving LP and try to round it */
617  SCIP_CALL( SCIPlinkLPSol(scip, heurdata->sol) );
618  SCIP_CALL( SCIProundSol(scip, heurdata->sol, &success) );
619  if( success )
620  {
621  SCIPdebugMsg(scip, "intdiving found roundable primal solution: obj=%g\n",
622  SCIPgetSolOrigObj(scip, heurdata->sol));
623 
624  /* try to add solution to SCIP */
625  SCIP_CALL( SCIPtrySol(scip, heurdata->sol, FALSE, FALSE, FALSE, FALSE, FALSE, &success) );
626 
627  /* check, if solution was feasible and good enough */
628  if( success )
629  {
630  SCIPdebugMsg(scip, " -> solution was feasible and good enough\n");
631  *result = SCIP_FOUNDSOL;
632  }
633  }
634  }
635  else
636  nextcand = bestcand+1; /* continue with the next candidate in the following loop */
637  }
638  SCIPdebugMsg(scip, " -> lpsolstat=%d, objval=%g/%g\n", lpsolstat, objval, searchbound);
639  }
640 
641  /* free temporary memory */
642  SCIPfreeBufferArray(scip, &fixcands);
643 
644  /* end diving */
646 
647  if( *result == SCIP_FOUNDSOL )
648  heurdata->nsuccess++;
649 
650  SCIPdebugMsg(scip, "intdiving heuristic finished\n");
651 
652  return SCIP_OKAY;
653 }
654 
655 
656 /*
657  * heuristic specific interface methods
658  */
659 
660 /** creates the intdiving heuristic and includes it in SCIP */
662  SCIP* scip /**< SCIP data structure */
663  )
664 {
665  SCIP_HEURDATA* heurdata;
666  SCIP_HEUR* heur;
667 
668  /* create Intdiving primal heuristic data */
669  SCIP_CALL( SCIPallocBlockMemory(scip, &heurdata) );
670 
671  /* include primal heuristic */
674  HEUR_MAXDEPTH, HEUR_TIMING, HEUR_USESSUBSCIP, heurExecIntdiving, heurdata) );
675 
676  assert(heur != NULL);
677 
678  /* set non-NULL pointers to callback methods */
679  SCIP_CALL( SCIPsetHeurCopy(scip, heur, heurCopyIntdiving) );
680  SCIP_CALL( SCIPsetHeurFree(scip, heur, heurFreeIntdiving) );
681  SCIP_CALL( SCIPsetHeurInit(scip, heur, heurInitIntdiving) );
682  SCIP_CALL( SCIPsetHeurExit(scip, heur, heurExitIntdiving) );
683 
684  /* intdiving heuristic parameters */
686  "heuristics/intdiving/minreldepth",
687  "minimal relative depth to start diving",
688  &heurdata->minreldepth, TRUE, DEFAULT_MINRELDEPTH, 0.0, 1.0, NULL, NULL) );
690  "heuristics/intdiving/maxreldepth",
691  "maximal relative depth to start diving",
692  &heurdata->maxreldepth, TRUE, DEFAULT_MAXRELDEPTH, 0.0, 1.0, NULL, NULL) );
694  "heuristics/intdiving/maxlpiterquot",
695  "maximal fraction of diving LP iterations compared to node LP iterations",
696  &heurdata->maxlpiterquot, FALSE, DEFAULT_MAXLPITERQUOT, 0.0, SCIP_REAL_MAX, NULL, NULL) );
698  "heuristics/intdiving/maxlpiterofs",
699  "additional number of allowed LP iterations",
700  &heurdata->maxlpiterofs, FALSE, DEFAULT_MAXLPITEROFS, 0, INT_MAX, NULL, NULL) );
702  "heuristics/intdiving/maxdiveubquot",
703  "maximal quotient (curlowerbound - lowerbound)/(cutoffbound - lowerbound) where diving is performed (0.0: no limit)",
704  &heurdata->maxdiveubquot, TRUE, DEFAULT_MAXDIVEUBQUOT, 0.0, 1.0, NULL, NULL) );
706  "heuristics/intdiving/maxdiveavgquot",
707  "maximal quotient (curlowerbound - lowerbound)/(avglowerbound - lowerbound) where diving is performed (0.0: no limit)",
708  &heurdata->maxdiveavgquot, TRUE, DEFAULT_MAXDIVEAVGQUOT, 0.0, SCIP_REAL_MAX, NULL, NULL) );
710  "heuristics/intdiving/maxdiveubquotnosol",
711  "maximal UBQUOT when no solution was found yet (0.0: no limit)",
712  &heurdata->maxdiveubquotnosol, TRUE, DEFAULT_MAXDIVEUBQUOTNOSOL, 0.0, 1.0, NULL, NULL) );
714  "heuristics/intdiving/maxdiveavgquotnosol",
715  "maximal AVGQUOT when no solution was found yet (0.0: no limit)",
716  &heurdata->maxdiveavgquotnosol, TRUE, DEFAULT_MAXDIVEAVGQUOTNOSOL, 0.0, SCIP_REAL_MAX, NULL, NULL) );
718  "heuristics/intdiving/backtrack",
719  "use one level of backtracking if infeasibility is encountered?",
720  &heurdata->backtrack, FALSE, DEFAULT_BACKTRACK, NULL, NULL) );
721 
722  return SCIP_OKAY;
723 }
int SCIPgetNIntVars(SCIP *scip)
Definition: scip_prob.c:2134
SCIP_RETCODE SCIPlinkLPSol(SCIP *scip, SCIP_SOL *sol)
Definition: scip_sol.c:1075
#define NULL
Definition: def.h:246
#define MINLPITER
public methods for SCIP parameter handling
#define HEUR_FREQOFS
SCIP_RETCODE SCIPbacktrackProbing(SCIP *scip, int probingdepth)
Definition: scip_probing.c:280
SCIP_Longint SCIPgetNLPIterations(SCIP *scip)
SCIP_Bool SCIPisFeasLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
public methods for memory management
int SCIPgetProbingDepth(SCIP *scip)
Definition: scip_probing.c:253
SCIP_Real SCIPgetCutoffbound(SCIP *scip)
SCIP_Bool SCIPisFeasFracIntegral(SCIP *scip, SCIP_Real val)
SCIP_Longint SCIPheurGetNBestSolsFound(SCIP_HEUR *heur)
Definition: heur.c:1400
SCIP_Longint SCIPgetNSolsFound(SCIP *scip)
SCIP_RETCODE SCIPsetHeurExit(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEUREXIT((*heurexit)))
Definition: scip_heur.c:280
SCIP_Real SCIPvarGetLbLocal(SCIP_VAR *var)
Definition: var.c:17400
int SCIPgetNPseudoBranchCands(SCIP *scip)
Definition: scip_branch.c:747
SCIP_Bool SCIPisGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPvarIsBinary(SCIP_VAR *var)
Definition: var.c:16910
#define HEUR_DESC
int SCIPgetMaxDepth(SCIP *scip)
#define FALSE
Definition: def.h:72
SCIP_Real SCIPinfinity(SCIP *scip)
#define TRUE
Definition: def.h:71
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:53
SCIP_Real SCIPgetAvgLowerbound(SCIP *scip)
#define HEUR_USESSUBSCIP
struct SCIP_HeurData SCIP_HEURDATA
Definition: type_heur.h:51
public methods for problem variables
#define SCIPfreeBlockMemory(scip, ptr)
Definition: scip_mem.h:114
SCIP_RETCODE SCIPincludeHeurBasic(SCIP *scip, SCIP_HEUR **heur, const char *name, const char *desc, char dispchar, int priority, int freq, int freqofs, int maxdepth, SCIP_HEURTIMING timingmask, SCIP_Bool usessubscip, SCIP_DECL_HEUREXEC((*heurexec)), SCIP_HEURDATA *heurdata)
Definition: scip_heur.c:187
#define SCIPduplicateBufferArray(scip, ptr, source, num)
Definition: scip_mem.h:138
SCIP_Bool SCIPisEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
#define SCIPfreeBufferArray(scip, ptr)
Definition: scip_mem.h:142
enum SCIP_LPSolStat SCIP_LPSOLSTAT
Definition: type_lp.h:42
void SCIPheurSetData(SCIP_HEUR *heur, SCIP_HEURDATA *heurdata)
Definition: heur.c:1175
#define SCIPallocBlockMemory(scip, ptr)
Definition: scip_mem.h:97
public methods for SCIP variables
void SCIPwarningMessage(SCIP *scip, const char *formatstr,...)
Definition: scip_message.c:203
#define SCIPdebugMsg
Definition: scip_message.h:88
SCIP_RETCODE SCIPaddIntParam(SCIP *scip, const char *name, const char *desc, int *valueptr, SCIP_Bool isadvanced, int defaultvalue, int minvalue, int maxvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition: scip_param.c:155
int SCIPvarGetNCliques(SCIP_VAR *var, SCIP_Bool varfixing)
Definition: var.c:17696
static SCIP_DECL_HEURINIT(heurInitIntdiving)
public methods for numerical tolerances
public methods for querying solving statistics
public methods for the branch-and-bound tree
SCIP_Bool SCIPisLPSolBasic(SCIP *scip)
Definition: scip_lp.c:670
LP diving heuristic that fixes variables with integral LP value.
const char * SCIPheurGetName(SCIP_HEUR *heur)
Definition: heur.c:1254
static SCIP_DECL_HEUREXEC(heurExecIntdiving)
SCIP_RETCODE SCIPsetHeurFree(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURFREE((*heurfree)))
Definition: scip_heur.c:248
SCIP_Bool SCIPisLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_RETCODE SCIPpropagateProbing(SCIP *scip, int maxproprounds, SCIP_Bool *cutoff, SCIP_Longint *ndomredsfound)
Definition: scip_probing.c:630
SCIP_RETCODE SCIPfixVarProbing(SCIP *scip, SCIP_VAR *var, SCIP_Real fixedval)
Definition: scip_probing.c:473
SCIP_Real SCIPgetDualbound(SCIP *scip)
SCIP_RETCODE SCIPendProbing(SCIP *scip)
Definition: scip_probing.c:315
const char * SCIPvarGetName(SCIP_VAR *var)
Definition: var.c:16730
SCIP_RETCODE SCIPincludeHeurIntdiving(SCIP *scip)
SCIP_Real SCIPvarGetLPSol(SCIP_VAR *var)
Definition: var.c:17718
#define SCIP_CALL(x)
Definition: def.h:358
SCIP_Real SCIPgetLowerbound(SCIP *scip)
SCIP_Bool SCIPisFeasGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_RETCODE SCIPsolveProbingLP(SCIP *scip, int itlim, SCIP_Bool *lperror, SCIP_Bool *cutoff)
Definition: scip_probing.c:866
SCIP_Bool SCIPisFeasLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Longint SCIPheurGetNCalls(SCIP_HEUR *heur)
Definition: heur.c:1380
SCIP_RETCODE SCIPgetPseudoBranchCands(SCIP *scip, SCIP_VAR ***pseudocands, int *npseudocands, int *npriopseudocands)
Definition: scip_branch.c:722
SCIP_Bool SCIPhasCurrentNodeLP(SCIP *scip)
Definition: scip_lp.c:141
public methods for primal heuristic plugins and divesets
SCIP_Longint SCIPgetLastDivenode(SCIP *scip)
Definition: scip_lp.c:2632
SCIP_Longint SCIPgetNNodeLPIterations(SCIP *scip)
static SCIP_DECL_HEUREXIT(heurExitIntdiving)
#define SCIPallocBufferArray(scip, ptr, num)
Definition: scip_mem.h:130
#define SCIP_Bool
Definition: def.h:69
SCIP_LPSOLSTAT SCIPgetLPSolstat(SCIP *scip)
Definition: scip_lp.c:226
static SCIP_DECL_HEURCOPY(heurCopyIntdiving)
#define DEFAULT_MAXLPITEROFS
#define HEUR_NAME
#define DEFAULT_MINRELDEPTH
#define HEUR_PRIORITY
SCIP_RETCODE SCIProundSol(SCIP *scip, SCIP_SOL *sol, SCIP_Bool *success)
Definition: scip_sol.c:2504
int SCIPgetDepth(SCIP *scip)
Definition: scip_tree.c:715
#define DEFAULT_MAXDIVEAVGQUOT
int SCIPvarGetNImpls(SCIP_VAR *var, SCIP_Bool varfixing)
Definition: var.c:17622
static SCIP_DECL_HEURFREE(heurFreeIntdiving)
#define MIN(x, y)
Definition: def.h:216
public methods for LP management
SCIP_RETCODE SCIPfreeSol(SCIP *scip, SCIP_SOL **sol)
Definition: scip_sol.c:1034
void SCIPenableVarHistory(SCIP *scip)
Definition: scip_var.c:8550
SCIP_COL * SCIPvarGetCol(SCIP_VAR *var)
Definition: var.c:17058
SCIP_Real SCIPgetSolOrigObj(SCIP *scip, SCIP_SOL *sol)
Definition: scip_sol.c:1493
SCIP_RETCODE SCIPtrySol(SCIP *scip, SCIP_SOL *sol, SCIP_Bool printreason, SCIP_Bool completely, SCIP_Bool checkbounds, SCIP_Bool checkintegrality, SCIP_Bool checklprows, SCIP_Bool *stored)
Definition: scip_sol.c:3182
#define SCIP_MAXTREEDEPTH
Definition: def.h:294
int SCIPgetNBinVars(SCIP *scip)
Definition: scip_prob.c:2089
public methods for the LP relaxation, rows and columns
#define HEUR_FREQ
#define SCIP_REAL_MAX
Definition: def.h:158
#define SCIP_LONGINT_FORMAT
Definition: def.h:149
#define HEUR_TIMING
public methods for branching rule plugins and branching
SCIP_Bool SCIPisObjIntegral(SCIP *scip)
Definition: scip_prob.c:1618
general public methods
int SCIPcolGetNNonz(SCIP_COL *col)
Definition: lp.c:16803
#define MAX(x, y)
Definition: def.h:215
SCIP_Real SCIPgetLPObjval(SCIP *scip)
Definition: scip_lp.c:305
SCIP_Bool SCIPisGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
#define DEFAULT_BACKTRACK
public methods for solutions
#define DEFAULT_MAXDIVEAVGQUOTNOSOL
public methods for the probing mode
public methods for message output
SCIP_RETCODE SCIPsetHeurInit(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURINIT((*heurinit)))
Definition: scip_heur.c:264
SCIP_Real SCIPretransformObj(SCIP *scip, SCIP_Real obj)
Definition: scip_sol.c:1625
#define DEFAULT_MAXLPITERQUOT
SCIP_VARSTATUS SCIPvarGetStatus(SCIP_VAR *var)
Definition: var.c:16849
#define SCIP_Real
Definition: def.h:157
SCIP_Bool SCIPisStopped(SCIP *scip)
Definition: scip_general.c:738
public methods for message handling
#define SCIP_INVALID
Definition: def.h:177
#define SCIP_Longint
Definition: def.h:142
SCIP_Real SCIPfrac(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisZero(SCIP *scip, SCIP_Real val)
#define HEUR_DISPCHAR
SCIP_Bool SCIPisLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_RETCODE SCIPsetHeurCopy(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURCOPY((*heurcopy)))
Definition: scip_heur.c:232
SCIP_Real SCIPvarGetUbLocal(SCIP_VAR *var)
Definition: var.c:17410
SCIP_RETCODE SCIPnewProbingNode(SCIP *scip)
Definition: scip_probing.c:220
SCIP_RETCODE SCIPstartProbing(SCIP *scip)
Definition: scip_probing.c:174
public methods for primal heuristics
#define DEFAULT_MAXRELDEPTH
SCIP_Real SCIPceil(SCIP *scip, SCIP_Real val)
SCIP_HEURDATA * SCIPheurGetData(SCIP_HEUR *heur)
Definition: heur.c:1165
SCIP_Longint SCIPgetNNodes(SCIP *scip)
public methods for global and local (sub)problems
SCIP_Bool SCIPvarIsIntegral(SCIP_VAR *var)
Definition: var.c:16921
SCIP_Real SCIPgetVarAvgInferenceScore(SCIP *scip, SCIP_VAR *var)
Definition: scip_var.c:9282
SCIP_RETCODE SCIPaddRealParam(SCIP *scip, const char *name, const char *desc, SCIP_Real *valueptr, SCIP_Bool isadvanced, SCIP_Real defaultvalue, SCIP_Real minvalue, SCIP_Real maxvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition: scip_param.c:211
SCIP_Real SCIPfloor(SCIP *scip, SCIP_Real val)
SCIP_RETCODE SCIPaddBoolParam(SCIP *scip, const char *name, const char *desc, SCIP_Bool *valueptr, SCIP_Bool isadvanced, SCIP_Bool defaultvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition: scip_param.c:129
#define DEFAULT_MAXDIVEUBQUOTNOSOL
SCIP_RETCODE SCIPcreateSol(SCIP *scip, SCIP_SOL **sol, SCIP_HEUR *heur)
Definition: scip_sol.c:377
#define DEFAULT_MAXDIVEUBQUOT
#define HEUR_MAXDEPTH
memory allocation routines