Scippy

SCIP

Solving Constraint Integer Programs

heur_rootsoldiving.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_rootsoldiving.c
26 * @ingroup DEFPLUGINS_HEUR
27 * @brief LP diving heuristic that changes variable's objective values using root LP solution as guide
28 * @author Kati Wolter
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_var.h"
38#include "scip/scip_branch.h"
39#include "scip/scip_general.h"
40#include "scip/scip_heur.h"
41#include "scip/scip_lp.h"
42#include "scip/scip_mem.h"
43#include "scip/scip_message.h"
44#include "scip/scip_numerics.h"
45#include "scip/scip_param.h"
46#include "scip/scip_prob.h"
47#include "scip/scip_sol.h"
49#include "scip/scip_tree.h"
50#include <string.h>
51
52#define HEUR_NAME "rootsoldiving"
53#define HEUR_DESC "LP diving heuristic that changes variable's objective values using root LP solution as guide"
54#define HEUR_DISPCHAR SCIP_HEURDISPCHAR_OBJDIVING
55#define HEUR_PRIORITY -1005000
56#define HEUR_FREQ 20
57#define HEUR_FREQOFS 5
58#define HEUR_MAXDEPTH -1
59#define HEUR_TIMING SCIP_HEURTIMING_AFTERLPPLUNGE
60#define HEUR_USESSUBSCIP FALSE /**< does the heuristic use a secondary SCIP instance? */
61
62
63/*
64 * Default parameter settings
65 */
66
67#define DEFAULT_MINRELDEPTH 0.0 /**< minimal relative depth to start diving */
68#define DEFAULT_MAXRELDEPTH 1.0 /**< maximal relative depth to start diving */
69#define DEFAULT_MAXLPITERQUOT 0.01 /**< maximal fraction of diving LP iterations compared to node LP iterations */
70#define DEFAULT_MAXLPITEROFS 1000 /**< additional number of allowed LP iterations */
71#define DEFAULT_MAXSOLS -1 /**< total number of feasible solutions found up to which heuristic is called
72 * (-1: no limit) */
73#define DEFAULT_DEPTHFAC 0.5 /**< maximal diving depth: number of binary/integer variables times depthfac */
74#define DEFAULT_DEPTHFACNOSOL 2.0 /**< maximal diving depth factor if no feasible solution was found yet */
75
76#define MINLPITER 10000 /**< minimal number of LP iterations allowed in each LP solving call */
77#define DEFAULT_ALPHA 0.9 /**< soft rounding factor to fade out objective coefficients */
78
79
80/* locally defined heuristic data */
81struct SCIP_HeurData
82{
83 SCIP_SOL* sol; /**< working solution */
84 SCIP_Real minreldepth; /**< minimal relative depth to start diving */
85 SCIP_Real maxreldepth; /**< maximal relative depth to start diving */
86 SCIP_Real maxlpiterquot; /**< maximal fraction of diving LP iterations compared to node LP iterations */
87 int maxlpiterofs; /**< additional number of allowed LP iterations */
88 int maxsols; /**< total number of feasible solutions found up to which heuristic is called
89 * (-1: no limit) */
90 SCIP_Real depthfac; /**< maximal diving depth: number of binary/integer variables times depthfac */
91 SCIP_Real depthfacnosol; /**< maximal diving depth factor if no feasible solution was found yet */
92 SCIP_Real alpha; /**< soft rounding factor to fade out objective coefficients */
93 SCIP_Longint nlpiterations; /**< LP iterations used in this heuristic */
94 int nsuccess; /**< number of runs that produced at least one feasible solution */
95};
96
97
98/*
99 * Callback methods
100 */
101
102/** copy method for primal heuristic plugins (called when SCIP copies plugins) */
103static
104SCIP_DECL_HEURCOPY(heurCopyRootsoldiving)
105{ /*lint --e{715}*/
106 assert(scip != NULL);
107 assert(heur != NULL);
108 assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0);
109
110 /* call inclusion method of primal heuristic */
112
113 return SCIP_OKAY;
114}
115
116/** destructor of primal heuristic to free user data (called when SCIP is exiting) */
117static
118SCIP_DECL_HEURFREE(heurFreeRootsoldiving) /*lint --e{715}*/
119{ /*lint --e{715}*/
120 SCIP_HEURDATA* heurdata;
121
122 assert(heur != NULL);
123 assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0);
124 assert(scip != NULL);
125
126 /* free heuristic data */
127 heurdata = SCIPheurGetData(heur);
128 assert(heurdata != NULL);
129 SCIPfreeBlockMemory(scip, &heurdata);
130 SCIPheurSetData(heur, NULL);
131
132 return SCIP_OKAY;
133}
134
135
136/** initialization method of primal heuristic (called after problem was transformed) */
137static
138SCIP_DECL_HEURINIT(heurInitRootsoldiving) /*lint --e{715}*/
139{ /*lint --e{715}*/
140 SCIP_HEURDATA* heurdata;
141
142 assert(heur != NULL);
143 assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0);
144
145 /* get heuristic data */
146 heurdata = SCIPheurGetData(heur);
147 assert(heurdata != NULL);
148
149 /* create working solution */
150 SCIP_CALL( SCIPcreateSol(scip, &heurdata->sol, heur) );
151
152 /* initialize data */
153 heurdata->nlpiterations = 0;
154 heurdata->nsuccess = 0;
155
156 return SCIP_OKAY;
157}
158
159
160/** deinitialization method of primal heuristic (called before transformed problem is freed) */
161static
162SCIP_DECL_HEUREXIT(heurExitRootsoldiving) /*lint --e{715}*/
163{ /*lint --e{715}*/
164 SCIP_HEURDATA* heurdata;
165
166 assert(heur != NULL);
167 assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0);
168
169 /* get heuristic data */
170 heurdata = SCIPheurGetData(heur);
171 assert(heurdata != NULL);
172
173 /* free working solution */
174 SCIP_CALL( SCIPfreeSol(scip, &heurdata->sol) );
175
176 return SCIP_OKAY;
177}
178
179
180/** execution method of primal heuristic */
181static
182SCIP_DECL_HEUREXEC(heurExecRootsoldiving) /*lint --e{715}*/
183{ /*lint --e{715}*/
184 SCIP_HEURDATA* heurdata;
185 SCIP_VAR** vars;
186 SCIP_Real* rootsol;
187 SCIP_Real* objchgvals;
188 int* softroundings;
189 int* intvalrounds;
190 int nvars;
191 int nbinvars;
192 int nintvars;
193 int nlpcands;
194 SCIP_LPSOLSTAT lpsolstat;
195 SCIP_Real absstartobjval;
196 SCIP_Real objstep;
197 SCIP_Real alpha;
198 SCIP_Real oldobj;
199 SCIP_Real newobj;
200 SCIP_Bool lperror;
201 SCIP_Bool lpsolchanged;
202 SCIP_Longint nsolsfound;
203 SCIP_Longint ncalls;
204 SCIP_Longint nlpiterations;
205 SCIP_Longint maxnlpiterations;
206 int depth;
207 int maxdepth;
208 int maxdivedepth;
209 int divedepth;
210 int startnlpcands;
211 int ncycles;
212 int i;
213
214 assert(heur != NULL);
215 assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0);
216 assert(scip != NULL);
217 assert(result != NULL);
218 assert(SCIPhasCurrentNodeLP(scip));
219
220 *result = SCIP_DELAYED;
221
222 /* do not call heuristic of node was already detected to be infeasible */
223 if( nodeinfeasible )
224 return SCIP_OKAY;
225
226 /* only call heuristic, if an optimal LP solution is at hand */
228 return SCIP_OKAY;
229
230 /* only call heuristic, if the LP objective value is smaller than the cutoff bound */
232 return SCIP_OKAY;
233
234 /* only call heuristic, if the LP solution is basic (which allows fast resolve in diving) */
235 if( !SCIPisLPSolBasic(scip) )
236 return SCIP_OKAY;
237
238 /* don't dive two times at the same node */
240 return SCIP_OKAY;
241
242 *result = SCIP_DIDNOTRUN;
243
244 /* get heuristic's data */
245 heurdata = SCIPheurGetData(heur);
246 assert(heurdata != NULL);
247
248 /* only apply heuristic, if only a few solutions have been found */
249 if( heurdata->maxsols >= 0 && SCIPgetNSolsFound(scip) >= heurdata->maxsols )
250 return SCIP_OKAY;
251
252 /* only try to dive, if we are in the correct part of the tree, given by minreldepth and maxreldepth */
253 depth = SCIPgetDepth(scip);
254 maxdepth = SCIPgetMaxDepth(scip);
255 maxdepth = MAX(maxdepth, 30);
256 if( depth < heurdata->minreldepth*maxdepth || depth > heurdata->maxreldepth*maxdepth )
257 return SCIP_OKAY;
258
259 /* calculate the maximal number of LP iterations until heuristic is aborted */
260 nlpiterations = SCIPgetNNodeLPIterations(scip);
261 ncalls = SCIPheurGetNCalls(heur);
262 nsolsfound = 10*SCIPheurGetNBestSolsFound(heur) + heurdata->nsuccess;
263 maxnlpiterations = (SCIP_Longint)((1.0 + 10.0*(nsolsfound+1.0)/(ncalls+1.0)) * heurdata->maxlpiterquot * nlpiterations);
264 maxnlpiterations += heurdata->maxlpiterofs;
265
266 /* don't try to dive, if we took too many LP iterations during diving */
267 if( heurdata->nlpiterations >= maxnlpiterations )
268 return SCIP_OKAY;
269
270 /* allow at least a certain number of LP iterations in this dive */
271 maxnlpiterations = MAX(maxnlpiterations, heurdata->nlpiterations + MINLPITER);
272
273 /* get number of fractional variables, that should be integral */
274 nlpcands = SCIPgetNLPBranchCands(scip);
275
276 /* don't try to dive, if there are no fractional variables */
277 if( nlpcands == 0 )
278 return SCIP_OKAY;
279
280 /* calculate the maximal diving depth */
282 if( SCIPgetNSolsFound(scip) == 0 )
283 maxdivedepth = (int)(heurdata->depthfacnosol * nvars);
284 else
285 maxdivedepth = (int)(heurdata->depthfac * nvars);
286 maxdivedepth = MAX(maxdivedepth, 10);
287
288 *result = SCIP_DIDNOTFIND;
289
290 /* get all variables of LP */
291 SCIP_CALL( SCIPgetVarsData(scip, &vars, &nvars, &nbinvars, &nintvars, NULL, NULL) );
292
293 /* get root solution value of all binary and integer variables */
294 SCIP_CALL( SCIPallocBufferArray(scip, &rootsol, nbinvars + nintvars) );
295 for( i = 0; i < nbinvars + nintvars; i++ )
296 rootsol[i] = SCIPvarGetRootSol(vars[i]);
297
298 /* get current LP objective value, and calculate length of a single step in an objective coefficient */
299 absstartobjval = SCIPgetLPObjval(scip);
300 absstartobjval = ABS(absstartobjval);
301 absstartobjval = MAX(absstartobjval, 1.0);
302 objstep = absstartobjval / 10.0;
303
304 /* initialize array storing the preferred soft rounding directions and counting the integral value rounds */
305 SCIP_CALL( SCIPallocBufferArray(scip, &softroundings, nbinvars + nintvars) );
306 BMSclearMemoryArray(softroundings, nbinvars + nintvars);
307 SCIP_CALL( SCIPallocBufferArray(scip, &intvalrounds, nbinvars + nintvars) );
308 BMSclearMemoryArray(intvalrounds, nbinvars + nintvars);
309
310 /* allocate temporary memory for buffering objective changes */
311 SCIP_CALL( SCIPallocBufferArray(scip, &objchgvals, nbinvars + nintvars) );
312
313 /* start diving */
315
316 SCIPdebugMsg(scip, "(node %" SCIP_LONGINT_FORMAT ") executing rootsoldiving heuristic: depth=%d, %d fractionals, dualbound=%g, maxnlpiterations=%" SCIP_LONGINT_FORMAT ", maxdivedepth=%d, LPobj=%g, objstep=%g\n",
317 SCIPgetNNodes(scip), SCIPgetDepth(scip), nlpcands, SCIPgetDualbound(scip), maxnlpiterations, maxdivedepth,
318 SCIPgetLPObjval(scip), objstep);
319
320 lperror = FALSE;
321 divedepth = 0;
322 lpsolstat = SCIP_LPSOLSTAT_OPTIMAL;
323 alpha = heurdata->alpha;
324 ncycles = 0;
325 lpsolchanged = TRUE;
326 startnlpcands = nlpcands;
327 while( !lperror && lpsolstat == SCIP_LPSOLSTAT_OPTIMAL && nlpcands > 0 && ncycles < 10
328 && (divedepth < 10
329 || nlpcands <= startnlpcands - divedepth/2
330 || (divedepth < maxdivedepth && heurdata->nlpiterations < maxnlpiterations))
331 && !SCIPisStopped(scip) )
332 {
333 SCIP_Bool success;
334 int hardroundingidx;
335 int hardroundingdir;
336 SCIP_Real hardroundingoldbd;
337 SCIP_Real hardroundingnewbd;
338 SCIP_Bool boundschanged;
339
340 SCIP_RETCODE retcode;
341
342 /* create solution from diving LP and try to round it */
343 SCIP_CALL( SCIPlinkLPSol(scip, heurdata->sol) );
344 SCIP_CALL( SCIProundSol(scip, heurdata->sol, &success) );
345
346 if( success )
347 {
348 SCIPdebugMsg(scip, "rootsoldiving found roundable primal solution: obj=%g\n", SCIPgetSolOrigObj(scip, heurdata->sol));
349
350 /* try to add solution to SCIP */
351 SCIP_CALL( SCIPtrySol(scip, heurdata->sol, FALSE, FALSE, FALSE, FALSE, FALSE, &success) );
352
353 /* check, if solution was feasible and good enough */
354 if( success )
355 {
356 SCIPdebugMsg(scip, " -> solution was feasible and good enough\n");
357 *result = SCIP_FOUNDSOL;
358 }
359 }
360
361 divedepth++;
362 hardroundingidx = -1;
363 hardroundingdir = 0;
364 hardroundingoldbd = 0.0;
365 hardroundingnewbd = 0.0;
366 boundschanged = FALSE;
367
368 SCIPdebugMsg(scip, "dive %d/%d, LP iter %" SCIP_LONGINT_FORMAT "/%" SCIP_LONGINT_FORMAT ":\n", divedepth, maxdivedepth, heurdata->nlpiterations, maxnlpiterations);
369
370 /* round solution x* from diving LP:
371 * - x~_j = down(x*_j) if x*_j is integer or binary variable and x*_j <= root solution_j
372 * - x~_j = up(x*_j) if x*_j is integer or binary variable and x*_j > root solution_j
373 * - x~_j = x*_j if x*_j is continuous variable
374 * change objective function in diving LP:
375 * - if x*_j is integral, or j is a continuous variable, set obj'_j = alpha * obj_j
376 * - otherwise, set obj'_j = alpha * obj_j + sign(x*_j - x~_j)
377 */
378 for( i = 0; i < nbinvars + nintvars; i++ )
379 {
380 SCIP_VAR* var;
381 SCIP_Real solval;
382
383 var = vars[i];
384 oldobj = SCIPgetVarObjDive(scip, var);
385 newobj = oldobj;
386
387 solval = SCIPvarGetLPSol(var);
388 if( SCIPisFeasIntegral(scip, solval) )
389 {
390 /* if the variable became integral after a soft rounding, count the rounds; after a while, fix it to its
391 * current integral value;
392 * otherwise, fade out the objective value
393 */
394 if( softroundings[i] != 0 && lpsolchanged )
395 {
396 intvalrounds[i]++;
397 if( intvalrounds[i] == 5 && SCIPgetVarLbDive(scip, var) < SCIPgetVarUbDive(scip, var) - 0.5 )
398 {
399 /* use exact integral value, if the variable is only integral within numerical tolerances */
400 solval = SCIPfloor(scip, solval+0.5);
401 SCIPdebugMsg(scip, " -> fixing <%s> = %g\n", SCIPvarGetName(var), solval);
402 SCIP_CALL( SCIPchgVarLbDive(scip, var, solval) );
403 SCIP_CALL( SCIPchgVarUbDive(scip, var, solval) );
404 boundschanged = TRUE;
405 }
406 }
407 else
408 newobj = alpha * oldobj;
409 }
410 else if( solval <= rootsol[i] )
411 {
412 /* if the variable was soft rounded most of the time downwards, round it downwards by changing the bounds;
413 * otherwise, apply soft rounding by changing the objective value
414 */
415 softroundings[i]--;
416 if( softroundings[i] <= -10 && hardroundingidx == -1 )
417 {
418 SCIPdebugMsg(scip, " -> hard rounding <%s>[%g] <= %g\n",
419 SCIPvarGetName(var), solval, SCIPfeasFloor(scip, solval));
420 hardroundingidx = i;
421 hardroundingdir = -1;
422 hardroundingoldbd = SCIPgetVarUbDive(scip, var);
423 hardroundingnewbd = SCIPfeasFloor(scip, solval);
424 SCIP_CALL( SCIPchgVarUbDive(scip, var, hardroundingnewbd) );
425 boundschanged = TRUE;
426 }
427 else
428 newobj = alpha * oldobj + objstep;
429 }
430 else
431 {
432 /* if the variable was soft rounded most of the time upwards, round it upwards by changing the bounds;
433 * otherwise, apply soft rounding by changing the objective value
434 */
435 softroundings[i]++;
436 if( softroundings[i] >= +10 && hardroundingidx == -1 )
437 {
438 SCIPdebugMsg(scip, " -> hard rounding <%s>[%g] >= %g\n",
439 SCIPvarGetName(var), solval, SCIPfeasCeil(scip, solval));
440 hardroundingidx = i;
441 hardroundingdir = +1;
442 hardroundingoldbd = SCIPgetVarLbDive(scip, var);
443 hardroundingnewbd = SCIPfeasCeil(scip, solval);
444 SCIP_CALL( SCIPchgVarLbDive(scip, var, hardroundingnewbd) );
445 boundschanged = TRUE;
446 }
447 else
448 newobj = alpha * oldobj - objstep;
449 }
450
451 /* remember the objective change */
452 objchgvals[i] = newobj;
453 }
454
455 /* apply objective changes if there was no bound change */
456 if( !boundschanged )
457 {
458 /* apply cached changes on integer variables */
459 for( i = 0; i < nbinvars + nintvars; ++i )
460 {
461 SCIP_VAR* var;
462
463 var = vars[i];
464 SCIPdebugMsg(scip, " -> i=%d var <%s>, solval=%g, rootsol=%g, oldobj=%g, newobj=%g\n",
465 i, SCIPvarGetName(var), SCIPvarGetLPSol(var), rootsol[i], SCIPgetVarObjDive(scip, var), objchgvals[i]);
466
467 SCIP_CALL( SCIPchgVarObjDive(scip, var, objchgvals[i]) );
468 }
469
470 /* fade out the objective values of the continuous variables */
471 for( i = nbinvars + nintvars; i < nvars; i++ )
472 {
473 SCIP_VAR* var;
474
475 var = vars[i];
476 oldobj = SCIPgetVarObjDive(scip, var);
477 newobj = alpha * oldobj;
478
479 SCIPdebugMsg(scip, " -> i=%d var <%s>, solval=%g, oldobj=%g, newobj=%g\n",
480 i, SCIPvarGetName(var), SCIPvarGetLPSol(var), oldobj, newobj);
481
482 SCIP_CALL( SCIPchgVarObjDive(scip, var, newobj) );
483 }
484 }
485
486 SOLVEAGAIN:
487 /* resolve the diving LP */
488 nlpiterations = SCIPgetNLPIterations(scip);
489
490 retcode = SCIPsolveDiveLP(scip, MAX((int)(maxnlpiterations - heurdata->nlpiterations), MINLPITER), &lperror, NULL);
491 lpsolstat = SCIPgetLPSolstat(scip);
492
493 /* Errors in the LP solver should not kill the overall solving process, if the LP is just needed for a heuristic.
494 * Hence in optimized mode, the return code is caught and a warning is printed, only in debug mode, SCIP will stop.
495 */
496 if( retcode != SCIP_OKAY )
497 {
498#ifndef NDEBUG
499 if( lpsolstat != SCIP_LPSOLSTAT_UNBOUNDEDRAY )
500 {
501 SCIP_CALL( retcode );
502 }
503#endif
504 SCIPwarningMessage(scip, "Error while solving LP in Rootsoldiving heuristic; LP solve terminated with code <%d>\n", retcode);
505 SCIPwarningMessage(scip, "This does not affect the remaining solution procedure --> continue\n");
506 }
507
508 if( lperror )
509 break;
510
511 /* update iteration count */
512 heurdata->nlpiterations += SCIPgetNLPIterations(scip) - nlpiterations;
513
514 /* if no LP iterations were performed, we stayed at the same solution -> count this cycling */
515 lpsolchanged = (SCIPgetNLPIterations(scip) != nlpiterations);
516 if( lpsolchanged )
517 ncycles = 0;
518 else if( !boundschanged ) /* do not count if integral variables have been fixed */
519 ncycles++;
520
521 /* get LP solution status and number of fractional variables, that should be integral */
522 if( lpsolstat == SCIP_LPSOLSTAT_INFEASIBLE && hardroundingidx != -1 )
523 {
524 SCIP_VAR* var;
525
526 var = vars[hardroundingidx];
527
528 /* round the hard rounded variable to the opposite direction and resolve the LP */
529 if( hardroundingdir == -1 )
530 {
531 SCIPdebugMsg(scip, " -> opposite hard rounding <%s> >= %g\n", SCIPvarGetName(var), hardroundingnewbd + 1.0);
532 SCIP_CALL( SCIPchgVarUbDive(scip, var, hardroundingoldbd) );
533 SCIP_CALL( SCIPchgVarLbDive(scip, var, hardroundingnewbd + 1.0) );
534 }
535 else
536 {
537 SCIPdebugMsg(scip, " -> opposite hard rounding <%s> <= %g\n", SCIPvarGetName(var), hardroundingnewbd - 1.0);
538 SCIP_CALL( SCIPchgVarLbDive(scip, var, hardroundingoldbd) );
539 SCIP_CALL( SCIPchgVarUbDive(scip, var, hardroundingnewbd - 1.0) );
540 }
541 hardroundingidx = -1;
542 goto SOLVEAGAIN;
543 }
544 if( lpsolstat == SCIP_LPSOLSTAT_OPTIMAL )
545 nlpcands = SCIPgetNLPBranchCands(scip);
546 SCIPdebugMsg(scip, " -> lpsolstat=%d, nfrac=%d\n", lpsolstat, nlpcands);
547 }
548
549 SCIPdebugMsg(scip, "---> diving finished: lpsolstat = %d, depth %d/%d, LP iter %" SCIP_LONGINT_FORMAT "/%" SCIP_LONGINT_FORMAT "\n",
550 lpsolstat, divedepth, maxdivedepth, heurdata->nlpiterations, maxnlpiterations);
551
552 /* check if a solution has been found */
553 if( nlpcands == 0 && !lperror && lpsolstat == SCIP_LPSOLSTAT_OPTIMAL )
554 {
555 SCIP_Bool success;
556
557 /* create solution from diving LP */
558 SCIP_CALL( SCIPlinkLPSol(scip, heurdata->sol) );
559 SCIPdebugMsg(scip, "rootsoldiving found primal solution: obj=%g\n", SCIPgetSolOrigObj(scip, heurdata->sol));
560
561 /* try to add solution to SCIP */
562 SCIP_CALL( SCIPtrySol(scip, heurdata->sol, FALSE, FALSE, FALSE, FALSE, FALSE, &success) );
563
564 /* check, if solution was feasible and good enough */
565 if( success )
566 {
567 SCIPdebugMsg(scip, " -> solution was feasible and good enough\n");
568 *result = SCIP_FOUNDSOL;
569 }
570 }
571
572 /* end diving */
574
575 if( *result == SCIP_FOUNDSOL )
576 heurdata->nsuccess++;
577
578 /* free temporary memory */
579 SCIPfreeBufferArray(scip, &objchgvals);
580 SCIPfreeBufferArray(scip, &intvalrounds);
581 SCIPfreeBufferArray(scip, &softroundings);
582 SCIPfreeBufferArray(scip, &rootsol);
583
584 SCIPdebugMsg(scip, "rootsoldiving heuristic finished\n");
585
586 return SCIP_OKAY;
587}
588
589
590/*
591 * heuristic specific interface methods
592 */
593
594/** creates the rootsoldiving heuristic and includes it in SCIP */
596 SCIP* scip /**< SCIP data structure */
597 )
598{
599 SCIP_HEURDATA* heurdata;
600 SCIP_HEUR* heur;
601
602 /* create Rootsoldiving primal heuristic data */
603 SCIP_CALL( SCIPallocBlockMemory(scip, &heurdata) );
604
605 /* include primal heuristic */
608 HEUR_MAXDEPTH, HEUR_TIMING, HEUR_USESSUBSCIP, heurExecRootsoldiving, heurdata) );
609
610 assert(heur != NULL);
611
612 /* set non-NULL pointers to callback methods */
613 SCIP_CALL( SCIPsetHeurCopy(scip, heur, heurCopyRootsoldiving) );
614 SCIP_CALL( SCIPsetHeurFree(scip, heur, heurFreeRootsoldiving) );
615 SCIP_CALL( SCIPsetHeurInit(scip, heur, heurInitRootsoldiving) );
616 SCIP_CALL( SCIPsetHeurExit(scip, heur, heurExitRootsoldiving) );
617
618 /* rootsoldiving heuristic parameters */
620 "heuristics/rootsoldiving/minreldepth",
621 "minimal relative depth to start diving",
622 &heurdata->minreldepth, TRUE, DEFAULT_MINRELDEPTH, 0.0, 1.0, NULL, NULL) );
624 "heuristics/rootsoldiving/maxreldepth",
625 "maximal relative depth to start diving",
626 &heurdata->maxreldepth, TRUE, DEFAULT_MAXRELDEPTH, 0.0, 1.0, NULL, NULL) );
628 "heuristics/rootsoldiving/maxlpiterquot",
629 "maximal fraction of diving LP iterations compared to node LP iterations",
630 &heurdata->maxlpiterquot, FALSE, DEFAULT_MAXLPITERQUOT, 0.0, SCIP_REAL_MAX, NULL, NULL) );
632 "heuristics/rootsoldiving/maxlpiterofs",
633 "additional number of allowed LP iterations",
634 &heurdata->maxlpiterofs, FALSE, DEFAULT_MAXLPITEROFS, 0, INT_MAX, NULL, NULL) );
636 "heuristics/rootsoldiving/maxsols",
637 "total number of feasible solutions found up to which heuristic is called (-1: no limit)",
638 &heurdata->maxsols, TRUE, DEFAULT_MAXSOLS, -1, INT_MAX, NULL, NULL) );
640 "heuristics/rootsoldiving/depthfac",
641 "maximal diving depth: number of binary/integer variables times depthfac",
642 &heurdata->depthfac, TRUE, DEFAULT_DEPTHFAC, 0.0, SCIP_REAL_MAX, NULL, NULL) );
644 "heuristics/rootsoldiving/depthfacnosol",
645 "maximal diving depth factor if no feasible solution was found yet",
646 &heurdata->depthfacnosol, TRUE, DEFAULT_DEPTHFACNOSOL, 0.0, SCIP_REAL_MAX, NULL, NULL) );
648 "heuristics/rootsoldiving/alpha",
649 "soft rounding factor to fade out objective coefficients",
650 &heurdata->alpha, TRUE, DEFAULT_ALPHA, 0.0, 1.0, NULL, NULL) );
651
652 return SCIP_OKAY;
653}
654
#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 SCIP_Real
Definition: def.h:173
#define ABS(x)
Definition: def.h:235
#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
SCIP_RETCODE SCIPgetVarsData(SCIP *scip, SCIP_VAR ***vars, int *nvars, int *nbinvars, int *nintvars, int *nimplvars, int *ncontvars)
Definition: scip_prob.c:1866
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 SCIPincludeHeurRootsoldiving(SCIP *scip)
int SCIPgetNLPBranchCands(SCIP *scip)
Definition: scip_branch.c:428
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 SCIPfloor(SCIP *scip, SCIP_Real val)
SCIP_Real SCIPfeasFloor(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisFeasIntegral(SCIP *scip, SCIP_Real val)
int SCIPgetDepth(SCIP *scip)
Definition: scip_tree.c:670
const char * SCIPvarGetName(SCIP_VAR *var)
Definition: var.c:17419
SCIP_Real SCIPvarGetRootSol(SCIP_VAR *var)
Definition: var.c:13350
SCIP_Real SCIPvarGetLPSol(SCIP_VAR *var)
Definition: var.c:18452
static SCIP_DECL_HEURCOPY(heurCopyRootsoldiving)
#define DEFAULT_DEPTHFAC
#define HEUR_TIMING
static SCIP_DECL_HEURFREE(heurFreeRootsoldiving)
#define DEFAULT_MAXLPITERQUOT
#define HEUR_FREQOFS
#define HEUR_DESC
#define MINLPITER
static SCIP_DECL_HEUREXIT(heurExitRootsoldiving)
#define HEUR_DISPCHAR
#define HEUR_MAXDEPTH
#define HEUR_PRIORITY
#define DEFAULT_MAXRELDEPTH
#define DEFAULT_MAXLPITEROFS
#define HEUR_NAME
#define DEFAULT_DEPTHFACNOSOL
static SCIP_DECL_HEUREXEC(heurExecRootsoldiving)
#define DEFAULT_ALPHA
#define HEUR_FREQ
#define DEFAULT_MINRELDEPTH
#define DEFAULT_MAXSOLS
#define HEUR_USESSUBSCIP
static SCIP_DECL_HEURINIT(heurInitRootsoldiving)
LP diving heuristic that changes variables' objective values using root LP solution as guide.
memory allocation routines
#define BMSclearMemoryArray(ptr, num)
Definition: memory.h:130
public methods for primal heuristics
public methods for message output
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 solutions
public methods for querying solving statistics
public methods for the branch-and-bound tree
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_LPSOLSTAT_INFEASIBLE
Definition: type_lp.h:44
@ 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