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