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-2024 Zuse Institute Berlin (ZIB) */
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
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"
49#include "scip/scip_sol.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 */
84struct 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
105static
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) */
175static
176SCIP_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) */
189static
190SCIP_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) */
209static
210SCIP_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) */
236static
237SCIP_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 */
259static
260SCIP_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 */
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 */
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 */
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 */
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 */
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 */
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 NULL
Definition: def.h:267
#define SCIP_Longint
Definition: def.h:158
#define SCIP_REAL_MAX
Definition: def.h:174
#define SCIP_Bool
Definition: def.h:91
#define MIN(x, y)
Definition: def.h:243
#define SCIP_Real
Definition: def.h:173
#define TRUE
Definition: def.h:93
#define FALSE
Definition: def.h:94
#define MAX(x, y)
Definition: def.h:239
#define SCIP_LONGINT_FORMAT
Definition: def.h:165
#define SCIP_CALL(x)
Definition: def.h:374
SCIP_Bool SCIPisStopped(SCIP *scip)
Definition: scip_general.c:724
int SCIPgetNIntVars(SCIP *scip)
Definition: scip_prob.c:2082
int SCIPgetNBinVars(SCIP *scip)
Definition: scip_prob.c:2037
#define SCIPdebugMsg
Definition: scip_message.h:78
void SCIPwarningMessage(SCIP *scip, const char *formatstr,...)
Definition: scip_message.c:120
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_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_RETCODE SCIPincludeHeurObjpscostdiving(SCIP *scip)
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
SCIP_RETCODE SCIPsetHeurCopy(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURCOPY((*heurcopy)))
Definition: scip_heur.c:162
SCIP_HEURDATA * SCIPheurGetData(SCIP_HEUR *heur)
Definition: heur.c:1364
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
SCIP_RETCODE SCIPsetHeurFree(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURFREE((*heurfree)))
Definition: scip_heur.c:178
SCIP_RETCODE SCIPsetHeurExit(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEUREXIT((*heurexit)))
Definition: scip_heur.c:210
SCIP_Longint SCIPheurGetNBestSolsFound(SCIP_HEUR *heur)
Definition: heur.c:1599
SCIP_Longint SCIPheurGetNCalls(SCIP_HEUR *heur)
Definition: heur.c:1579
SCIP_RETCODE SCIPsetHeurInit(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURINIT((*heurinit)))
Definition: scip_heur.c:194
const char * SCIPheurGetName(SCIP_HEUR *heur)
Definition: heur.c:1453
void SCIPheurSetData(SCIP_HEUR *heur, SCIP_HEURDATA *heurdata)
Definition: heur.c:1374
SCIP_RETCODE SCIPchgVarLbDive(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound)
Definition: scip_lp.c:2419
SCIP_RETCODE SCIPchgVarUbDive(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound)
Definition: scip_lp.c:2451
SCIP_Real SCIPgetVarLbDive(SCIP *scip, SCIP_VAR *var)
Definition: scip_lp.c:2616
SCIP_Real SCIPgetVarUbDive(SCIP *scip, SCIP_VAR *var)
Definition: scip_lp.c:2645
SCIP_Real SCIPgetVarObjDive(SCIP *scip, SCIP_VAR *var)
Definition: scip_lp.c:2587
SCIP_RETCODE SCIPstartDive(SCIP *scip)
Definition: scip_lp.c:2242
SCIP_RETCODE SCIPchgVarObjDive(SCIP *scip, SCIP_VAR *var, SCIP_Real newobj)
Definition: scip_lp.c:2378
SCIP_RETCODE SCIPsolveDiveLP(SCIP *scip, int itlim, SCIP_Bool *lperror, SCIP_Bool *cutoff)
Definition: scip_lp.c:2678
SCIP_RETCODE SCIPendDive(SCIP *scip)
Definition: scip_lp.c:2291
SCIP_Longint SCIPgetLastDivenode(SCIP *scip)
Definition: scip_lp.c:2745
SCIP_Bool SCIPhasCurrentNodeLP(SCIP *scip)
Definition: scip_lp.c:83
SCIP_LPSOLSTAT SCIPgetLPSolstat(SCIP *scip)
Definition: scip_lp.c:168
SCIP_Real SCIPgetLPObjval(SCIP *scip)
Definition: scip_lp.c:247
SCIP_Bool SCIPisLPSolBasic(SCIP *scip)
Definition: scip_lp.c:667
#define SCIPallocBufferArray(scip, ptr, num)
Definition: scip_mem.h:124
#define SCIPfreeBufferArray(scip, ptr)
Definition: scip_mem.h:136
#define SCIPfreeBlockMemory(scip, ptr)
Definition: scip_mem.h:108
#define SCIPallocBlockMemory(scip, ptr)
Definition: scip_mem.h:89
SCIP_RETCODE SCIPcreateSol(SCIP *scip, SCIP_SOL **sol, SCIP_HEUR *heur)
Definition: scip_sol.c:184
SCIP_RETCODE SCIPfreeSol(SCIP *scip, SCIP_SOL **sol)
Definition: scip_sol.c:841
SCIP_RETCODE SCIProundSol(SCIP *scip, SCIP_SOL *sol, SCIP_Bool *success)
Definition: scip_sol.c:2311
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:2954
SCIP_RETCODE SCIPlinkLPSol(SCIP *scip, SCIP_SOL *sol)
Definition: scip_sol.c:882
SCIP_Real SCIPgetSolOrigObj(SCIP *scip, SCIP_SOL *sol)
Definition: scip_sol.c:1300
SCIP_Longint SCIPgetNSolsFound(SCIP *scip)
int SCIPgetMaxDepth(SCIP *scip)
SCIP_Longint SCIPgetNNodes(SCIP *scip)
SCIP_Real SCIPgetDualbound(SCIP *scip)
SCIP_Longint SCIPgetNNodeLPIterations(SCIP *scip)
SCIP_Real SCIPgetCutoffbound(SCIP *scip)
SCIP_Longint SCIPgetNLPIterations(SCIP *scip)
SCIP_Bool SCIPisGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Real SCIPfeasCeil(SCIP *scip, SCIP_Real val)
SCIP_Real SCIPfeasFloor(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
int SCIPgetDepth(SCIP *scip)
Definition: scip_tree.c:670
SCIP_Bool SCIPvarMayRoundUp(SCIP_VAR *var)
Definition: var.c:3451
SCIP_Bool SCIPvarIsBinary(SCIP_VAR *var)
Definition: var.c:17599
SCIP_Bool SCIPvarMayRoundDown(SCIP_VAR *var)
Definition: var.c:3440
int SCIPvarGetProbindex(SCIP_VAR *var)
Definition: var.c:17768
const char * SCIPvarGetName(SCIP_VAR *var)
Definition: var.c:17419
SCIP_Real SCIPvarGetRootSol(SCIP_VAR *var)
Definition: var.c:13350
SCIP_Real SCIPgetVarPseudocostVal(SCIP *scip, SCIP_VAR *var, SCIP_Real solvaldelta)
Definition: scip_var.c:8814
void SCIPfreeRandom(SCIP *scip, SCIP_RANDNUMGEN **randnumgen)
int SCIPrandomGetInt(SCIP_RANDNUMGEN *randnumgen, int minrandval, int maxrandval)
Definition: misc.c:10108
SCIP_RETCODE SCIPcreateRandom(SCIP *scip, SCIP_RANDNUMGEN **randnumgen, unsigned int initialseed, SCIP_Bool useglobalseed)
static void calcPscostQuot(SCIP *scip, SCIP_HEURDATA *heurdata, SCIP_VAR *var, SCIP_Real primsol, SCIP_Real frac, int rounddir, SCIP_Real *pscostquot, SCIP_Bool *roundup)
static SCIP_DECL_HEUREXEC(heurExecObjpscostdiving)
#define DEFAULT_DEPTHFAC
#define HEUR_TIMING
static SCIP_DECL_HEUREXIT(heurExitObjpscostdiving)
#define DEFAULT_MAXLPITERQUOT
#define HEUR_FREQOFS
#define HEUR_DESC
static SCIP_DECL_HEURINIT(heurInitObjpscostdiving)
#define MINLPITER
#define HEUR_DISPCHAR
#define HEUR_MAXDEPTH
#define HEUR_PRIORITY
#define DEFAULT_MAXRELDEPTH
#define DEFAULT_MAXLPITEROFS
#define HEUR_NAME
#define DEFAULT_DEPTHFACNOSOL
#define DEFAULT_RANDSEED
static SCIP_DECL_HEURCOPY(heurCopyObjpscostdiving)
#define HEUR_FREQ
#define DEFAULT_MINRELDEPTH
#define DEFAULT_MAXSOLS
#define HEUR_USESSUBSCIP
static SCIP_DECL_HEURFREE(heurFreeObjpscostdiving)
LP diving heuristic that changes variable's objective value instead of bounds, using pseudo cost valu...
memory allocation routines
#define BMSclearMemoryArray(ptr, num)
Definition: memory.h:130
public methods for primal heuristics
public methods for message output
public data structures and miscellaneous methods
public methods for problem variables
public methods for branching rule plugins and branching
general public methods
public methods for primal heuristic plugins and divesets
public methods for the LP relaxation, rows and columns
public methods for memory management
public methods for message handling
public methods for numerical tolerances
public methods for SCIP parameter handling
public methods for global and local (sub)problems
public methods for random numbers
public methods for solutions
public methods for querying solving statistics
public methods for the branch-and-bound tree
public methods for SCIP variables
struct SCIP_HeurData SCIP_HEURDATA
Definition: type_heur.h:77
enum SCIP_LPSolStat SCIP_LPSOLSTAT
Definition: type_lp.h:51
@ SCIP_LPSOLSTAT_OPTIMAL
Definition: type_lp.h:43
@ SCIP_LPSOLSTAT_UNBOUNDEDRAY
Definition: type_lp.h:45
@ SCIP_DIDNOTRUN
Definition: type_result.h:42
@ SCIP_DELAYED
Definition: type_result.h:43
@ SCIP_DIDNOTFIND
Definition: type_result.h:44
@ SCIP_FOUNDSOL
Definition: type_result.h:56
@ SCIP_OKAY
Definition: type_retcode.h:42
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:63