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