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