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