Scippy

SCIP

Solving Constraint Integer Programs

heur_objpscostdiving.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_objpscostdiving.c
17  * @brief LP diving heuristic that changes variable's objective value instead of bounds, using pseudo cost values as guide
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 
27 
28 
29 #define HEUR_NAME "objpscostdiving"
30 #define HEUR_DESC "LP diving heuristic that changes variable's objective values instead of bounds, using pseudo costs as guide"
31 #define HEUR_DISPCHAR 'o'
32 #define HEUR_PRIORITY -1004000
33 #define HEUR_FREQ 20
34 #define HEUR_FREQOFS 4
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.01 /**< maximal fraction of diving LP iterations compared to total iteration number */
47 #define DEFAULT_MAXLPITEROFS 1000 /**< additional number of allowed LP iterations */
48 #define DEFAULT_MAXSOLS -1 /**< total number of feasible solutions found up to which heuristic is called
49  * (-1: no limit) */
50 #define DEFAULT_DEPTHFAC 0.5 /**< maximal diving depth: number of binary/integer variables times depthfac */
51 #define DEFAULT_DEPTHFACNOSOL 2.0 /**< maximal diving depth factor if no feasible solution was found yet */
52 #define DEFAULT_RANDSEED 139 /**< initial random seed */
53 
54 #define MINLPITER 10000 /**< minimal number of LP iterations allowed in each LP solving call */
55 
56 
57 /* locally defined heuristic data */
58 struct SCIP_HeurData
59 {
60  SCIP_SOL* sol; /**< working solution */
61  SCIP_RANDNUMGEN* randnumgen; /**< random number generator */
62  SCIP_Real minreldepth; /**< minimal relative depth to start diving */
63  SCIP_Real maxreldepth; /**< maximal relative depth to start diving */
64  SCIP_Real maxlpiterquot; /**< maximal fraction of diving LP iterations compared to total iteration number */
65  int maxlpiterofs; /**< additional number of allowed LP iterations */
66  int maxsols; /**< total number of feasible solutions found up to which heuristic is called
67  * (-1: no limit) */
68  SCIP_Real depthfac; /**< maximal diving depth: number of binary/integer variables times depthfac */
69  SCIP_Real depthfacnosol; /**< maximal diving depth factor if no feasible solution was found yet */
70  SCIP_Longint nlpiterations; /**< LP iterations used in this heuristic */
71  int nsuccess; /**< number of runs that produced at least one feasible solution */
72 };
73 
74 
75 /*
76  * local methods
77  */
78 
79 static
80 void calcPscostQuot(
81  SCIP* scip, /**< SCIP data structure */
82  SCIP_HEURDATA* heurdata, /**< heuristic data structure */
83  SCIP_VAR* var, /**< problem variable */
84  SCIP_Real primsol, /**< primal solution of variable */
85  SCIP_Real frac, /**< fractionality of variable */
86  int rounddir, /**< -1: round down, +1: round up, 0: select due to pseudo cost values */
87  SCIP_Real* pscostquot, /**< pointer to store pseudo cost quotient */
88  SCIP_Bool* roundup /**< pointer to store whether the variable should be rounded up */
89  )
90 {
91  SCIP_Real pscostdown;
92  SCIP_Real pscostup;
93 
94  assert(heurdata != NULL);
95  assert(pscostquot != NULL);
96  assert(roundup != NULL);
97 
98  /* bound fractions to not prefer variables that are nearly integral */
99  frac = MAX(frac, 0.1);
100  frac = MIN(frac, 0.9);
101 
102  /* get pseudo cost quotient */
103  pscostdown = SCIPgetVarPseudocostVal(scip, var, 0.0-frac);
104  pscostup = SCIPgetVarPseudocostVal(scip, var, 1.0-frac);
105  assert(pscostdown >= 0.0 && pscostup >= 0.0);
106 
107  /* choose rounding direction
108  *
109  * to avoid performance variability caused by numerics we use random numbers to decide whether we want to roundup or
110  * round down if the values to compare are equal within tolerances.
111  */
112  if( rounddir == -1 )
113  *roundup = FALSE;
114  else if( rounddir == +1 )
115  *roundup = TRUE;
116  else if( SCIPisLT(scip, frac, 0.3) || (SCIPisEQ(scip, frac, 0.3) && SCIPrandomGetInt(heurdata->randnumgen, 0, 1) == 0) )
117  *roundup = FALSE;
118  else if( SCIPisGT(scip, frac, 0.7) || (SCIPisEQ(scip, frac, 0.7) && SCIPrandomGetInt(heurdata->randnumgen, 0, 1) == 0) )
119  *roundup = TRUE;
120  else if( SCIPisLT(scip, primsol, SCIPvarGetRootSol(var) - 0.4)
121  || (SCIPisEQ(scip, primsol, SCIPvarGetRootSol(var) - 0.4) && SCIPrandomGetInt(heurdata->randnumgen, 0, 1) == 0) )
122  *roundup = FALSE;
123  else if( SCIPisGT(scip, primsol, SCIPvarGetRootSol(var) + 0.4)
124  || (SCIPisEQ(scip, primsol, SCIPvarGetRootSol(var) + 0.4) && SCIPrandomGetInt(heurdata->randnumgen, 0, 1) == 0) )
125  *roundup = TRUE;
126  else if( SCIPisLT(scip, pscostdown, pscostup)
127  || (SCIPisEQ(scip, pscostdown, pscostup) && SCIPrandomGetInt(heurdata->randnumgen, 0, 1) == 0) )
128  *roundup = FALSE;
129  else
130  *roundup = TRUE;
131 
132  /* calculate pseudo cost quotient */
133  if( *roundup )
134  *pscostquot = sqrt(frac) * (1.0+pscostdown) / (1.0+pscostup);
135  else
136  *pscostquot = sqrt(1.0-frac) * (1.0+pscostup) / (1.0+pscostdown);
137 
138  /* prefer decisions on binary variables */
139  if( SCIPvarIsBinary(var) )
140  (*pscostquot) *= 1000.0;
141 }
142 
143 
144 /*
145  * Callback methods
146  */
147 
148 /** copy method for primal heuristic plugins (called when SCIP copies plugins) */
149 static
150 SCIP_DECL_HEURCOPY(heurCopyObjpscostdiving)
151 { /*lint --e{715}*/
152  assert(scip != NULL);
153  assert(heur != NULL);
154  assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0);
155 
156  /* call inclusion method of primal heuristic */
158 
159  return SCIP_OKAY;
160 }
161 
162 /** destructor of primal heuristic to free user data (called when SCIP is exiting) */
163 static
164 SCIP_DECL_HEURFREE(heurFreeObjpscostdiving) /*lint --e{715}*/
165 { /*lint --e{715}*/
166  SCIP_HEURDATA* heurdata;
167 
168  assert(heur != NULL);
169  assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0);
170  assert(scip != NULL);
171 
172  /* free heuristic data */
173  heurdata = SCIPheurGetData(heur);
174  assert(heurdata != NULL);
175  SCIPfreeBlockMemory(scip, &heurdata);
176  SCIPheurSetData(heur, NULL);
177 
178  return SCIP_OKAY;
179 }
180 
181 
182 /** initialization method of primal heuristic (called after problem was transformed) */
183 static
184 SCIP_DECL_HEURINIT(heurInitObjpscostdiving) /*lint --e{715}*/
185 { /*lint --e{715}*/
186  SCIP_HEURDATA* heurdata;
187 
188  assert(heur != NULL);
189  assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0);
190 
191  /* get heuristic data */
192  heurdata = SCIPheurGetData(heur);
193  assert(heurdata != NULL);
194 
195  /* create working solution */
196  SCIP_CALL( SCIPcreateSol(scip, &heurdata->sol, heur) );
197 
198  /* create random number generator */
199  SCIP_CALL( SCIPrandomCreate(&heurdata->randnumgen, SCIPblkmem(scip), SCIPinitializeRandomSeed(scip, DEFAULT_RANDSEED)) );
200 
201  /* initialize data */
202  heurdata->nlpiterations = 0;
203  heurdata->nsuccess = 0;
204 
205  return SCIP_OKAY;
206 }
207 
208 
209 /** deinitialization method of primal heuristic (called before transformed problem is freed) */
210 static
211 SCIP_DECL_HEUREXIT(heurExitObjpscostdiving) /*lint --e{715}*/
212 { /*lint --e{715}*/
213  SCIP_HEURDATA* heurdata;
214 
215  assert(heur != NULL);
216  assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0);
217 
218  /* get heuristic data */
219  heurdata = SCIPheurGetData(heur);
220  assert(heurdata != NULL);
221 
222  /* free random number generator */
223  SCIPrandomFree(&heurdata->randnumgen);
224 
225  /* free working solution */
226  SCIP_CALL( SCIPfreeSol(scip, &heurdata->sol) );
227 
228  return SCIP_OKAY;
229 }
230 
231 
232 /** execution method of primal heuristic */
233 static
234 SCIP_DECL_HEUREXEC(heurExecObjpscostdiving) /*lint --e{715}*/
235 { /*lint --e{715}*/
236  SCIP_HEURDATA* heurdata;
237  SCIP_LPSOLSTAT lpsolstat;
238  SCIP_VAR* var;
239  SCIP_VAR** lpcands;
240  SCIP_Real* lpcandssol;
241  SCIP_Real* lpcandsfrac;
242  SCIP_Real primsol;
243  SCIP_Real frac;
244  SCIP_Real pscostquot;
245  SCIP_Real bestpscostquot;
246  SCIP_Real oldobj;
247  SCIP_Real newobj;
248  SCIP_Real objscale;
249  SCIP_Bool bestcandmayrounddown;
250  SCIP_Bool bestcandmayroundup;
251  SCIP_Bool bestcandroundup;
252  SCIP_Bool mayrounddown;
253  SCIP_Bool mayroundup;
254  SCIP_Bool roundup;
255  SCIP_Bool lperror;
256  SCIP_Longint ncalls;
257  SCIP_Longint nsolsfound;
258  SCIP_Longint nlpiterations;
259  SCIP_Longint maxnlpiterations;
260  int* roundings;
261  int nvars;
262  int varidx;
263  int nlpcands;
264  int startnlpcands;
265  int depth;
266  int maxdepth;
267  int maxdivedepth;
268  int divedepth;
269  int bestcand;
270  int c;
271 
272  assert(heur != NULL);
273  assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0);
274  assert(scip != NULL);
275  assert(result != NULL);
276  assert(SCIPhasCurrentNodeLP(scip));
277 
278  *result = SCIP_DELAYED;
279 
280  /* do not call heuristic of node was already detected to be infeasible */
281  if( nodeinfeasible )
282  return SCIP_OKAY;
283 
284  /* only call heuristic, if an optimal LP solution is at hand */
286  return SCIP_OKAY;
287 
288  /* only call heuristic, if the LP objective value is smaller than the cutoff bound */
289  if( SCIPisGE(scip, SCIPgetLPObjval(scip), SCIPgetCutoffbound(scip)) )
290  return SCIP_OKAY;
291 
292  /* only call heuristic, if the LP solution is basic (which allows fast resolve in diving) */
293  if( !SCIPisLPSolBasic(scip) )
294  return SCIP_OKAY;
295 
296  /* don't dive two times at the same node */
297  if( SCIPgetLastDivenode(scip) == SCIPgetNNodes(scip) && SCIPgetDepth(scip) > 0 )
298  return SCIP_OKAY;
299 
300  *result = SCIP_DIDNOTRUN;
301 
302  /* get heuristic's data */
303  heurdata = SCIPheurGetData(heur);
304  assert(heurdata != NULL);
305 
306  /* only apply heuristic, if only a few solutions have been found */
307  if( heurdata->maxsols >= 0 && SCIPgetNSolsFound(scip) >= heurdata->maxsols )
308  return SCIP_OKAY;
309 
310  /* only try to dive, if we are in the correct part of the tree, given by minreldepth and maxreldepth */
311  depth = SCIPgetDepth(scip);
312  maxdepth = SCIPgetMaxDepth(scip);
313  maxdepth = MAX(maxdepth, 30);
314  if( depth < heurdata->minreldepth*maxdepth || depth > heurdata->maxreldepth*maxdepth )
315  return SCIP_OKAY;
316 
317  /* calculate the maximal number of LP iterations until heuristic is aborted */
318  nlpiterations = SCIPgetNNodeLPIterations(scip);
319  ncalls = SCIPheurGetNCalls(heur);
320  nsolsfound = 10*SCIPheurGetNBestSolsFound(heur) + heurdata->nsuccess;
321  maxnlpiterations = (SCIP_Longint)((1.0 + 10.0*(nsolsfound+1.0)/(ncalls+1.0)) * heurdata->maxlpiterquot * nlpiterations);
322  maxnlpiterations += heurdata->maxlpiterofs;
323 
324  /* don't try to dive, if we took too many LP iterations during diving */
325  if( heurdata->nlpiterations >= maxnlpiterations )
326  return SCIP_OKAY;
327 
328  /* allow at least a certain number of LP iterations in this dive */
329  maxnlpiterations = MAX(maxnlpiterations, heurdata->nlpiterations + MINLPITER);
330 
331  /* get fractional variables that should be integral */
332  SCIP_CALL( SCIPgetLPBranchCands(scip, &lpcands, &lpcandssol, &lpcandsfrac, &nlpcands, NULL, NULL) );
333 
334  /* don't try to dive, if there are no fractional variables */
335  if( nlpcands == 0 )
336  return SCIP_OKAY;
337 
338  /* calculate the maximal diving depth */
339  nvars = SCIPgetNBinVars(scip) + SCIPgetNIntVars(scip);
340  if( SCIPgetNSolsFound(scip) == 0 )
341  maxdivedepth = (int)(heurdata->depthfacnosol * nvars);
342  else
343  maxdivedepth = (int)(heurdata->depthfac * nvars);
344  maxdivedepth = MIN(maxdivedepth, 10*maxdepth);
345 
346 
347  *result = SCIP_DIDNOTFIND;
348 
349  /* get temporary memory for remembering the current soft roundings */
350  SCIP_CALL( SCIPallocBufferArray(scip, &roundings, nvars) );
351  BMSclearMemoryArray(roundings, nvars);
352 
353  /* start diving */
354  SCIP_CALL( SCIPstartDive(scip) );
355 
356  SCIPdebugMsg(scip, "(node %" SCIP_LONGINT_FORMAT ") executing objpscostdiving heuristic: depth=%d, %d fractionals, dualbound=%g, maxnlpiterations=%" SCIP_LONGINT_FORMAT ", maxdivedepth=%d\n",
357  SCIPgetNNodes(scip), SCIPgetDepth(scip), nlpcands, SCIPgetDualbound(scip), maxnlpiterations, maxdivedepth);
358 
359  /* dive as long we are in the given diving depth and iteration limits and fractional variables exist, but
360  * - if the last objective change was in a direction, that corresponds to a feasible rounding, we continue in any case
361  * - if possible, we dive at least with the depth 10
362  * - if the number of fractional variables decreased at least with 1 variable per 2 dive depths, we continue diving
363  */
364  lperror = FALSE;
365  lpsolstat = SCIP_LPSOLSTAT_OPTIMAL;
366  divedepth = 0;
367  startnlpcands = nlpcands;
368  while( !lperror && lpsolstat == SCIP_LPSOLSTAT_OPTIMAL && nlpcands > 0
369  && (divedepth < 10
370  || nlpcands <= startnlpcands - divedepth/2
371  || (divedepth < maxdivedepth && nlpcands <= startnlpcands - divedepth/10
372  && heurdata->nlpiterations < maxnlpiterations)) && !SCIPisStopped(scip) )
373  {
374  SCIP_RETCODE retcode;
375 
376  divedepth++;
377 
378  /* choose variable for objective change:
379  * - prefer variables that may not be rounded without destroying LP feasibility:
380  * - of these variables, change objective value of variable with largest rel. difference of pseudo cost values
381  * - if all remaining fractional variables may be rounded without destroying LP feasibility:
382  * - change objective value of variable with largest rel. difference of pseudo cost values
383  */
384  bestcand = -1;
385  bestpscostquot = -1.0;
386  bestcandmayrounddown = TRUE;
387  bestcandmayroundup = TRUE;
388  bestcandroundup = FALSE;
389  for( c = 0; c < nlpcands; ++c )
390  {
391  var = lpcands[c];
392  mayrounddown = SCIPvarMayRoundDown(var);
393  mayroundup = SCIPvarMayRoundUp(var);
394  primsol = lpcandssol[c];
395  frac = lpcandsfrac[c];
396  if( mayrounddown || mayroundup )
397  {
398  /* the candidate may be rounded: choose this candidate only, if the best candidate may also be rounded */
399  if( bestcandmayrounddown || bestcandmayroundup )
400  {
401  /* choose rounding direction:
402  * - if variable may be rounded in both directions, round corresponding to the pseudo cost values
403  * - otherwise, round in the infeasible direction, because feasible direction is tried by rounding
404  * the current fractional solution
405  */
406  roundup = FALSE;
407  if( mayrounddown && mayroundup )
408  calcPscostQuot(scip, heurdata, var, primsol, frac, 0, &pscostquot, &roundup);
409  else if( mayrounddown )
410  calcPscostQuot(scip, heurdata, var, primsol, frac, +1, &pscostquot, &roundup);
411  else
412  calcPscostQuot(scip, heurdata, var, primsol, frac, -1, &pscostquot, &roundup);
413 
414  /* prefer variables, that have already been soft rounded but failed to get integral */
415  varidx = SCIPvarGetProbindex(var);
416  assert(0 <= varidx && varidx < nvars);
417  if( roundings[varidx] != 0 )
418  pscostquot *= 1000.0;
419 
420  /* check, if candidate is new best candidate */
421  if( pscostquot > bestpscostquot )
422  {
423  bestcand = c;
424  bestpscostquot = pscostquot;
425  bestcandmayrounddown = mayrounddown;
426  bestcandmayroundup = mayroundup;
427  bestcandroundup = roundup;
428  }
429  }
430  }
431  else
432  {
433  /* the candidate may not be rounded: calculate pseudo cost quotient and preferred direction */
434  calcPscostQuot(scip, heurdata, var, primsol, frac, 0, &pscostquot, &roundup);
435 
436  /* prefer variables, that have already been soft rounded but failed to get integral */
437  varidx = SCIPvarGetProbindex(var);
438  assert(0 <= varidx && varidx < nvars);
439  if( roundings[varidx] != 0 )
440  pscostquot *= 1000.0;
441 
442  /* check, if candidate is new best candidate: prefer unroundable candidates in any case */
443  if( bestcandmayrounddown || bestcandmayroundup || pscostquot > bestpscostquot )
444  {
445  bestcand = c;
446  bestpscostquot = pscostquot;
447  bestcandmayrounddown = FALSE;
448  bestcandmayroundup = FALSE;
449  bestcandroundup = roundup;
450  }
451  }
452  }
453  assert(bestcand != -1);
454 
455  /* if all candidates are roundable, try to round the solution */
456  if( bestcandmayrounddown || bestcandmayroundup )
457  {
458  SCIP_Bool success;
459 
460  /* create solution from diving LP and try to round it */
461  SCIP_CALL( SCIPlinkLPSol(scip, heurdata->sol) );
462  SCIP_CALL( SCIProundSol(scip, heurdata->sol, &success) );
463 
464  if( success )
465  {
466  SCIPdebugMsg(scip, "objpscostdiving found roundable primal solution: obj=%g\n",
467  SCIPgetSolOrigObj(scip, heurdata->sol));
468 
469  /* try to add solution to SCIP */
470  SCIP_CALL( SCIPtrySol(scip, heurdata->sol, FALSE, FALSE, FALSE, FALSE, FALSE, &success) );
471 
472  /* check, if solution was feasible and good enough */
473  if( success )
474  {
475  SCIPdebugMsg(scip, " -> solution was feasible and good enough\n");
476  *result = SCIP_FOUNDSOL;
477  }
478  }
479  }
480 
481  var = lpcands[bestcand];
482 
483  /* check, if the best candidate was already subject to soft rounding */
484  varidx = SCIPvarGetProbindex(var);
485  assert(0 <= varidx && varidx < nvars);
486  if( roundings[varidx] == +1 )
487  {
488  /* variable was already soft rounded upwards: hard round it downwards */
489  SCIP_CALL( SCIPchgVarUbDive(scip, var, SCIPfeasFloor(scip, lpcandssol[bestcand])) );
490  SCIPdebugMsg(scip, " dive %d/%d: var <%s>, round=%u/%u, sol=%g, was already soft rounded upwards -> bounds=[%g,%g]\n",
491  divedepth, maxdivedepth, SCIPvarGetName(var), bestcandmayrounddown, bestcandmayroundup,
492  lpcandssol[bestcand], SCIPgetVarLbDive(scip, var), SCIPgetVarUbDive(scip, var));
493  }
494  else if( roundings[varidx] == -1 )
495  {
496  /* variable was already soft rounded downwards: hard round it upwards */
497  SCIP_CALL( SCIPchgVarLbDive(scip, var, SCIPfeasCeil(scip, lpcandssol[bestcand])) );
498  SCIPdebugMsg(scip, " dive %d/%d: var <%s>, round=%u/%u, sol=%g, was already soft rounded downwards -> bounds=[%g,%g]\n",
499  divedepth, maxdivedepth, SCIPvarGetName(var), bestcandmayrounddown, bestcandmayroundup,
500  lpcandssol[bestcand], SCIPgetVarLbDive(scip, var), SCIPgetVarUbDive(scip, var));
501  }
502  else
503  {
504  assert(roundings[varidx] == 0);
505 
506  /* apply soft rounding of best candidate via a change in the objective value */
507  objscale = divedepth * 1000.0;
508  oldobj = SCIPgetVarObjDive(scip, var);
509  if( bestcandroundup )
510  {
511  /* soft round variable up: make objective value (more) negative */
512  if( oldobj < 0.0 )
513  newobj = objscale * oldobj;
514  else
515  newobj = -objscale * oldobj;
516  newobj = MIN(newobj, -objscale);
517 
518  /* remember, that this variable was soft rounded upwards */
519  roundings[varidx] = +1;
520  }
521  else
522  {
523  /* soft round variable down: make objective value (more) positive */
524  if( oldobj > 0.0 )
525  newobj = objscale * oldobj;
526  else
527  newobj = -objscale * oldobj;
528  newobj = MAX(newobj, objscale);
529 
530  /* remember, that this variable was soft rounded downwards */
531  roundings[varidx] = -1;
532  }
533  SCIP_CALL( SCIPchgVarObjDive(scip, var, newobj) );
534  SCIPdebugMsg(scip, " dive %d/%d, LP iter %" SCIP_LONGINT_FORMAT "/%" SCIP_LONGINT_FORMAT ": var <%s>, round=%u/%u, sol=%g, bounds=[%g,%g], obj=%g, newobj=%g\n",
535  divedepth, maxdivedepth, heurdata->nlpiterations, maxnlpiterations,
536  SCIPvarGetName(var), bestcandmayrounddown, bestcandmayroundup,
537  lpcandssol[bestcand], SCIPgetVarLbDive(scip, var), SCIPgetVarUbDive(scip, var), oldobj, newobj);
538  }
539 
540  /* resolve the diving LP */
541  nlpiterations = SCIPgetNLPIterations(scip);
542  retcode = SCIPsolveDiveLP(scip, MAX((int)(maxnlpiterations - heurdata->nlpiterations), MINLPITER), &lperror, NULL);
543  lpsolstat = SCIPgetLPSolstat(scip);
544 
545  /* Errors in the LP solver should not kill the overall solving process, if the LP is just needed for a heuristic.
546  * Hence in optimized mode, the return code is caught and a warning is printed, only in debug mode, SCIP will stop.
547  */
548  if( retcode != SCIP_OKAY )
549  {
550 #ifndef NDEBUG
551  if( lpsolstat != SCIP_LPSOLSTAT_UNBOUNDEDRAY )
552  {
553  SCIP_CALL( retcode );
554  }
555 #endif
556  SCIPwarningMessage(scip, "Error while solving LP in Objpscostdiving heuristic; LP solve terminated with code <%d>\n", retcode);
557  SCIPwarningMessage(scip, "This does not affect the remaining solution procedure --> continue\n");
558  }
559 
560  if( lperror )
561  break;
562 
563  /* update iteration count */
564  heurdata->nlpiterations += SCIPgetNLPIterations(scip) - nlpiterations;
565 
566  /* get LP solution status and fractional variables, that should be integral */
567  if( lpsolstat == SCIP_LPSOLSTAT_OPTIMAL )
568  {
569  /* get new fractional variables */
570  SCIP_CALL( SCIPgetLPBranchCands(scip, &lpcands, &lpcandssol, &lpcandsfrac, &nlpcands, NULL, NULL) );
571  }
572  SCIPdebugMsg(scip, " -> lpsolstat=%d, nfrac=%d\n", lpsolstat, nlpcands);
573  }
574 
575  /* check if a solution has been found */
576  if( nlpcands == 0 && !lperror && lpsolstat == SCIP_LPSOLSTAT_OPTIMAL )
577  {
578  SCIP_Bool success;
579 
580  /* create solution from diving LP */
581  SCIP_CALL( SCIPlinkLPSol(scip, heurdata->sol) );
582  SCIPdebugMsg(scip, "objpscostdiving found primal solution: obj=%g\n", SCIPgetSolOrigObj(scip, heurdata->sol));
583 
584  /* try to add solution to SCIP */
585  SCIP_CALL( SCIPtrySol(scip, heurdata->sol, FALSE, FALSE, FALSE, FALSE, FALSE, &success) );
586 
587  /* check, if solution was feasible and good enough */
588  if( success )
589  {
590  SCIPdebugMsg(scip, " -> solution was feasible and good enough\n");
591  *result = SCIP_FOUNDSOL;
592  }
593  }
594 
595  /* end diving */
596  SCIP_CALL( SCIPendDive(scip) );
597 
598  if( *result == SCIP_FOUNDSOL )
599  heurdata->nsuccess++;
600 
601  /* free temporary memory for remembering the current soft roundings */
602  SCIPfreeBufferArray(scip, &roundings);
603 
604  SCIPdebugMsg(scip, "objpscostdiving heuristic finished\n");
605 
606  return SCIP_OKAY;
607 }
608 
609 
610 /*
611  * heuristic specific interface methods
612  */
613 
614 /** creates the objpscostdiving heuristic and includes it in SCIP */
616  SCIP* scip /**< SCIP data structure */
617  )
618 {
619  SCIP_HEURDATA* heurdata;
620  SCIP_HEUR* heur;
621 
622  /* create Objpscostdiving primal heuristic data */
623  SCIP_CALL( SCIPallocBlockMemory(scip, &heurdata) );
624 
625  /* include primal heuristic */
626  SCIP_CALL( SCIPincludeHeurBasic(scip, &heur,
628  HEUR_MAXDEPTH, HEUR_TIMING, HEUR_USESSUBSCIP, heurExecObjpscostdiving, heurdata) );
629 
630  assert(heur != NULL);
631 
632  /* set non-NULL pointers to callback methods */
633  SCIP_CALL( SCIPsetHeurCopy(scip, heur, heurCopyObjpscostdiving) );
634  SCIP_CALL( SCIPsetHeurFree(scip, heur, heurFreeObjpscostdiving) );
635  SCIP_CALL( SCIPsetHeurInit(scip, heur, heurInitObjpscostdiving) );
636  SCIP_CALL( SCIPsetHeurExit(scip, heur, heurExitObjpscostdiving) );
637 
638  /* objpscostdiving heuristic parameters */
640  "heuristics/objpscostdiving/minreldepth",
641  "minimal relative depth to start diving",
642  &heurdata->minreldepth, TRUE, DEFAULT_MINRELDEPTH, 0.0, 1.0, NULL, NULL) );
644  "heuristics/objpscostdiving/maxreldepth",
645  "maximal relative depth to start diving",
646  &heurdata->maxreldepth, TRUE, DEFAULT_MAXRELDEPTH, 0.0, 1.0, NULL, NULL) );
648  "heuristics/objpscostdiving/maxlpiterquot",
649  "maximal fraction of diving LP iterations compared to total iteration number",
650  &heurdata->maxlpiterquot, FALSE, DEFAULT_MAXLPITERQUOT, 0.0, 1.0, NULL, NULL) );
652  "heuristics/objpscostdiving/maxlpiterofs",
653  "additional number of allowed LP iterations",
654  &heurdata->maxlpiterofs, FALSE, DEFAULT_MAXLPITEROFS, 0, INT_MAX, NULL, NULL) );
656  "heuristics/objpscostdiving/maxsols",
657  "total number of feasible solutions found up to which heuristic is called (-1: no limit)",
658  &heurdata->maxsols, TRUE, DEFAULT_MAXSOLS, -1, INT_MAX, NULL, NULL) );
660  "heuristics/objpscostdiving/depthfac",
661  "maximal diving depth: number of binary/integer variables times depthfac",
662  &heurdata->depthfac, TRUE, DEFAULT_DEPTHFAC, 0.0, SCIP_REAL_MAX, NULL, NULL) );
664  "heuristics/objpscostdiving/depthfacnosol",
665  "maximal diving depth factor if no feasible solution was found yet",
666  &heurdata->depthfacnosol, TRUE, DEFAULT_DEPTHFACNOSOL, 0.0, SCIP_REAL_MAX, NULL, NULL) );
667 
668  return SCIP_OKAY;
669 }
670 
#define HEUR_USESSUBSCIP
SCIP_RETCODE SCIPgetLPBranchCands(SCIP *scip, SCIP_VAR ***lpcands, SCIP_Real **lpcandssol, SCIP_Real **lpcandsfrac, int *nlpcands, int *npriolpcands, int *nfracimplvars)
Definition: scip.c:36301
int SCIPgetNIntVars(SCIP *scip)
Definition: scip.c:11770
SCIP_RETCODE SCIPrandomCreate(SCIP_RANDNUMGEN **randnumgen, BMS_BLKMEM *blkmem, unsigned int initialseed)
Definition: misc.c:8693
#define DEFAULT_MINRELDEPTH
SCIP_RETCODE SCIPlinkLPSol(SCIP *scip, SCIP_SOL *sol)
Definition: scip.c:37847
SCIP_Longint SCIPgetNLPIterations(SCIP *scip)
Definition: scip.c:41609
SCIP_Real SCIPgetCutoffbound(SCIP *scip)
Definition: scip.c:42726
SCIP_Real SCIPgetVarPseudocostVal(SCIP *scip, SCIP_VAR *var, SCIP_Real solvaldelta)
Definition: scip.c:25687
SCIP_Longint SCIPheurGetNBestSolsFound(SCIP_HEUR *heur)
Definition: heur.c:1327
SCIP_Longint SCIPgetNSolsFound(SCIP *scip)
Definition: scip.c:42891
#define DEFAULT_MAXLPITEROFS
SCIP_RETCODE SCIPsetHeurExit(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEUREXIT((*heurexit)))
Definition: scip.c:8127
SCIP_Bool SCIPisGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip.c:46037
#define DEFAULT_MAXLPITERQUOT
SCIP_Bool SCIPvarIsBinary(SCIP_VAR *var)
Definition: var.c:16735
SCIP_Real SCIPvarGetRootSol(SCIP_VAR *var)
Definition: var.c:12654
int SCIPgetMaxDepth(SCIP *scip)
Definition: scip.c:42371
#define DEFAULT_MAXRELDEPTH
#define FALSE
Definition: def.h:64
#define DEFAULT_RANDSEED
static SCIP_DECL_HEURINIT(heurInitObjpscostdiving)
#define TRUE
Definition: def.h:63
#define DEFAULT_DEPTHFAC
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:53
SCIP_RETCODE SCIPchgVarLbDive(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound)
Definition: scip.c:34772
int SCIPvarGetProbindex(SCIP_VAR *var)
Definition: var.c:16862
struct SCIP_HeurData SCIP_HEURDATA
Definition: type_heur.h:51
#define SCIPfreeBlockMemory(scip, ptr)
Definition: scip.h:21973
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:8034
int SCIPrandomGetInt(SCIP_RANDNUMGEN *randnumgen, int minrandval, int maxrandval)
Definition: misc.c:8723
SCIP_Bool SCIPisEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip.c:45985
#define SCIPfreeBufferArray(scip, ptr)
Definition: scip.h:22003
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:21956
static SCIP_DECL_HEURFREE(heurFreeObjpscostdiving)
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:4237
SCIP_Real SCIPfeasCeil(SCIP *scip, SCIP_Real val)
Definition: scip.c:46457
#define HEUR_DISPCHAR
SCIP_Real SCIPfeasFloor(SCIP *scip, SCIP_Real val)
Definition: scip.c:46445
#define DEFAULT_MAXSOLS
SCIP_Bool SCIPisLPSolBasic(SCIP *scip)
Definition: scip.c:29392
void SCIPrandomFree(SCIP_RANDNUMGEN **randnumgen)
Definition: misc.c:8710
SCIP_Real SCIPgetVarUbDive(SCIP *scip, SCIP_VAR *var)
Definition: scip.c:34998
const char * SCIPheurGetName(SCIP_HEUR *heur)
Definition: heur.c:1181
#define HEUR_FREQ
static SCIP_DECL_HEUREXEC(heurExecObjpscostdiving)
SCIP_RETCODE SCIPsolveDiveLP(SCIP *scip, int itlim, SCIP_Bool *lperror, SCIP_Bool *cutoff)
Definition: scip.c:35031
SCIP_RETCODE SCIPsetHeurFree(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURFREE((*heurfree)))
Definition: scip.c:8095
SCIP_Bool SCIPisLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip.c:45998
SCIP_Real SCIPgetDualbound(SCIP *scip)
Definition: scip.c:42529
#define HEUR_FREQOFS
#define HEUR_NAME
SCIPInterval sqrt(const SCIPInterval &x)
BMS_BLKMEM * SCIPblkmem(SCIP *scip)
Definition: scip.c:45753
SCIP_RETCODE SCIPincludeHeurObjpscostdiving(SCIP *scip)
const char * SCIPvarGetName(SCIP_VAR *var)
Definition: var.c:16555
#define NULL
Definition: lpi_spx1.cpp:137
#define HEUR_TIMING
#define SCIP_CALL(x)
Definition: def.h:316
SCIP_Longint SCIPheurGetNCalls(SCIP_HEUR *heur)
Definition: heur.c:1307
#define DEFAULT_DEPTHFACNOSOL
SCIP_Bool SCIPhasCurrentNodeLP(SCIP *scip)
Definition: scip.c:28863
SCIP_Longint SCIPgetLastDivenode(SCIP *scip)
Definition: scip.c:35099
SCIP_Longint SCIPgetNNodeLPIterations(SCIP *scip)
Definition: scip.c:41930
#define HEUR_MAXDEPTH
#define SCIPallocBufferArray(scip, ptr, num)
Definition: scip.h:21991
#define SCIP_Bool
Definition: def.h:61
SCIP_LPSOLSTAT SCIPgetLPSolstat(SCIP *scip)
Definition: scip.c:28948
SCIP_RETCODE SCIProundSol(SCIP *scip, SCIP_SOL *sol, SCIP_Bool *success)
Definition: scip.c:39300
int SCIPgetDepth(SCIP *scip)
Definition: scip.c:42321
SCIP_RETCODE SCIPchgVarUbDive(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound)
Definition: scip.c:34804
static void calcPscostQuot(SCIP *scip, SCIP_HEURDATA *heurdata, SCIP_VAR *var, SCIP_Real primsol, SCIP_Real frac, int rounddir, SCIP_Real *pscostquot, SCIP_Bool *roundup)
#define MAX(x, y)
Definition: tclique_def.h:75
static SCIP_DECL_HEURCOPY(heurCopyObjpscostdiving)
unsigned int SCIPinitializeRandomSeed(SCIP *scip, int initialseedvalue)
Definition: scip.c:25561
SCIP_RETCODE SCIPfreeSol(SCIP *scip, SCIP_SOL **sol)
Definition: scip.c:37806
SCIP_Real SCIPgetSolOrigObj(SCIP *scip, SCIP_SOL *sol)
Definition: scip.c:38268
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:39976
int SCIPgetNBinVars(SCIP *scip)
Definition: scip.c:11725
#define SCIP_REAL_MAX
Definition: def.h:146
SCIP_Real SCIPgetLPObjval(SCIP *scip)
Definition: scip.c:29027
SCIP_Bool SCIPisGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip.c:46024
SCIP_RETCODE SCIPchgVarObjDive(SCIP *scip, SCIP_VAR *var, SCIP_Real newobj)
Definition: scip.c:34731
#define HEUR_PRIORITY
SCIP_RETCODE SCIPsetHeurInit(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURINIT((*heurinit)))
Definition: scip.c:8111
#define SCIP_Real
Definition: def.h:145
SCIP_Bool SCIPisStopped(SCIP *scip)
Definition: scip.c:1138
#define MIN(x, y)
Definition: memory.c:75
#define MINLPITER
#define SCIP_Longint
Definition: def.h:130
static SCIP_DECL_HEUREXIT(heurExitObjpscostdiving)
SCIP_Real SCIPgetVarLbDive(SCIP *scip, SCIP_VAR *var)
Definition: scip.c:34969
SCIP_RETCODE SCIPstartDive(SCIP *scip)
Definition: scip.c:34607
SCIP_RETCODE SCIPsetHeurCopy(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURCOPY((*heurcopy)))
Definition: scip.c:8079
#define BMSclearMemoryArray(ptr, num)
Definition: memory.h:89
SCIP_RETCODE SCIPendDive(SCIP *scip)
Definition: scip.c:34650
SCIP_HEURDATA * SCIPheurGetData(SCIP_HEUR *heur)
Definition: heur.c:1092
LP diving heuristic that changes variable&#39;s objective value instead of bounds, using pseudo cost valu...
SCIP_Longint SCIPgetNNodes(SCIP *scip)
Definition: scip.c:41409
SCIP_Real SCIPgetVarObjDive(SCIP *scip, SCIP_VAR *var)
Definition: scip.c:34940
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:4293
SCIP_Bool SCIPvarMayRoundUp(SCIP_VAR *var)
Definition: var.c:3280
SCIP_Bool SCIPvarMayRoundDown(SCIP_VAR *var)
Definition: var.c:3272
#define HEUR_DESC
SCIP_RETCODE SCIPcreateSol(SCIP *scip, SCIP_SOL **sol, SCIP_HEUR *heur)
Definition: scip.c:37178