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-2021 Konrad-Zuse-Zentrum */
7 /* fuer Informationstechnik Berlin */
8 /* */
9 /* SCIP is distributed under the terms of the ZIB Academic License. */
10 /* */
11 /* You should have received a copy of the ZIB Academic License */
12 /* along with SCIP; see the file COPYING. If not visit scipopt.org. */
13 /* */
14 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
15 
16 /**@file heur_randrounding.c
17  * @ingroup DEFPLUGINS_HEUR
18  * @brief randomized LP rounding heuristic which also generates conflicts via an auxiliary probing tree
19  * @author Gregor Hendel
20  *
21  * Randomized LP rounding uses a random variable from a uniform distribution
22  * over [0,1] to determine whether the fractional LP value x should be rounded
23  * up with probability x - floor(x) or down with probability ceil(x) - x.
24  *
25  * This implementation uses domain propagation techniques to tighten the variable domains after every
26  * rounding step.
27  */
28 
29 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
30 
31 #include "blockmemshell/memory.h"
32 #include "scip/heur_randrounding.h"
33 #include "scip/pub_heur.h"
34 #include "scip/pub_message.h"
35 #include "scip/pub_misc.h"
36 #include "scip/pub_var.h"
37 #include "scip/scip_branch.h"
38 #include "scip/scip_general.h"
39 #include "scip/scip_heur.h"
40 #include "scip/scip_lp.h"
41 #include "scip/scip_mem.h"
42 #include "scip/scip_message.h"
43 #include "scip/scip_numerics.h"
44 #include "scip/scip_param.h"
45 #include "scip/scip_probing.h"
46 #include "scip/scip_randnumgen.h"
47 #include "scip/scip_sol.h"
48 #include "scip/scip_solvingstats.h"
49 #include "scip/scip_tree.h"
50 #include "scip/scip_var.h"
51 #include <string.h>
52 
53 #define HEUR_NAME "randrounding"
54 #define HEUR_DESC "fast LP rounding heuristic"
55 #define HEUR_DISPCHAR SCIP_HEURDISPCHAR_ROUNDING
56 #define HEUR_PRIORITY -200
57 #define HEUR_FREQ 20
58 #define HEUR_FREQOFS 0
59 #define HEUR_MAXDEPTH -1
60 #define HEUR_TIMING SCIP_HEURTIMING_DURINGLPLOOP
61 #define HEUR_USESSUBSCIP FALSE /**< does the heuristic use a secondary SCIP instance? */
62 
63 #define DEFAULT_ONCEPERNODE FALSE /**< should the heuristic only be called once per node? */
64 #define DEFAULT_RANDSEED 23 /**< default random seed */
65 #define DEFAULT_USESIMPLEROUNDING FALSE /**< should the heuristic apply the variable lock strategy of simple rounding,
66  * if possible? */
67 #define DEFAULT_MAXPROPROUNDS 1 /**< limit of rounds for each propagation call */
68 #define DEFAULT_PROPAGATEONLYROOT TRUE /**< should the probing part of the heuristic be applied exclusively at the root node */
69 
70 /* locally defined heuristic data */
71 struct SCIP_HeurData
72 {
73  SCIP_SOL* sol; /**< working solution */
74  SCIP_RANDNUMGEN* randnumgen; /**< random number generation */
75  SCIP_Longint lastlp; /**< last LP number where the heuristic was applied */
76  int maxproprounds; /**< limit of rounds for each propagation call */
77  SCIP_Bool oncepernode; /**< should the heuristic only be called once per node? */
78  SCIP_Bool usesimplerounding; /**< should the heuristic apply the variable lock strategy of simple rounding,
79  * if possible? */
80  SCIP_Bool propagateonlyroot; /**< should the probing part of the heuristic be applied exclusively at the root node? */
81 };
82 
83 /*
84  * Local methods
85  */
86 
87 /** perform randomized rounding of the given solution. Domain propagation is optionally applied after every rounding
88  * step
89  */
90 static
92  SCIP* scip, /**< SCIP main data structure */
93  SCIP_HEURDATA* heurdata, /**< heuristic data */
94  SCIP_SOL* sol, /**< solution to round */
95  SCIP_VAR** cands, /**< candidate variables */
96  int ncands, /**< number of candidates */
97  SCIP_Bool propagate, /**< should the rounding be propagated? */
98  SCIP_RESULT* result /**< pointer to store the result of the heuristic call */
99  )
100 {
101  int c;
102  SCIP_Bool stored;
103  SCIP_VAR** permutedcands;
104  SCIP_Bool cutoff;
105 
106  assert(heurdata != NULL);
107 
108  /* start probing tree before rounding begins */
109  if( propagate )
110  {
111  SCIP_CALL( SCIPstartProbing(scip) );
112  SCIPenableVarHistory(scip);
113  }
114 
115  /* copy and permute the candidate array */
116  SCIP_CALL( SCIPduplicateBufferArray(scip, &permutedcands, cands, ncands) );
117 
118  assert(permutedcands != NULL);
119 
120  SCIPrandomPermuteArray(heurdata->randnumgen, (void **)permutedcands, 0, ncands);
121  cutoff = FALSE;
122 
123  /* loop over candidates and perform randomized rounding and optionally probing. */
124  for (c = 0; c < ncands && !cutoff; ++c)
125  {
126  SCIP_VAR* var;
127  SCIP_Real oldsolval;
128  SCIP_Real newsolval;
129  SCIP_Bool mayrounddown;
130  SCIP_Bool mayroundup;
131  SCIP_Longint ndomreds;
132  SCIP_Real lb;
133  SCIP_Real ub;
134  SCIP_Real ceilval;
135  SCIP_Real floorval;
136 
137  /* get next variable from permuted candidate array */
138  var = permutedcands[c];
139  oldsolval = SCIPgetSolVal(scip, sol, var);
140  lb = SCIPvarGetLbLocal(var);
141  ub = SCIPvarGetUbLocal(var);
142 
143  assert( ! SCIPisFeasIntegral(scip, oldsolval) );
144  assert( SCIPvarGetStatus(var) == SCIP_VARSTATUS_COLUMN );
145 
146  mayrounddown = SCIPvarMayRoundDown(var);
147  mayroundup = SCIPvarMayRoundUp(var);
148  ceilval = SCIPfeasCeil(scip, oldsolval);
149  floorval = SCIPfeasFloor(scip, oldsolval);
150 
151  SCIPdebugMsg(scip, "rand rounding heuristic: var <%s>, val=%g, rounddown=%u, roundup=%u\n",
152  SCIPvarGetName(var), oldsolval, mayrounddown, mayroundup);
153 
154  /* abort if rounded ceil and floor value lie outside the variable domain. Otherwise, check if
155  * bounds allow only one rounding direction, anyway */
156  if( lb > ceilval + 0.5 || ub < floorval - 0.5 )
157  {
158  cutoff = TRUE;
159  break;
160  }
161  else if( SCIPisFeasEQ(scip, lb, ceilval) )
162  {
163  /* only rounding up possible */
164  assert(SCIPisFeasGE(scip, ub, ceilval));
165  newsolval = ceilval;
166  }
167  else if( SCIPisFeasEQ(scip, ub, floorval) )
168  {
169  /* only rounding down possible */
170  assert(SCIPisFeasLE(scip,lb, floorval));
171  newsolval = floorval;
172  }
173  else if( !heurdata->usesimplerounding || !(mayroundup || mayrounddown) )
174  {
175  /* the standard randomized rounding */
176  SCIP_Real randnumber;
177 
178  randnumber = SCIPrandomGetReal(heurdata->randnumgen, 0.0, 1.0);
179  if( randnumber <= oldsolval - floorval )
180  newsolval = ceilval;
181  else
182  newsolval = floorval;
183  }
184  /* choose rounding direction, if possible, or use the only direction guaranteed to be feasible */
185  else if( mayrounddown && mayroundup )
186  {
187  /* we can round in both directions: round in objective function direction */
188  if ( SCIPvarGetObj(var) >= 0.0 )
189  newsolval = floorval;
190  else
191  newsolval = ceilval;
192  }
193  else if( mayrounddown )
194  newsolval = floorval;
195  else
196  {
197  assert(mayroundup);
198  newsolval = ceilval;
199  }
200 
201  assert(SCIPisFeasLE(scip, lb, newsolval));
202  assert(SCIPisFeasGE(scip, ub, newsolval));
203 
204  /* if propagation is enabled, fix the candidate variable to its rounded value and propagate the solution */
205  if( propagate )
206  {
207  SCIP_Bool lbadjust;
208  SCIP_Bool ubadjust;
209 
210  lbadjust = SCIPisGT(scip, newsolval, lb);
211  ubadjust = SCIPisLT(scip, newsolval, ub);
212 
213  assert( lbadjust || ubadjust || SCIPisFeasEQ(scip, lb, ub));
214 
215  /* enter a new probing node if the variable was not already fixed before */
216  if( lbadjust || ubadjust )
217  {
218  if( SCIPisStopped(scip) )
219  break;
220 
221  /* We only want to create a new probing node if we do not exceeed the maximal tree depth,
222  * otherwise we finish at this point.
223  * @todo: Maybe we want to continue with the same node because we do not backtrack.
224  */
225  if( SCIPgetDepth(scip) < SCIP_MAXTREEDEPTH )
226  {
227  SCIP_CALL( SCIPnewProbingNode(scip) );
228  }
229  else
230  break;
231 
232  /* tighten the bounds to fix the variable for the probing node */
233  if( lbadjust )
234  {
235  SCIP_CALL( SCIPchgVarLbProbing(scip, var, newsolval) );
236  }
237  if( ubadjust )
238  {
239  SCIP_CALL( SCIPchgVarUbProbing(scip, var, newsolval) );
240  }
241 
242  /* call propagation routines for the reduced problem */
243  SCIP_CALL( SCIPpropagateProbing(scip, heurdata->maxproprounds, &cutoff, &ndomreds) );
244  }
245  }
246  /* store new solution value */
247  SCIP_CALL( SCIPsetSolVal(scip, sol, var, newsolval) );
248  }
249 
250  /* if no cutoff was detected, the solution is a candidate to be checked for feasibility */
251  if( !cutoff && ! SCIPisStopped(scip) )
252  {
253  if( SCIPallColsInLP(scip) )
254  {
255  /* check solution for feasibility, and add it to solution store if possible
256  * neither integrality nor feasibility of LP rows has to be checked, because all fractional
257  * variables were already moved in feasible direction to the next integer
258  */
259  SCIP_CALL( SCIPtrySol(scip, sol, FALSE, FALSE, FALSE, FALSE, TRUE, &stored) );
260  }
261  else
262  {
263  /* if there are variables which are not present in the LP, e.g., for
264  * column generation, we need to check their bounds
265  */
266  SCIP_CALL( SCIPtrySol(scip, sol, FALSE, FALSE, TRUE, FALSE, TRUE, &stored) );
267  }
268 
269  if( stored )
270  {
271 #ifdef SCIP_DEBUG
272  SCIPdebugMsg(scip, "found feasible rounded solution:\n");
273  SCIP_CALL( SCIPprintSol(scip, sol, NULL, FALSE) );
274 #endif
275  *result = SCIP_FOUNDSOL;
276  }
277  }
278 
279  assert( !propagate || SCIPinProbing(scip) );
280 
281  /* exit probing mode and free locally allocated memory */
282  if( propagate )
283  {
284  SCIP_CALL( SCIPendProbing(scip) );
285  }
286 
287  SCIPfreeBufferArray(scip, &permutedcands);
288 
289  return SCIP_OKAY;
290 }
291 
292 /** perform randomized LP-rounding */
293 static
295  SCIP* scip, /**< SCIP main data structure */
296  SCIP_HEURDATA* heurdata, /**< heuristic data */
297  SCIP_HEURTIMING heurtiming, /**< heuristic timing mask */
298  SCIP_Bool propagate, /**< should the heuristic apply SCIP's propagation? */
299  SCIP_RESULT* result /**< pointer to store the result of the heuristic call */
300  )
301 {
302  SCIP_SOL* sol;
303  SCIP_VAR** lpcands;
304  SCIP_Longint nlps;
305  int nlpcands;
306 
307  /* only call heuristic, if an optimal LP solution is at hand */
308  assert(SCIPgetLPSolstat(scip) == SCIP_LPSOLSTAT_OPTIMAL);
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 */
327  SCIP_CALL( SCIPlinkLPSol(scip, sol) );
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 */
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 */
477  if( SCIPgetNLPs(scip) == heurdata->lastlp )
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:977
SCIP_Bool SCIPisStopped(SCIP *scip)
Definition: scip_general.c:687
static SCIP_DECL_HEUREXIT(heurExitRandrounding)
const char * SCIPheurGetName(SCIP_HEUR *heur)
Definition: heur.c:1429
SCIP_RETCODE SCIPsetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var, SCIP_Real val)
Definition: scip_sol.c:1213
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:156
SCIP_RETCODE SCIPsetHeurExitsol(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEUREXITSOL((*heurexitsol)))
Definition: scip_heur.c:233
public methods for memory management
SCIP_HEURDATA * SCIPheurGetData(SCIP_HEUR *heur)
Definition: heur.c:1340
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:1353
#define DEFAULT_RANDSEED
#define FALSE
Definition: def.h:73
SCIP_EXPORT SCIP_Real SCIPvarGetObj(SCIP_VAR *var)
Definition: var.c:17515
SCIP_Real SCIPrandomGetReal(SCIP_RANDNUMGEN *randnumgen, SCIP_Real minrandval, SCIP_Real maxrandval)
Definition: misc.c:9981
#define TRUE
Definition: def.h:72
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:54
SCIP_RETCODE SCIPlinkLPSol(SCIP *scip, SCIP_SOL *sol)
Definition: scip_sol.c:1018
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:67
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:48
#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:17136
#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:185
SCIP_EXPORT SCIP_Bool SCIPvarMayRoundDown(SCIP_VAR *var)
Definition: var.c:3336
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:3126
#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:159
SCIP_Bool SCIPhasCurrentNodeLP(SCIP *scip)
Definition: scip_lp.c:74
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:320
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:108
public methods for the branch-and-bound tree
SCIP_EXPORT const char * SCIPvarGetName(SCIP_VAR *var)
Definition: var.c:17017
static SCIP_DECL_HEURCOPY(heurCopyRandrounding)
SCIP_Bool SCIPallColsInLP(SCIP *scip)
Definition: scip_lp.c:619
void SCIPenableVarHistory(SCIP *scip)
Definition: scip_var.c:8669
#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:88
void SCIPheurSetData(SCIP_HEUR *heur, SCIP_HEURDATA *heurdata)
Definition: heur.c:1350
#define NULL
Definition: lpi_spx1.cpp:155
SCIP_RETCODE SCIPendProbing(SCIP *scip)
Definition: scip_probing.c:251
void SCIPheurSetTimingmask(SCIP_HEUR *heur, SCIP_HEURTIMING timingmask)
Definition: heur.c:1469
#define HEUR_USESSUBSCIP
#define SCIP_CALL(x)
Definition: def.h:370
SCIP_Real SCIPfeasFloor(SCIP *scip, SCIP_Real val)
static SCIP_DECL_HEURFREE(heurFreeRandrounding)
SCIP_Real SCIPgetLPObjval(SCIP *scip)
Definition: scip_lp.c:238
#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:3347
public data structures and miscellaneous methods
int SCIPgetDepth(SCIP *scip)
Definition: scip_tree.c:638
#define SCIP_Bool
Definition: def.h:70
SCIP_RETCODE SCIPsetHeurExit(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEUREXIT((*heurexit)))
Definition: scip_heur.c:201
#define HEUR_PRIORITY
#define DEFAULT_ONCEPERNODE
SCIP_RETCODE SCIPpropagateProbing(SCIP *scip, int maxproprounds, SCIP_Bool *cutoff, SCIP_Longint *ndomredsfound)
Definition: scip_probing.c:571
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:17723
#define SCIP_MAXTREEDEPTH
Definition: def.h:306
public methods for the LP relaxation, rows and columns
SCIP_EXPORT SCIP_Real SCIPvarGetUbLocal(SCIP_VAR *var)
Definition: var.c:17733
#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:153
SCIP_RETCODE SCIPstartProbing(SCIP *scip)
Definition: scip_probing.c:110
#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:74
SCIP_RETCODE SCIPchgVarLbProbing(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound)
Definition: scip_probing.c:292
SCIP_RETCODE SCIPprintSol(SCIP *scip, SCIP_SOL *sol, FILE *file, SCIP_Bool printzeros)
Definition: scip_sol.c:1767
#define SCIP_Real
Definition: def.h:163
static SCIP_DECL_HEURINIT(heurInitRandrounding)
SCIP_RETCODE SCIPchgVarUbProbing(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound)
Definition: scip_probing.c:336
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:386
SCIP_RETCODE SCIPsetHeurInitsol(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURINITSOL((*heurinitsol)))
Definition: scip_heur.c:217
#define SCIP_Longint
Definition: def.h:148
#define HEUR_FREQ
SCIP_RETCODE SCIPsetHeurFree(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURFREE((*heurfree)))
Definition: scip_heur.c:169
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:10030
static SCIP_DECL_HEURINITSOL(heurInitsolRandrounding)
#define DEFAULT_PROPAGATEONLYROOT
memory allocation routines