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