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