Scippy

SCIP

Solving Constraint Integer Programs

heur_randrounding.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_randrounding.c
26 * @ingroup DEFPLUGINS_HEUR
27 * @brief randomized LP rounding heuristic which also generates conflicts via an auxiliary probing tree
28 * @author Gregor Hendel
29 *
30 * Randomized LP rounding uses a random variable from a uniform distribution
31 * over [0,1] to determine whether the fractional LP value x should be rounded
32 * up with probability x - floor(x) or down with probability ceil(x) - x.
33 *
34 * This implementation uses domain propagation techniques to tighten the variable domains after every
35 * rounding step.
36 */
37
38/*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
39
42#include "scip/pub_heur.h"
43#include "scip/pub_message.h"
44#include "scip/pub_misc.h"
45#include "scip/pub_var.h"
46#include "scip/scip_branch.h"
47#include "scip/scip_general.h"
48#include "scip/scip_heur.h"
49#include "scip/scip_lp.h"
50#include "scip/scip_mem.h"
51#include "scip/scip_message.h"
52#include "scip/scip_numerics.h"
53#include "scip/scip_param.h"
54#include "scip/scip_probing.h"
56#include "scip/scip_sol.h"
58#include "scip/scip_tree.h"
59#include "scip/scip_var.h"
60#include <string.h>
61
62#define HEUR_NAME "randrounding"
63#define HEUR_DESC "fast LP rounding heuristic"
64#define HEUR_DISPCHAR SCIP_HEURDISPCHAR_ROUNDING
65#define HEUR_PRIORITY -200
66#define HEUR_FREQ 20
67#define HEUR_FREQOFS 0
68#define HEUR_MAXDEPTH -1
69#define HEUR_TIMING SCIP_HEURTIMING_DURINGLPLOOP
70#define HEUR_USESSUBSCIP FALSE /**< does the heuristic use a secondary SCIP instance? */
71
72#define DEFAULT_ONCEPERNODE FALSE /**< should the heuristic only be called once per node? */
73#define DEFAULT_RANDSEED 23 /**< default random seed */
74#define DEFAULT_USESIMPLEROUNDING FALSE /**< should the heuristic apply the variable lock strategy of simple rounding,
75 * if possible? */
76#define DEFAULT_MAXPROPROUNDS 1 /**< limit of rounds for each propagation call */
77#define DEFAULT_PROPAGATEONLYROOT TRUE /**< should the probing part of the heuristic be applied exclusively at the root node */
78
79/* locally defined heuristic data */
80struct SCIP_HeurData
81{
82 SCIP_SOL* sol; /**< working solution */
83 SCIP_RANDNUMGEN* randnumgen; /**< random number generation */
84 SCIP_Longint lastlp; /**< last LP number where the heuristic was applied */
85 int maxproprounds; /**< limit of rounds for each propagation call */
86 SCIP_Bool oncepernode; /**< should the heuristic only be called once per node? */
87 SCIP_Bool usesimplerounding; /**< should the heuristic apply the variable lock strategy of simple rounding,
88 * if possible? */
89 SCIP_Bool propagateonlyroot; /**< should the probing part of the heuristic be applied exclusively at the root node? */
90};
91
92/*
93 * Local methods
94 */
95
96/** perform randomized rounding of the given solution. Domain propagation is optionally applied after every rounding
97 * step
98 */
99static
101 SCIP* scip, /**< SCIP main data structure */
102 SCIP_HEURDATA* heurdata, /**< heuristic data */
103 SCIP_SOL* sol, /**< solution to round */
104 SCIP_VAR** cands, /**< candidate variables */
105 int ncands, /**< number of candidates */
106 SCIP_Bool propagate, /**< should the rounding be propagated? */
107 SCIP_RESULT* result /**< pointer to store the result of the heuristic call */
108 )
109{
110 int c;
111 SCIP_Bool stored;
112 SCIP_VAR** permutedcands;
113 SCIP_Bool cutoff;
114
115 assert(heurdata != NULL);
116
117 /* start probing tree before rounding begins */
118 if( propagate )
119 {
122 }
123
124 /* copy and permute the candidate array */
125 SCIP_CALL( SCIPduplicateBufferArray(scip, &permutedcands, cands, ncands) );
126
127 assert(permutedcands != NULL);
128
129 SCIPrandomPermuteArray(heurdata->randnumgen, (void **)permutedcands, 0, ncands);
130 cutoff = FALSE;
131
132 /* loop over candidates and perform randomized rounding and optionally probing. */
133 for (c = 0; c < ncands && !cutoff; ++c)
134 {
135 SCIP_VAR* var;
136 SCIP_Real oldsolval;
137 SCIP_Real newsolval;
138 SCIP_Bool mayrounddown;
139 SCIP_Bool mayroundup;
140 SCIP_Longint ndomreds;
141 SCIP_Real lb;
142 SCIP_Real ub;
143 SCIP_Real ceilval;
144 SCIP_Real floorval;
145
146 /* get next variable from permuted candidate array */
147 var = permutedcands[c];
148 oldsolval = SCIPgetSolVal(scip, sol, var);
149 lb = SCIPvarGetLbLocal(var);
150 ub = SCIPvarGetUbLocal(var);
151
152 assert( ! SCIPisFeasIntegral(scip, oldsolval) );
153 assert( SCIPvarGetStatus(var) == SCIP_VARSTATUS_COLUMN );
154
155 mayrounddown = SCIPvarMayRoundDown(var);
156 mayroundup = SCIPvarMayRoundUp(var);
157 ceilval = SCIPfeasCeil(scip, oldsolval);
158 floorval = SCIPfeasFloor(scip, oldsolval);
159
160 SCIPdebugMsg(scip, "rand rounding heuristic: var <%s>, val=%g, rounddown=%u, roundup=%u\n",
161 SCIPvarGetName(var), oldsolval, mayrounddown, mayroundup);
162
163 /* abort if rounded ceil and floor value lie outside the variable domain. Otherwise, check if
164 * bounds allow only one rounding direction, anyway */
165 if( lb > ceilval + 0.5 || ub < floorval - 0.5 )
166 {
167 cutoff = TRUE;
168 break;
169 }
170 else if( SCIPisFeasEQ(scip, lb, ceilval) )
171 {
172 /* only rounding up possible */
173 assert(SCIPisFeasGE(scip, ub, ceilval));
174 newsolval = ceilval;
175 }
176 else if( SCIPisFeasEQ(scip, ub, floorval) )
177 {
178 /* only rounding down possible */
179 assert(SCIPisFeasLE(scip,lb, floorval));
180 newsolval = floorval;
181 }
182 else if( !heurdata->usesimplerounding || !(mayroundup || mayrounddown) )
183 {
184 /* the standard randomized rounding */
185 SCIP_Real randnumber;
186
187 randnumber = SCIPrandomGetReal(heurdata->randnumgen, 0.0, 1.0);
188 if( randnumber <= oldsolval - floorval )
189 newsolval = ceilval;
190 else
191 newsolval = floorval;
192 }
193 /* choose rounding direction, if possible, or use the only direction guaranteed to be feasible */
194 else if( mayrounddown && mayroundup )
195 {
196 /* we can round in both directions: round in objective function direction */
197 if ( SCIPvarGetObj(var) >= 0.0 )
198 newsolval = floorval;
199 else
200 newsolval = ceilval;
201 }
202 else if( mayrounddown )
203 newsolval = floorval;
204 else
205 {
206 assert(mayroundup);
207 newsolval = ceilval;
208 }
209
210 assert(SCIPisFeasLE(scip, lb, newsolval));
211 assert(SCIPisFeasGE(scip, ub, newsolval));
212
213 /* if propagation is enabled, fix the candidate variable to its rounded value and propagate the solution */
214 if( propagate )
215 {
216 SCIP_Bool lbadjust;
217 SCIP_Bool ubadjust;
218
219 lbadjust = SCIPisGT(scip, newsolval, lb);
220 ubadjust = SCIPisLT(scip, newsolval, ub);
221
222 assert( lbadjust || ubadjust || SCIPisFeasEQ(scip, lb, ub));
223
224 /* enter a new probing node if the variable was not already fixed before */
225 if( lbadjust || ubadjust )
226 {
227 if( SCIPisStopped(scip) )
228 break;
229
230 /* We only want to create a new probing node if we do not exceeed the maximal tree depth,
231 * otherwise we finish at this point.
232 * @todo: Maybe we want to continue with the same node because we do not backtrack.
233 */
235 {
237 }
238 else
239 break;
240
241 /* tighten the bounds to fix the variable for the probing node */
242 if( lbadjust )
243 {
244 SCIP_CALL( SCIPchgVarLbProbing(scip, var, newsolval) );
245 }
246 if( ubadjust )
247 {
248 SCIP_CALL( SCIPchgVarUbProbing(scip, var, newsolval) );
249 }
250
251 /* call propagation routines for the reduced problem */
252 SCIP_CALL( SCIPpropagateProbing(scip, heurdata->maxproprounds, &cutoff, &ndomreds) );
253 }
254 }
255 /* store new solution value */
256 SCIP_CALL( SCIPsetSolVal(scip, sol, var, newsolval) );
257 }
258
259 /* if no cutoff was detected, the solution is a candidate to be checked for feasibility */
260 if( !cutoff && ! SCIPisStopped(scip) )
261 {
262 if( SCIPallColsInLP(scip) )
263 {
264 /* check solution for feasibility, and add it to solution store if possible
265 * neither integrality nor feasibility of LP rows has to be checked, because all fractional
266 * variables were already moved in feasible direction to the next integer
267 */
268 SCIP_CALL( SCIPtrySol(scip, sol, FALSE, FALSE, FALSE, FALSE, TRUE, &stored) );
269 }
270 else
271 {
272 /* if there are variables which are not present in the LP, e.g., for
273 * column generation, we need to check their bounds
274 */
275 SCIP_CALL( SCIPtrySol(scip, sol, FALSE, FALSE, TRUE, FALSE, TRUE, &stored) );
276 }
277
278 if( stored )
279 {
280#ifdef SCIP_DEBUG
281 SCIPdebugMsg(scip, "found feasible rounded solution:\n");
283#endif
284 *result = SCIP_FOUNDSOL;
285 }
286 }
287
288 assert( !propagate || SCIPinProbing(scip) );
289
290 /* exit probing mode and free locally allocated memory */
291 if( propagate )
292 {
294 }
295
296 SCIPfreeBufferArray(scip, &permutedcands);
297
298 return SCIP_OKAY;
299}
300
301/** perform randomized LP-rounding */
302static
304 SCIP* scip, /**< SCIP main data structure */
305 SCIP_HEURDATA* heurdata, /**< heuristic data */
306 SCIP_HEURTIMING heurtiming, /**< heuristic timing mask */
307 SCIP_Bool propagate, /**< should the heuristic apply SCIP's propagation? */
308 SCIP_RESULT* result /**< pointer to store the result of the heuristic call */
309 )
310{
311 SCIP_SOL* sol;
312 SCIP_VAR** lpcands;
313 SCIP_Longint nlps;
314 int nlpcands;
315
316 /* only call heuristic, if an optimal LP solution is at hand */
318
319 /* only call heuristic, if the LP objective value is smaller than the cutoff bound */
321 return SCIP_OKAY;
322
323 /* get fractional variables, that should be integral */
324 SCIP_CALL( SCIPgetLPBranchCands(scip, &lpcands, NULL, NULL, &nlpcands, NULL, NULL) );
325
326 /* only call heuristic, if LP solution is fractional; except we are called during pricing, in this case we
327 * want to detect a (mixed) integer (LP) solution which is primal feasible */
328 if ( nlpcands == 0 && heurtiming != SCIP_HEURTIMING_DURINGPRICINGLOOP )
329 return SCIP_OKAY;
330
331 /* get the working solution from heuristic's local data */
332 sol = heurdata->sol;
333 assert( sol != NULL );
334
335 /* copy the current LP solution to the working solution */
337
338 /* don't call heuristic, if we have already processed the current LP solution */
339 nlps = SCIPgetNLPs(scip);
340 if( nlps == heurdata->lastlp )
341 return SCIP_OKAY;
342 heurdata->lastlp = nlps;
343
344 *result = SCIP_DIDNOTFIND;
345
346 /* perform random rounding */
347 SCIPdebugMsg(scip, "executing rand LP-rounding heuristic: %d fractionals\n", nlpcands);
348 SCIP_CALL( performRandRounding(scip, heurdata, sol, lpcands, nlpcands, propagate, result) );
349
350 return SCIP_OKAY;
351}
352
353/*
354 * Callback methods
355 */
356
357/** copy method for primal heuristic plugins (called when SCIP copies plugins) */
358static
359SCIP_DECL_HEURCOPY(heurCopyRandrounding)
360{ /*lint --e{715}*/
361 assert(scip != NULL);
362 assert(heur != NULL);
363 assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0);
364
365 /* call inclusion method of primal heuristic */
367
368 return SCIP_OKAY;
369}
370
371/** destructor of primal heuristic to free user data (called when SCIP is exiting) */
372static
373SCIP_DECL_HEURFREE(heurFreeRandrounding) /*lint --e{715}*/
374{ /*lint --e{715}*/
375 SCIP_HEURDATA* heurdata;
376
377 assert(heur != NULL);
378 assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0);
379 assert(scip != NULL);
380
381 /* free heuristic data */
382 heurdata = SCIPheurGetData(heur);
383 assert(heurdata != NULL);
384 SCIPfreeBlockMemory(scip, &heurdata);
385 SCIPheurSetData(heur, NULL);
386
387 return SCIP_OKAY;
388}
389
390/** initialization method of primal heuristic (called after problem was transformed) */
391static
392SCIP_DECL_HEURINIT(heurInitRandrounding) /*lint --e{715}*/
393{ /*lint --e{715}*/
394 SCIP_HEURDATA* heurdata;
395
396 assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0);
397 heurdata = SCIPheurGetData(heur);
398 assert(heurdata != NULL);
399
400 /* create heuristic data */
401 SCIP_CALL( SCIPcreateSol(scip, &heurdata->sol, heur) );
402 heurdata->lastlp = -1;
403
404 /* create random number generator */
405 SCIP_CALL( SCIPcreateRandom(scip, &heurdata->randnumgen,
407
408 return SCIP_OKAY;
409}
410
411/** deinitialization method of primal heuristic (called before transformed problem is freed) */
412static
413SCIP_DECL_HEUREXIT(heurExitRandrounding) /*lint --e{715}*/
414{ /*lint --e{715}*/
415 SCIP_HEURDATA* heurdata;
416
417 assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0);
418
419 /* free heuristic data */
420 heurdata = SCIPheurGetData(heur);
421 assert(heurdata != NULL);
422 SCIP_CALL( SCIPfreeSol(scip, &heurdata->sol) );
423
424 /* free random number generator */
425 SCIPfreeRandom(scip, &heurdata->randnumgen);
426
427 return SCIP_OKAY;
428}
429
430/** solving process initialization method of primal heuristic (called when branch and bound process is about to begin) */
431static
432SCIP_DECL_HEURINITSOL(heurInitsolRandrounding)
433{
434 SCIP_HEURDATA* heurdata;
435
436 assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0);
437
438 heurdata = SCIPheurGetData(heur);
439 assert(heurdata != NULL);
440 heurdata->lastlp = -1;
441
442 /* change the heuristic's timingmask, if it should be called only once per node */
443 if( heurdata->oncepernode )
445
446 return SCIP_OKAY;
447}
448
449
450/** solving process deinitialization method of primal heuristic (called before branch and bound process data is freed) */
451static
452SCIP_DECL_HEUREXITSOL(heurExitsolRandrounding)
453{
454 /* reset the timing mask to its default value */
456
457 return SCIP_OKAY;
458}
459
460/** execution method of primal heuristic */
461static
462SCIP_DECL_HEUREXEC(heurExecRandrounding) /*lint --e{715}*/
463{ /*lint --e{715}*/
464 SCIP_HEURDATA* heurdata;
465 SCIP_Bool propagate;
466
467 assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0);
468 assert(result != NULL);
469 assert(SCIPhasCurrentNodeLP(scip));
470
471 *result = SCIP_DIDNOTRUN;
472
473 /* only call heuristic, if an optimal LP solution is at hand */
475 return SCIP_OKAY;
476
477 /* only call heuristic, if the LP objective value is smaller than the cutoff bound */
479 return SCIP_OKAY;
480
481 /* get heuristic data */
482 heurdata = SCIPheurGetData(heur);
483 assert(heurdata != NULL);
484
485 /* don't call heuristic, if we have already processed the current LP solution */
486 if( SCIPgetNLPs(scip) == heurdata->lastlp )
487 return SCIP_OKAY;
488
489 propagate = (!heurdata->propagateonlyroot || SCIPgetDepth(scip) == 0);
490
491 /* try to round LP solution */
492 SCIP_CALL( performLPRandRounding(scip, heurdata, heurtiming, propagate, result) );
493
494 return SCIP_OKAY;
495}
496
497/*
498 * heuristic specific interface methods
499 */
500
501/** creates the rand rounding heuristic and includes it in SCIP */
503 SCIP* scip /**< SCIP data structure */
504 )
505{
506 SCIP_HEURDATA* heurdata;
507 SCIP_HEUR* heur;
508
509 /* create heuristic data */
510 SCIP_CALL( SCIPallocBlockMemory(scip, &heurdata) );
511
512 /* include primal heuristic */
515 HEUR_MAXDEPTH, HEUR_TIMING, HEUR_USESSUBSCIP, heurExecRandrounding, heurdata) );
516 assert(heur != NULL);
517
518 /* set non-NULL pointers to callback methods */
519 SCIP_CALL( SCIPsetHeurCopy(scip, heur, heurCopyRandrounding) );
520 SCIP_CALL( SCIPsetHeurInit(scip, heur, heurInitRandrounding) );
521 SCIP_CALL( SCIPsetHeurExit(scip, heur, heurExitRandrounding) );
522 SCIP_CALL( SCIPsetHeurInitsol(scip, heur, heurInitsolRandrounding) );
523 SCIP_CALL( SCIPsetHeurExitsol(scip, heur, heurExitsolRandrounding) );
524 SCIP_CALL( SCIPsetHeurFree(scip, heur, heurFreeRandrounding) );
525
526 SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/oncepernode",
527 "should the heuristic only be called once per node?",
528 &heurdata->oncepernode, TRUE, DEFAULT_ONCEPERNODE, NULL, NULL) );
529 SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/usesimplerounding", "should the heuristic apply the variable lock strategy of simple rounding, if possible?",
530 &heurdata->usesimplerounding, TRUE, DEFAULT_USESIMPLEROUNDING, NULL, NULL) );
531 SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/propagateonlyroot",
532 "should the probing part of the heuristic be applied exclusively at the root node?",
533 &heurdata->propagateonlyroot, TRUE, DEFAULT_PROPAGATEONLYROOT, NULL, NULL) );
534 SCIP_CALL( SCIPaddIntParam(scip, "heuristics/" HEUR_NAME "/maxproprounds",
535 "limit of rounds for each propagation call",
536 &heurdata->maxproprounds, TRUE, DEFAULT_MAXPROPROUNDS,
537 -1, INT_MAX, NULL, NULL) );
538 return SCIP_OKAY;
539}
#define NULL
Definition: def.h:267
#define SCIP_Longint
Definition: def.h:158
#define SCIP_MAXTREEDEPTH
Definition: def.h:316
#define SCIP_Bool
Definition: def.h:91
#define SCIP_Real
Definition: def.h:173
#define TRUE
Definition: def.h:93
#define FALSE
Definition: def.h:94
#define SCIP_CALL(x)
Definition: def.h:374
SCIP_Bool SCIPisStopped(SCIP *scip)
Definition: scip_general.c:724
#define SCIPdebugMsg
Definition: scip_message.h:78
SCIP_RETCODE SCIPaddIntParam(SCIP *scip, const char *name, const char *desc, int *valueptr, SCIP_Bool isadvanced, int defaultvalue, int minvalue, int maxvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition: scip_param.c:83
SCIP_RETCODE SCIPaddBoolParam(SCIP *scip, const char *name, const char *desc, SCIP_Bool *valueptr, SCIP_Bool isadvanced, SCIP_Bool defaultvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition: scip_param.c:57
void SCIPrandomPermuteArray(SCIP_RANDNUMGEN *randnumgen, void **array, int begin, int end)
Definition: misc.c:10179
SCIP_RETCODE SCIPincludeHeurRandrounding(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 SCIPsetHeurExitsol(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEUREXITSOL((*heurexitsol)))
Definition: scip_heur.c:242
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
void SCIPheurSetTimingmask(SCIP_HEUR *heur, SCIP_HEURTIMING timingmask)
Definition: heur.c:1493
SCIP_RETCODE SCIPsetHeurInitsol(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURINITSOL((*heurinitsol)))
Definition: scip_heur.c:226
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_Bool SCIPhasCurrentNodeLP(SCIP *scip)
Definition: scip_lp.c:83
SCIP_LPSOLSTAT SCIPgetLPSolstat(SCIP *scip)
Definition: scip_lp.c:168
SCIP_Bool SCIPallColsInLP(SCIP *scip)
Definition: scip_lp.c:649
SCIP_Real SCIPgetLPObjval(SCIP *scip)
Definition: scip_lp.c:247
#define SCIPfreeBufferArray(scip, ptr)
Definition: scip_mem.h:136
#define SCIPduplicateBufferArray(scip, ptr, source, num)
Definition: scip_mem.h:132
#define SCIPfreeBlockMemory(scip, ptr)
Definition: scip_mem.h:108
#define SCIPallocBlockMemory(scip, ptr)
Definition: scip_mem.h:89
SCIP_RETCODE SCIPchgVarUbProbing(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound)
Definition: scip_probing.c:345
SCIP_RETCODE SCIPchgVarLbProbing(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound)
Definition: scip_probing.c:301
SCIP_RETCODE SCIPpropagateProbing(SCIP *scip, int maxproprounds, SCIP_Bool *cutoff, SCIP_Longint *ndomredsfound)
Definition: scip_probing.c:580
SCIP_Bool SCIPinProbing(SCIP *scip)
Definition: scip_probing.c:97
SCIP_RETCODE SCIPstartProbing(SCIP *scip)
Definition: scip_probing.c:119
SCIP_RETCODE SCIPnewProbingNode(SCIP *scip)
Definition: scip_probing.c:165
SCIP_RETCODE SCIPendProbing(SCIP *scip)
Definition: scip_probing.c:260
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 SCIPprintSol(SCIP *scip, SCIP_SOL *sol, FILE *file, SCIP_Bool printzeros)
Definition: scip_sol.c:1631
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_RETCODE SCIPsetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var, SCIP_Real val)
Definition: scip_sol.c:1077
SCIP_Real SCIPgetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var)
Definition: scip_sol.c:1217
SCIP_Longint SCIPgetNLPs(SCIP *scip)
SCIP_Real SCIPgetCutoffbound(SCIP *scip)
SCIP_Bool SCIPisFeasGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisFeasEQ(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 SCIPisFeasLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisFeasIntegral(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisGT(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_VARSTATUS SCIPvarGetStatus(SCIP_VAR *var)
Definition: var.c:17538
SCIP_Real SCIPvarGetUbLocal(SCIP_VAR *var)
Definition: var.c:18144
SCIP_Bool SCIPvarMayRoundDown(SCIP_VAR *var)
Definition: var.c:3440
SCIP_Real SCIPvarGetObj(SCIP_VAR *var)
Definition: var.c:17926
const char * SCIPvarGetName(SCIP_VAR *var)
Definition: var.c:17419
SCIP_Real SCIPvarGetLbLocal(SCIP_VAR *var)
Definition: var.c:18134
void SCIPenableVarHistory(SCIP *scip)
Definition: scip_var.c:8741
void SCIPfreeRandom(SCIP *scip, SCIP_RANDNUMGEN **randnumgen)
SCIP_Real SCIPrandomGetReal(SCIP_RANDNUMGEN *randnumgen, SCIP_Real minrandval, SCIP_Real maxrandval)
Definition: misc.c:10130
SCIP_RETCODE SCIPcreateRandom(SCIP *scip, SCIP_RANDNUMGEN **randnumgen, unsigned int initialseed, SCIP_Bool useglobalseed)
static SCIP_RETCODE performRandRounding(SCIP *scip, SCIP_HEURDATA *heurdata, SCIP_SOL *sol, SCIP_VAR **cands, int ncands, SCIP_Bool propagate, SCIP_RESULT *result)
static SCIP_DECL_HEURINITSOL(heurInitsolRandrounding)
#define HEUR_TIMING
#define HEUR_FREQOFS
#define HEUR_DESC
#define DEFAULT_ONCEPERNODE
#define HEUR_DISPCHAR
#define HEUR_MAXDEPTH
#define HEUR_PRIORITY
static SCIP_DECL_HEURINIT(heurInitRandrounding)
#define HEUR_NAME
static SCIP_DECL_HEUREXITSOL(heurExitsolRandrounding)
static SCIP_RETCODE performLPRandRounding(SCIP *scip, SCIP_HEURDATA *heurdata, SCIP_HEURTIMING heurtiming, SCIP_Bool propagate, SCIP_RESULT *result)
#define DEFAULT_PROPAGATEONLYROOT
static SCIP_DECL_HEURCOPY(heurCopyRandrounding)
static SCIP_DECL_HEURFREE(heurFreeRandrounding)
static SCIP_DECL_HEUREXIT(heurExitRandrounding)
#define DEFAULT_RANDSEED
static SCIP_DECL_HEUREXEC(heurExecRandrounding)
#define HEUR_FREQ
#define DEFAULT_USESIMPLEROUNDING
#define HEUR_USESSUBSCIP
#define DEFAULT_MAXPROPROUNDS
randomized LP rounding heuristic which also generates conflicts via an auxiliary probing tree
memory allocation routines
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 the probing mode
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
@ SCIP_LPSOLSTAT_OPTIMAL
Definition: type_lp.h:43
@ SCIP_DIDNOTRUN
Definition: type_result.h:42
@ SCIP_DIDNOTFIND
Definition: type_result.h:44
@ SCIP_FOUNDSOL
Definition: type_result.h:56
enum SCIP_Result SCIP_RESULT
Definition: type_result.h:61
@ SCIP_OKAY
Definition: type_retcode.h:42
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:63
#define SCIP_HEURTIMING_DURINGPRICINGLOOP
Definition: type_timing.h:89
unsigned int SCIP_HEURTIMING
Definition: type_timing.h:101
#define SCIP_HEURTIMING_AFTERLPNODE
Definition: type_timing.h:81
@ SCIP_VARSTATUS_COLUMN
Definition: type_var.h:51