SCIP Doxygen Documentation
 
Loading...
Searching...
No Matches
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);
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}*/
193
194 assert(heur != NULL);
195 assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0);
197
198 /* free heuristic data */
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}*/
213
214 assert(heur != NULL);
215 assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0);
216
217 /* get heuristic data */
219 assert(heurdata != NULL);
220
221 /* create working solution */
223
224 /* create random number generator */
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}*/
240
241 assert(heur != NULL);
242 assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0);
243
244 /* get heuristic data */
246 assert(heurdata != NULL);
247
248 /* free random number generator */
250
251 /* free working solution */
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}*/
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;
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;
287 int nvars;
291 int depth;
296 int c;
297
298 assert(heur != NULL);
299 assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0);
300 assert(scip != NULL);
303
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
327
328 /* get heuristic's data */
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 */
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 */
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 */
356
357 /* get fractional variables that should be integral */
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);
371
373
374 /* get temporary memory for remembering the current soft roundings */
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",
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;
391 divedepth = 0;
394 && (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;
414 for( c = 0; c < nlpcands; ++c )
415 {
416 var = lpcands[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 */
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 )
434 else if( mayrounddown )
436 else
438
439 /* prefer variables, that have already been soft rounded but failed to get integral */
441 assert(0 <= varidx && varidx < nvars);
442 if( roundings[varidx] != 0 )
443 pscostquot *= 1000.0;
444
445 /* check, if candidate is new best candidate */
447 {
448 bestcand = c;
453 }
454 }
455 }
456 else
457 {
458 /* the candidate may not be rounded: calculate pseudo cost quotient and preferred direction */
460
461 /* prefer variables, that have already been soft rounded but failed to get integral */
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 */
469 {
470 bestcand = c;
475 }
476 }
477 }
478 assert(bestcand != -1);
479
480 /* if all candidates are roundable, try to round the solution */
482 {
483 SCIP_Bool success;
484
485 /* create solution from diving LP and try to round it */
487 SCIP_CALL( SCIProundSol(scip, heurdata->sol, &success) );
488
489 if( success )
490 {
491 SCIPdebugMsg(scip, "objpscostdiving found roundable primal solution: obj=%g\n",
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");
502 }
503 }
504 }
505
507
508 /* check, if the best candidate was already subject to soft rounding */
510 assert(0 <= varidx && varidx < nvars);
511 if( roundings[varidx] == +1 )
512 {
513 /* variable was already soft rounded upwards: hard round it downwards */
515 SCIPdebugMsg(scip, " dive %d/%d: var <%s>, round=%u/%u, sol=%g, was already soft rounded upwards -> bounds=[%g,%g]\n",
518 }
519 else if( roundings[varidx] == -1 )
520 {
521 /* variable was already soft rounded downwards: hard round it upwards */
523 SCIPdebugMsg(scip, " dive %d/%d: var <%s>, round=%u/%u, sol=%g, was already soft rounded downwards -> bounds=[%g,%g]\n",
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;
534 if( bestcandroundup )
535 {
536 /* soft round variable up: make objective value (more) negative */
537 if( oldobj < 0.0 )
539 else
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 )
551 else
554
555 /* remember, that this variable was soft rounded downwards */
556 roundings[varidx] = -1;
557 }
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",
563 }
564
565 /* resolve the diving LP */
567 retcode = SCIPsolveDiveLP(scip, MAX((int)(maxnlpiterations - heurdata->nlpiterations), MINLPITER), &lperror, NULL);
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
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 */
593 {
594 /* get new fractional variables */
596 }
597 SCIPdebugMsg(scip, " -> lpsolstat=%d, nfrac=%d\n", lpsolstat, nlpcands);
598 }
599
600 /* check if a solution has been found */
602 {
603 SCIP_Bool success;
604
605 /* create solution from diving LP */
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");
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 */
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{
645 SCIP_HEUR* heur;
646
647 /* create Objpscostdiving primal heuristic data */
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:266
#define SCIP_Longint
Definition def.h:157
#define SCIP_REAL_MAX
Definition def.h:173
#define MIN(x, y)
Definition def.h:242
#define TRUE
Definition def.h:93
#define FALSE
Definition def.h:94
#define MAX(x, y)
Definition def.h:238
#define SCIP_LONGINT_FORMAT
Definition def.h:164
#define SCIP_CALL(x)
Definition def.h:373
SCIP_Bool SCIPisStopped(SCIP *scip)
int SCIPgetNIntVars(SCIP *scip)
Definition scip_prob.c:2082
int SCIPgetNBinVars(SCIP *scip)
Definition scip_prob.c:2037
#define SCIPdebugMsg
void SCIPwarningMessage(SCIP *scip, const char *formatstr,...)
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)
SCIP_RETCODE SCIPsetHeurFree(SCIP *scip, SCIP_HEUR *heur,)
Definition scip_heur.c:178
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_Longint SCIPheurGetNBestSolsFound(SCIP_HEUR *heur)
Definition heur.c:1599
SCIP_RETCODE SCIPsetHeurCopy(SCIP *scip, SCIP_HEUR *heur,)
Definition scip_heur.c:162
SCIP_Longint SCIPheurGetNCalls(SCIP_HEUR *heur)
Definition heur.c:1579
SCIP_RETCODE SCIPsetHeurExit(SCIP *scip, SCIP_HEUR *heur,)
Definition scip_heur.c:210
SCIP_RETCODE SCIPsetHeurInit(SCIP *scip, SCIP_HEUR *heur,)
Definition scip_heur.c:194
const char * SCIPheurGetName(SCIP_HEUR *heur)
Definition heur.c:1453
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_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 SCIProundSol(SCIP *scip, SCIP_SOL *sol, SCIP_Bool *success)
Definition scip_sol.c:2307
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:2950
SCIP_Real SCIPgetSolOrigObj(SCIP *scip, SCIP_SOL *sol)
Definition scip_sol.c:1296
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:672
SCIP_Bool SCIPvarMayRoundUp(SCIP_VAR *var)
Definition var.c:3451
SCIP_Bool SCIPvarIsBinary(SCIP_VAR *var)
Definition var.c:17598
SCIP_Bool SCIPvarMayRoundDown(SCIP_VAR *var)
Definition var.c:3440
int SCIPvarGetProbindex(SCIP_VAR *var)
Definition var.c:17767
const char * SCIPvarGetName(SCIP_VAR *var)
Definition var.c:17418
SCIP_Real SCIPvarGetRootSol(SCIP_VAR *var)
Definition var.c:13349
SCIP_Real SCIPgetVarPseudocostVal(SCIP *scip, SCIP_VAR *var, SCIP_Real solvaldelta)
Definition scip_var.c:8937
int SCIPrandomGetInt(SCIP_RANDNUMGEN *randnumgen, int minrandval, int maxrandval)
Definition misc.c:10111
heurdata nsuccess
heurdata nlpiterations
static SCIP_SOL * sol
assert(minobj< SCIPgetCutoffbound(scip))
SCIPlinkLPSol(scip, sol))
SCIPcreateRandom(scip, &heurdata->randnumgen, DEFAULT_RANDSEED, TRUE))
int maxdivedepth
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)
SCIP_Bool lperror
SCIP_Bool mayrounddown
int * roundings
SCIP_Longint nsolsfound
SCIP_VAR * var
SCIPheurSetData(heur, NULL)
int bestcand
SCIP_Longint ncalls
#define DEFAULT_DEPTHFAC
#define HEUR_TIMING
SCIP_Bool bestcandroundup
return SCIP_OKAY
SCIP_Bool bestcandmayroundup
SCIP_Real primsol
#define DEFAULT_MAXLPITERQUOT
#define HEUR_FREQOFS
SCIPendDive(scip))
#define HEUR_DESC
SCIP_Real objscale
#define MINLPITER
SCIP_Bool bestcandmayrounddown
#define HEUR_DISPCHAR
#define HEUR_MAXDEPTH
#define HEUR_PRIORITY
#define DEFAULT_MAXRELDEPTH
#define DEFAULT_MAXLPITEROFS
SCIP_Real * lpcandssol
heurdata nlpiterations
SCIPfreeSol(scip, &heurdata->sol))
SCIP_Real frac
SCIP_Real * lpcandsfrac
#define HEUR_NAME
SCIP_VAR ** lpcands
int divedepth
int startnlpcands
SCIP_Longint maxnlpiterations
SCIP_Bool mayroundup
#define DEFAULT_DEPTHFACNOSOL
int nlpcands
int maxdepth
SCIP_Real newobj
SCIPfreeRandom(scip, &heurdata->randnumgen)
#define DEFAULT_RANDSEED
static SCIP_LPSOLSTAT lpsolstat
SCIP_Real bestpscostquot
#define HEUR_FREQ
SCIP_Real pscostquot
#define DEFAULT_MINRELDEPTH
#define DEFAULT_MAXSOLS
#define HEUR_USESSUBSCIP
SCIP_Real oldobj
SCIPcreateSol(scip, &heurdata->sol, heur))
SCIP_Bool roundup
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
#define SCIP_DECL_HEURCOPY(x)
Definition type_heur.h:97
struct SCIP_HeurData SCIP_HEURDATA
Definition type_heur.h:77
#define SCIP_DECL_HEURINIT(x)
Definition type_heur.h:113
#define SCIP_DECL_HEUREXIT(x)
Definition type_heur.h:121
#define SCIP_DECL_HEURFREE(x)
Definition type_heur.h:105
#define SCIP_DECL_HEUREXEC(x)
Definition type_heur.h:163
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
enum SCIP_Retcode SCIP_RETCODE