# 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-2017 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_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 <assert.h>
24 #include <string.h>
25
26 #include "scip/heur_intdiving.h"
27
28
29 #define HEUR_NAME "intdiving"
30 #define HEUR_DESC "LP diving heuristic that fixes binary variables with large LP value to one"
31 #define HEUR_DISPCHAR 'n'
32 #define HEUR_PRIORITY -1003500
33 #define HEUR_FREQ -1
34 #define HEUR_FREQOFS 9
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? */
56 #define MINLPITER 10000 /**< minimal number of LP iterations allowed in each LP solving call */
57
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(heurCopyIntdiving)
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 */
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(heurFreeIntdiving) /*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  SCIPfreeBlockMemory(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(heurInitIntdiving) /*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(heurExitIntdiving) /*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(heurExecIntdiving) /*lint --e{715}*/
169 { /*lint --e{715}*/
170  SCIP_HEURDATA* heurdata;
171  SCIP_LPSOLSTAT lpsolstat;
172  SCIP_VAR** pseudocands;
173  SCIP_VAR** fixcands;
174  SCIP_Real* fixcandscores;
175  SCIP_Real searchubbound;
176  SCIP_Real searchavgbound;
177  SCIP_Real searchbound;
178  SCIP_Real objval;
179  SCIP_Bool lperror;
180  SCIP_Bool cutoff;
181  SCIP_Bool backtracked;
182  SCIP_Longint ncalls;
183  SCIP_Longint nsolsfound;
184  SCIP_Longint nlpiterations;
185  SCIP_Longint maxnlpiterations;
186  int nfixcands;
187  int nbinfixcands;
188  int depth;
189  int maxdepth;
190  int maxdivedepth;
191  int divedepth;
192  int nextcand;
193  int c;
194
195  assert(heur != NULL);
196  assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0);
197  assert(scip != NULL);
198  assert(result != NULL);
199  assert(SCIPhasCurrentNodeLP(scip));
200
201  *result = SCIP_DELAYED;
202
203  /* do not call heuristic of node was already detected to be infeasible */
204  if( nodeinfeasible )
205  return SCIP_OKAY;
206
207  /* only call heuristic, if an optimal LP solution is at hand */
209  return SCIP_OKAY;
210
211  /* only call heuristic, if the LP objective value is smaller than the cutoff bound */
213  return SCIP_OKAY;
214
215  /* only call heuristic, if the LP solution is basic (which allows fast resolve in diving) */
216  if( !SCIPisLPSolBasic(scip) )
217  return SCIP_OKAY;
218
219  /* don't dive two times at the same node */
221  return SCIP_OKAY;
222
223  *result = SCIP_DIDNOTRUN;
224
225  /* get heuristic's data */
226  heurdata = SCIPheurGetData(heur);
227  assert(heurdata != NULL);
228
229  /* only try to dive, if we are in the correct part of the tree, given by minreldepth and maxreldepth */
230  depth = SCIPgetDepth(scip);
231  maxdepth = SCIPgetMaxDepth(scip);
232  maxdepth = MAX(maxdepth, 100);
233  if( depth < heurdata->minreldepth*maxdepth || depth > heurdata->maxreldepth*maxdepth )
234  return SCIP_OKAY;
235
236  /* calculate the maximal number of LP iterations until heuristic is aborted */
237  nlpiterations = SCIPgetNNodeLPIterations(scip);
238  ncalls = SCIPheurGetNCalls(heur);
239  nsolsfound = 10*SCIPheurGetNBestSolsFound(heur) + heurdata->nsuccess;
240  maxnlpiterations = (SCIP_Longint)((1.0 + 10.0*(nsolsfound+1.0)/(ncalls+1.0)) * heurdata->maxlpiterquot * nlpiterations);
241  maxnlpiterations += heurdata->maxlpiterofs;
242
243  /* don't try to dive, if we took too many LP iterations during diving */
244  if( heurdata->nlpiterations >= maxnlpiterations )
245  return SCIP_OKAY;
246
247  /* allow at least a certain number of LP iterations in this dive */
248  maxnlpiterations = MAX(maxnlpiterations, heurdata->nlpiterations + MINLPITER);
249
250  /* get unfixed integer variables */
251  SCIP_CALL( SCIPgetPseudoBranchCands(scip, &pseudocands, &nfixcands, NULL) );
252
253  /* don't try to dive, if there are no fractional variables */
254  if( nfixcands == 0 )
255  return SCIP_OKAY;
256
257  /* calculate the objective search bound */
258  if( SCIPgetNSolsFound(scip) == 0 )
259  {
260  if( heurdata->maxdiveubquotnosol > 0.0 )
261  searchubbound = SCIPgetLowerbound(scip)
262  + heurdata->maxdiveubquotnosol * (SCIPgetCutoffbound(scip) - SCIPgetLowerbound(scip));
263  else
264  searchubbound = SCIPinfinity(scip);
265  if( heurdata->maxdiveavgquotnosol > 0.0 )
266  searchavgbound = SCIPgetLowerbound(scip)
267  + heurdata->maxdiveavgquotnosol * (SCIPgetAvgLowerbound(scip) - SCIPgetLowerbound(scip));
268  else
269  searchavgbound = SCIPinfinity(scip);
270  }
271  else
272  {
273  if( heurdata->maxdiveubquot > 0.0 )
274  searchubbound = SCIPgetLowerbound(scip)
275  + heurdata->maxdiveubquot * (SCIPgetCutoffbound(scip) - SCIPgetLowerbound(scip));
276  else
277  searchubbound = SCIPinfinity(scip);
278  if( heurdata->maxdiveavgquot > 0.0 )
279  searchavgbound = SCIPgetLowerbound(scip)
280  + heurdata->maxdiveavgquot * (SCIPgetAvgLowerbound(scip) - SCIPgetLowerbound(scip));
281  else
282  searchavgbound = SCIPinfinity(scip);
283  }
284  searchbound = MIN(searchubbound, searchavgbound);
285  if( SCIPisObjIntegral(scip) )
286  searchbound = SCIPceil(scip, searchbound);
287
288  /* calculate the maximal diving depth: 10 * min{number of integer variables, max depth} */
289  maxdivedepth = SCIPgetNBinVars(scip) + SCIPgetNIntVars(scip);
290  maxdivedepth = MIN(maxdivedepth, maxdepth);
291  maxdivedepth *= 10;
292
293  *result = SCIP_DIDNOTFIND;
294
295  /* start diving */
297
298  /* enables collection of variable statistics during probing */
300
301  SCIPdebugMsg(scip, "(node %" SCIP_LONGINT_FORMAT ") executing intdiving heuristic: depth=%d, %d non-fixed, dualbound=%g, searchbound=%g\n",
303
304  /* copy the pseudo candidates into own array, because we want to reorder them */
305  SCIP_CALL( SCIPduplicateBufferArray(scip, &fixcands, pseudocands, nfixcands) );
306
307  /* sort non-fixed variables by non-increasing inference score, but prefer binaries over integers in any case */
308  SCIP_CALL( SCIPallocBufferArray(scip, &fixcandscores, nfixcands) );
309  nbinfixcands = 0;
310  for( c = 0; c < nfixcands; ++c )
311  {
312  SCIP_VAR* var;
313  SCIP_Real score;
314  int colveclen;
315  int left;
316  int right;
317  int i;
318
319  assert(c >= nbinfixcands);
320  var = fixcands[c];
321  assert(SCIPvarIsIntegral(var));
322  colveclen = (SCIPvarGetStatus(var) == SCIP_VARSTATUS_COLUMN ? SCIPcolGetNNonz(SCIPvarGetCol(var)) : 0);
323  if( SCIPvarIsBinary(var) )
324  {
325  score = 500.0 * SCIPvarGetNCliques(var, TRUE) + 100.0 * SCIPvarGetNImpls(var, TRUE)
326  + SCIPgetVarAvgInferenceScore(scip, var) + (SCIP_Real)colveclen/100.0;
327
328  /* shift the non-binary variables one slot to the right */
329  for( i = c; i > nbinfixcands; --i )
330  {
331  fixcands[i] = fixcands[i-1];
332  fixcandscores[i] = fixcandscores[i-1];
333  }
334  /* put the new candidate into the first nbinfixcands slot */
335  left = 0;
336  right = nbinfixcands;
337  nbinfixcands++;
338  }
339  else
340  {
341  score = 5.0 * (SCIPvarGetNCliques(var, FALSE) + SCIPvarGetNCliques(var, TRUE))
343  + (SCIP_Real)colveclen/10000.0;
344
345  /* put the new candidate in the slots after the binary candidates */
346  left = nbinfixcands;
347  right = c;
348  }
349  for( i = right; i > left && score > fixcandscores[i-1]; --i )
350  {
351  fixcands[i] = fixcands[i-1];
352  fixcandscores[i] = fixcandscores[i-1];
353  }
354  fixcands[i] = var;
355  fixcandscores[i] = score;
356  SCIPdebugMsg(scip, " <%s>: ncliques=%d/%d, nimpls=%d/%d, inferencescore=%g, colveclen=%d -> score=%g\n",
359  colveclen, score);
360  }
361  SCIPfreeBufferArray(scip, &fixcandscores);
362
363  /* get LP objective value */
364  lpsolstat = SCIP_LPSOLSTAT_OPTIMAL;
365  objval = SCIPgetLPObjval(scip);
366
367  /* dive as long we are in the given objective, depth and iteration limits, but if possible, we dive at least with
368  * the depth 10
369  */
370  lperror = FALSE;
371  cutoff = FALSE;
372  divedepth = 0;
373  nextcand = 0;
374  while( !lperror && !cutoff && lpsolstat == SCIP_LPSOLSTAT_OPTIMAL
375  && (divedepth < 10
376  || (divedepth < maxdivedepth && heurdata->nlpiterations < maxnlpiterations && objval < searchbound))
377  && !SCIPisStopped(scip) )
378  {
379  SCIP_VAR* var;
380  SCIP_Real bestsolval;
381  SCIP_Real bestfixval;
382  int bestcand;
383  SCIP_Longint nnewlpiterations;
384  SCIP_Longint nnewdomreds;
385
386  /* open a new probing node if this will not exceed the maximal tree depth, otherwise stop here */
388  {
390  divedepth++;
391  }
392  else
393  break;
394
395  nnewlpiterations = 0;
396  nnewdomreds = 0;
397
398  /* fix binary variable that is closest to 1 in the LP solution to 1;
399  * if all binary variables are fixed, fix integer variable with least fractionality in LP solution
400  */
401  bestcand = -1;
402  bestsolval = -1.0;
403  bestfixval = 1.0;
404
405  /* look in the binary variables for fixing candidates */
406  for( c = nextcand; c < nbinfixcands; ++c )
407  {
408  SCIP_Real solval;
409
410  var = fixcands[c];
411
412  /* ignore already fixed variables */
413  if( var == NULL )
414  continue;
415  if( SCIPvarGetLbLocal(var) > 0.5 || SCIPvarGetUbLocal(var) < 0.5 )
416  {
417  fixcands[c] = NULL;
418  continue;
419  }
420
421  /* get the LP solution value */
422  solval = SCIPvarGetLPSol(var);
423
424  if( solval > bestsolval )
425  {
426  bestcand = c;
427  bestfixval = 1.0;
428  bestsolval = solval;
429  if( SCIPisGE(scip, bestsolval, 1.0) )
430  {
431  /* we found an unfixed binary variable with LP solution value of 1.0 - there cannot be a better candidate */
432  break;
433  }
434  else if( SCIPisLE(scip, bestsolval, 0.0) )
435  {
436  /* the variable is currently at 0.0 - this is the only situation where we want to fix it to 0.0 */
437  bestfixval = 0.0;
438  }
439  }
440  }
441
442  /* if all binary variables are fixed, look in the integer variables for a fixing candidate */
443  if( bestcand == -1 )
444  {
445  SCIP_Real bestfrac;
446
447  bestfrac = SCIP_INVALID;
448  for( c = MAX(nextcand, nbinfixcands); c < nfixcands; ++c )
449  {
450  SCIP_Real solval;
451  SCIP_Real frac;
452
453  var = fixcands[c];
454
455  /* ignore already fixed variables */
456  if( var == NULL )
457  continue;
458  if( SCIPvarGetUbLocal(var) - SCIPvarGetLbLocal(var) < 0.5 )
459  {
460  fixcands[c] = NULL;
461  continue;
462  }
463
464  /* get the LP solution value */
465  solval = SCIPvarGetLPSol(var);
466  frac = SCIPfrac(scip, solval);
467
468  /* ignore integer variables that are currently integral */
469  if( SCIPisFeasFracIntegral(scip, frac) )
470  continue;
471
472  if( frac < bestfrac )
473  {
474  bestcand = c;
475  bestsolval = solval;
476  bestfrac = frac;
477  bestfixval = SCIPfloor(scip, bestsolval + 0.5);
478  if( SCIPisZero(scip, bestfrac) )
479  {
480  /* we found an unfixed integer variable with integral LP solution value */
481  break;
482  }
483  }
484  }
485  }
486  assert(-1 <= bestcand && bestcand < nfixcands);
487
488  /* if there is no unfixed candidate left, we are done */
489  if( bestcand == -1 )
490  break;
491
492  var = fixcands[bestcand];
493  assert(var != NULL);
494  assert(SCIPvarIsIntegral(var));
495  assert(SCIPvarGetUbLocal(var) - SCIPvarGetLbLocal(var) > 0.5);
496  assert(SCIPisGE(scip, bestfixval, SCIPvarGetLbLocal(var)));
497  assert(SCIPisLE(scip, bestfixval, SCIPvarGetUbLocal(var)));
498
499  backtracked = FALSE;
500  do
501  {
502  /* if the variable is already fixed or if the solution value is outside the domain, numerical troubles may have
503  * occured or variable was fixed by propagation while backtracking => Abort diving!
504  */
505  if( SCIPvarGetLbLocal(var) >= SCIPvarGetUbLocal(var) - 0.5 )
506  {
507  SCIPdebugMsg(scip, "Selected variable <%s> already fixed to [%g,%g], diving aborted \n",
509  cutoff = TRUE;
510  break;
511  }
512  if( SCIPisFeasLT(scip, bestfixval, SCIPvarGetLbLocal(var)) || SCIPisFeasGT(scip, bestfixval, SCIPvarGetUbLocal(var)) )
513  {
514  SCIPdebugMsg(scip, "selected variable's <%s> solution value is outside the domain [%g,%g] (solval: %.9f), diving aborted\n",
515  SCIPvarGetName(var), SCIPvarGetLbLocal(var), SCIPvarGetUbLocal(var), bestfixval);
516  assert(backtracked);
517  break;
518  }
519
520  /* apply fixing of best candidate */
521  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",
522  divedepth, maxdivedepth, heurdata->nlpiterations, maxnlpiterations, SCIPgetNPseudoBranchCands(scip),
523  SCIPvarGetName(var), bestsolval, SCIPvarGetLbLocal(var), SCIPvarGetUbLocal(var), bestfixval);
524  SCIP_CALL( SCIPfixVarProbing(scip, var, bestfixval) );
525
526  /* apply domain propagation */
527  SCIP_CALL( SCIPpropagateProbing(scip, 0, &cutoff, &nnewdomreds) );
528  if( !cutoff )
529  {
530  /* if the best candidate was just fixed to its LP value and no domain reduction was found, the LP solution
531  * stays valid, and the LP does not need to be resolved
532  */
533  if( nnewdomreds > 0 || !SCIPisEQ(scip, bestsolval, bestfixval) )
534  {
535  /* resolve the diving LP */
536  /* Errors in the LP solver should not kill the overall solving process, if the LP is just needed for a heuristic.
537  * Hence in optimized mode, the return code is caught and a warning is printed, only in debug mode, SCIP will stop.
538  */
539 #ifdef NDEBUG
540  SCIP_RETCODE retstat;
541  nlpiterations = SCIPgetNLPIterations(scip);
542  retstat = SCIPsolveProbingLP(scip, MAX((int)(maxnlpiterations - heurdata->nlpiterations), MINLPITER), &lperror, &cutoff);
543  if( retstat != SCIP_OKAY )
544  {
545  SCIPwarningMessage(scip, "Error while solving LP in Intdiving heuristic; LP solve terminated with code <%d>\n",retstat);
546  }
547 #else
548  nlpiterations = SCIPgetNLPIterations(scip);
549  SCIP_CALL( SCIPsolveProbingLP(scip, MAX((int)(maxnlpiterations - heurdata->nlpiterations), MINLPITER), &lperror, &cutoff) );
550 #endif
551
552  if( lperror )
553  break;
554
555  /* update iteration count */
556  nnewlpiterations = SCIPgetNLPIterations(scip) - nlpiterations;
557  heurdata->nlpiterations += nnewlpiterations;
558
559  /* get LP solution status */
560  lpsolstat = SCIPgetLPSolstat(scip);
561  assert(cutoff || (lpsolstat != SCIP_LPSOLSTAT_OBJLIMIT && lpsolstat != SCIP_LPSOLSTAT_INFEASIBLE &&
563  }
564  }
565
566  /* perform backtracking if a cutoff was detected */
567  if( cutoff && !backtracked && heurdata->backtrack )
568  {
569  SCIPdebugMsg(scip, " *** cutoff detected at level %d - backtracking\n", SCIPgetProbingDepth(scip));
571
572  /* after backtracking there has to be at least one open node without exceeding the maximal tree depth */
574
576
577  bestfixval = SCIPvarIsBinary(var)
578  ? 1.0 - bestfixval
579  : (SCIPisGT(scip, bestsolval, bestfixval) && SCIPisFeasLE(scip, bestfixval + 1, SCIPvarGetUbLocal(var)) ? bestfixval + 1 : bestfixval - 1);
580
581  backtracked = TRUE;
582  }
583  else
584  backtracked = FALSE;
585  }
586  while( backtracked );
587
588  if( !lperror && !cutoff && lpsolstat == SCIP_LPSOLSTAT_OPTIMAL )
589  {
590  SCIP_Bool success;
591
592  /* get new objective value */
593  objval = SCIPgetLPObjval(scip);
594
595  if( nnewlpiterations > 0 || !SCIPisEQ(scip, bestsolval, bestfixval) )
596  {
597  /* we must start again with the first candidate, since the LP solution changed */
598  nextcand = 0;
599
600  /* create solution from diving LP and try to round it */
601  SCIP_CALL( SCIPlinkLPSol(scip, heurdata->sol) );
602  SCIP_CALL( SCIProundSol(scip, heurdata->sol, &success) );
603  if( success )
604  {
605  SCIPdebugMsg(scip, "intdiving found roundable primal solution: obj=%g\n",
606  SCIPgetSolOrigObj(scip, heurdata->sol));
607
608  /* try to add solution to SCIP */
609  SCIP_CALL( SCIPtrySol(scip, heurdata->sol, FALSE, FALSE, FALSE, FALSE, FALSE, &success) );
610
611  /* check, if solution was feasible and good enough */
612  if( success )
613  {
614  SCIPdebugMsg(scip, " -> solution was feasible and good enough\n");
615  *result = SCIP_FOUNDSOL;
616  }
617  }
618  }
619  else
620  nextcand = bestcand+1; /* continue with the next candidate in the following loop */
621  }
622  SCIPdebugMsg(scip, " -> lpsolstat=%d, objval=%g/%g\n", lpsolstat, objval, searchbound);
623  }
624
625  /* free temporary memory */
626  SCIPfreeBufferArray(scip, &fixcands);
627
628  /* end diving */
630
631  if( *result == SCIP_FOUNDSOL )
632  heurdata->nsuccess++;
633
634  SCIPdebugMsg(scip, "intdiving heuristic finished\n");
635
636  return SCIP_OKAY;
637 }
638
639
640 /*
641  * heuristic specific interface methods
642  */
643
644 /** creates the intdiving heuristic and includes it in SCIP */
646  SCIP* scip /**< SCIP data structure */
647  )
648 {
649  SCIP_HEURDATA* heurdata;
650  SCIP_HEUR* heur;
651
652  /* create Intdiving primal heuristic data */
653  SCIP_CALL( SCIPallocBlockMemory(scip, &heurdata) );
654
655  /* include primal heuristic */
658  HEUR_MAXDEPTH, HEUR_TIMING, HEUR_USESSUBSCIP, heurExecIntdiving, heurdata) );
659
660  assert(heur != NULL);
661
662  /* set non-NULL pointers to callback methods */
663  SCIP_CALL( SCIPsetHeurCopy(scip, heur, heurCopyIntdiving) );
664  SCIP_CALL( SCIPsetHeurFree(scip, heur, heurFreeIntdiving) );
665  SCIP_CALL( SCIPsetHeurInit(scip, heur, heurInitIntdiving) );
666  SCIP_CALL( SCIPsetHeurExit(scip, heur, heurExitIntdiving) );
667
668  /* intdiving heuristic parameters */
670  "heuristics/intdiving/minreldepth",
671  "minimal relative depth to start diving",
672  &heurdata->minreldepth, TRUE, DEFAULT_MINRELDEPTH, 0.0, 1.0, NULL, NULL) );
674  "heuristics/intdiving/maxreldepth",
675  "maximal relative depth to start diving",
676  &heurdata->maxreldepth, TRUE, DEFAULT_MAXRELDEPTH, 0.0, 1.0, NULL, NULL) );
678  "heuristics/intdiving/maxlpiterquot",
679  "maximal fraction of diving LP iterations compared to node LP iterations",
680  &heurdata->maxlpiterquot, FALSE, DEFAULT_MAXLPITERQUOT, 0.0, SCIP_REAL_MAX, NULL, NULL) );
682  "heuristics/intdiving/maxlpiterofs",
683  "additional number of allowed LP iterations",
684  &heurdata->maxlpiterofs, FALSE, DEFAULT_MAXLPITEROFS, 0, INT_MAX, NULL, NULL) );
686  "heuristics/intdiving/maxdiveubquot",
687  "maximal quotient (curlowerbound - lowerbound)/(cutoffbound - lowerbound) where diving is performed (0.0: no limit)",
688  &heurdata->maxdiveubquot, TRUE, DEFAULT_MAXDIVEUBQUOT, 0.0, 1.0, NULL, NULL) );
690  "heuristics/intdiving/maxdiveavgquot",
691  "maximal quotient (curlowerbound - lowerbound)/(avglowerbound - lowerbound) where diving is performed (0.0: no limit)",
692  &heurdata->maxdiveavgquot, TRUE, DEFAULT_MAXDIVEAVGQUOT, 0.0, SCIP_REAL_MAX, NULL, NULL) );
694  "heuristics/intdiving/maxdiveubquotnosol",
695  "maximal UBQUOT when no solution was found yet (0.0: no limit)",
696  &heurdata->maxdiveubquotnosol, TRUE, DEFAULT_MAXDIVEUBQUOTNOSOL, 0.0, 1.0, NULL, NULL) );
698  "heuristics/intdiving/maxdiveavgquotnosol",
699  "maximal AVGQUOT when no solution was found yet (0.0: no limit)",
700  &heurdata->maxdiveavgquotnosol, TRUE, DEFAULT_MAXDIVEAVGQUOTNOSOL, 0.0, SCIP_REAL_MAX, NULL, NULL) );
702  "heuristics/intdiving/backtrack",
703  "use one level of backtracking if infeasibility is encountered?",
704  &heurdata->backtrack, FALSE, DEFAULT_BACKTRACK, NULL, NULL) );
705
706  return SCIP_OKAY;
707 }
int SCIPgetNIntVars(SCIP *scip)
Definition: scip.c:11721
SCIP_RETCODE SCIPlinkLPSol(SCIP *scip, SCIP_SOL *sol)
Definition: scip.c:37672
#define MINLPITER
#define HEUR_FREQOFS
SCIP_RETCODE SCIPbacktrackProbing(SCIP *scip, int probingdepth)
Definition: scip.c:35152
SCIP_Longint SCIPgetNLPIterations(SCIP *scip)
Definition: scip.c:41382
SCIP_Bool SCIPisFeasLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip.c:46099
int SCIPgetProbingDepth(SCIP *scip)
Definition: scip.c:35125
SCIP_Real SCIPgetCutoffbound(SCIP *scip)
Definition: scip.c:42499
SCIP_Bool SCIPisFeasFracIntegral(SCIP *scip, SCIP_Real val)
Definition: scip.c:46199
SCIP_Longint SCIPheurGetNBestSolsFound(SCIP_HEUR *heur)
Definition: heur.c:1327
SCIP_Longint SCIPgetNSolsFound(SCIP *scip)
Definition: scip.c:42664
SCIP_RETCODE SCIPsetHeurExit(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEUREXIT((*heurexit)))
Definition: scip.c:8092
SCIP_Real SCIPvarGetLbLocal(SCIP_VAR *var)
Definition: var.c:17222
int SCIPgetNPseudoBranchCands(SCIP *scip)
Definition: scip.c:36492
SCIP_Bool SCIPisGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip.c:45803
SCIP_Bool SCIPvarIsBinary(SCIP_VAR *var)
Definition: var.c:16732
#define HEUR_DESC
int SCIPgetMaxDepth(SCIP *scip)
Definition: scip.c:42144
#define FALSE
Definition: def.h:64
SCIP_Real SCIPinfinity(SCIP *scip)
Definition: scip.c:45816
#define TRUE
Definition: def.h:63
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:53
SCIP_Real SCIPgetAvgLowerbound(SCIP *scip)
Definition: scip.c:42280
#define HEUR_USESSUBSCIP
struct SCIP_HeurData SCIP_HEURDATA
Definition: type_heur.h:51
#define SCIPfreeBlockMemory(scip, ptr)
Definition: scip.h:21907
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.c:7999
#define SCIPduplicateBufferArray(scip, ptr, source, num)
Definition: scip.h:21933
SCIP_Bool SCIPisEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip.c:45751
#define SCIPfreeBufferArray(scip, ptr)
Definition: scip.h:21937
enum SCIP_LPSolStat SCIP_LPSOLSTAT
Definition: type_lp.h:42
void SCIPheurSetData(SCIP_HEUR *heur, SCIP_HEURDATA *heurdata)
Definition: heur.c:1102
#define SCIPallocBlockMemory(scip, ptr)
Definition: scip.h:21890
void SCIPwarningMessage(SCIP *scip, const char *formatstr,...)
Definition: scip.c:1260
#define SCIPdebugMsg
Definition: scip.h:451
SCIP_RETCODE SCIPaddIntParam(SCIP *scip, const char *name, const char *desc, int *valueptr, SCIP_Bool isadvanced, int defaultvalue, int minvalue, int maxvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition: scip.c:4202
int SCIPvarGetNCliques(SCIP_VAR *var, SCIP_Bool varfixing)
Definition: var.c:17518
static SCIP_DECL_HEURINIT(heurInitIntdiving)
SCIP_Bool SCIPisLPSolBasic(SCIP *scip)
Definition: scip.c:29262
LP diving heuristic that fixes variables with integral LP value.
const char * SCIPheurGetName(SCIP_HEUR *heur)
Definition: heur.c:1181
static SCIP_DECL_HEUREXEC(heurExecIntdiving)
SCIP_RETCODE SCIPsetHeurFree(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURFREE((*heurfree)))
Definition: scip.c:8060
SCIP_Bool SCIPisLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip.c:45764
SCIP_RETCODE SCIPpropagateProbing(SCIP *scip, int maxproprounds, SCIP_Bool *cutoff, SCIP_Longint *ndomredsfound)
Definition: scip.c:35477
SCIP_RETCODE SCIPfixVarProbing(SCIP *scip, SCIP_VAR *var, SCIP_Real fixedval)
Definition: scip.c:35337
SCIP_Real SCIPgetDualbound(SCIP *scip)
Definition: scip.c:42302
SCIP_RETCODE SCIPendProbing(SCIP *scip)
Definition: scip.c:35187
const char * SCIPvarGetName(SCIP_VAR *var)
Definition: var.c:16552
SCIP_RETCODE SCIPincludeHeurIntdiving(SCIP *scip)
#define NULL
Definition: lpi_spx1.cpp:137
SCIP_Real SCIPvarGetLPSol(SCIP_VAR *var)
Definition: var.c:17540
#define SCIP_CALL(x)
Definition: def.h:306
SCIP_Real SCIPgetLowerbound(SCIP *scip)
Definition: scip.c:42323
SCIP_Bool SCIPisFeasGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip.c:46125
SCIP_RETCODE SCIPsolveProbingLP(SCIP *scip, int itlim, SCIP_Bool *lperror, SCIP_Bool *cutoff)
Definition: scip.c:35713
SCIP_Bool SCIPisFeasLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip.c:46112
SCIP_Longint SCIPheurGetNCalls(SCIP_HEUR *heur)
Definition: heur.c:1307
SCIP_RETCODE SCIPgetPseudoBranchCands(SCIP *scip, SCIP_VAR ***pseudocands, int *npseudocands, int *npriopseudocands)
Definition: scip.c:36467
SCIP_Bool SCIPhasCurrentNodeLP(SCIP *scip)
Definition: scip.c:28769
SCIP_Longint SCIPgetLastDivenode(SCIP *scip)
Definition: scip.c:34969
SCIP_Longint SCIPgetNNodeLPIterations(SCIP *scip)
Definition: scip.c:41703
static SCIP_DECL_HEUREXIT(heurExitIntdiving)
#define SCIPallocBufferArray(scip, ptr, num)
Definition: scip.h:21925
#define SCIP_Bool
Definition: def.h:61
SCIP_LPSOLSTAT SCIPgetLPSolstat(SCIP *scip)
Definition: scip.c:28854
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.c:39073
int SCIPgetDepth(SCIP *scip)
Definition: scip.c:42094
#define DEFAULT_MAXDIVEAVGQUOT
int SCIPvarGetNImpls(SCIP_VAR *var, SCIP_Bool varfixing)
Definition: var.c:17444
static SCIP_DECL_HEURFREE(heurFreeIntdiving)
#define MAX(x, y)
Definition: tclique_def.h:75
SCIP_RETCODE SCIPfreeSol(SCIP *scip, SCIP_SOL **sol)
Definition: scip.c:37631
void SCIPenableVarHistory(SCIP *scip)
Definition: scip.c:25520
SCIP_COL * SCIPvarGetCol(SCIP_VAR *var)
Definition: var.c:16880
SCIP_Real SCIPgetSolOrigObj(SCIP *scip, SCIP_SOL *sol)
Definition: scip.c:38090
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.c:39749
#define SCIP_MAXTREEDEPTH
Definition: def.h:242
int SCIPgetNBinVars(SCIP *scip)
Definition: scip.c:11676
#define HEUR_FREQ
#define SCIP_REAL_MAX
Definition: def.h:136
#define HEUR_TIMING
SCIP_Bool SCIPisObjIntegral(SCIP *scip)
Definition: scip.c:11205
int SCIPcolGetNNonz(SCIP_COL *col)
Definition: lp.c:16155
SCIP_Real SCIPgetLPObjval(SCIP *scip)
Definition: scip.c:28897
SCIP_Bool SCIPisGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip.c:45790
#define DEFAULT_BACKTRACK
#define DEFAULT_MAXDIVEAVGQUOTNOSOL
SCIP_RETCODE SCIPsetHeurInit(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURINIT((*heurinit)))
Definition: scip.c:8076
SCIP_Real SCIPretransformObj(SCIP *scip, SCIP_Real obj)
Definition: scip.c:38222
#define DEFAULT_MAXLPITERQUOT
SCIP_VARSTATUS SCIPvarGetStatus(SCIP_VAR *var)
Definition: var.c:16671
#define SCIP_Real
Definition: def.h:135
SCIP_Bool SCIPisStopped(SCIP *scip)
Definition: scip.c:1138
#define MIN(x, y)
Definition: memory.c:75
#define SCIP_INVALID
Definition: def.h:155
#define SCIP_Longint
Definition: def.h:120
SCIP_Real SCIPfrac(SCIP *scip, SCIP_Real val)
Definition: scip.c:45973
SCIP_Bool SCIPisZero(SCIP *scip, SCIP_Real val)
Definition: scip.c:45864
#define HEUR_DISPCHAR
SCIP_Bool SCIPisLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip.c:45777
SCIP_RETCODE SCIPsetHeurCopy(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURCOPY((*heurcopy)))
Definition: scip.c:8044
SCIP_Real SCIPvarGetUbLocal(SCIP_VAR *var)
Definition: var.c:17232
SCIP_RETCODE SCIPnewProbingNode(SCIP *scip)
Definition: scip.c:35092
SCIP_RETCODE SCIPstartProbing(SCIP *scip)
Definition: scip.c:35055
#define DEFAULT_MAXRELDEPTH
SCIP_Real SCIPceil(SCIP *scip, SCIP_Real val)
Definition: scip.c:45949
SCIP_HEURDATA * SCIPheurGetData(SCIP_HEUR *heur)
Definition: heur.c:1092
SCIP_Longint SCIPgetNNodes(SCIP *scip)
Definition: scip.c:41182
SCIP_Bool SCIPvarIsIntegral(SCIP_VAR *var)
Definition: var.c:16743
SCIP_Real SCIPgetVarAvgInferenceScore(SCIP *scip, SCIP_VAR *var)
Definition: scip.c:26252
SCIP_RETCODE SCIPaddRealParam(SCIP *scip, const char *name, const char *desc, SCIP_Real *valueptr, SCIP_Bool isadvanced, SCIP_Real defaultvalue, SCIP_Real minvalue, SCIP_Real maxvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition: scip.c:4258
SCIP_Real SCIPfloor(SCIP *scip, SCIP_Real val)
Definition: scip.c:45937
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.c:4176
#define DEFAULT_MAXDIVEUBQUOTNOSOL
SCIP_RETCODE SCIPcreateSol(SCIP *scip, SCIP_SOL **sol, SCIP_HEUR *heur)
Definition: scip.c:37005
#define DEFAULT_MAXDIVEUBQUOT
#define HEUR_MAXDEPTH