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