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-2019 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 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 */
68 
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  {
206  SCIP_Bool lbadjust;
207  SCIP_Bool ubadjust;
208 
209  lbadjust = SCIPisGT(scip, newsolval, lb);
210  ubadjust = SCIPisLT(scip, newsolval, ub);
211 
212  assert( lbadjust || ubadjust || SCIPisFeasEQ(scip, lb, ub));
213 
214  /* enter a new probing node if the variable was not already fixed before */
215  if( lbadjust || ubadjust )
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 */
232  if( lbadjust )
233  {
234  SCIP_CALL( SCIPchgVarLbProbing(scip, var, newsolval) );
235  }
236  if( ubadjust )
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 */
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 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
SCIP_RETCODE SCIPsetHeurExitsol(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEUREXITSOL((*heurexitsol)))
Definition: scip_heur.c:312
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
void SCIPfreeRandom(SCIP *scip, SCIP_RANDNUMGEN **randnumgen)
#define HEUR_FREQOFS
SCIP_RETCODE SCIPlinkLPSol(SCIP *scip, SCIP_SOL *sol)
Definition: scip_sol.c:1075
#define NULL
Definition: def.h:246
static SCIP_DECL_HEUREXIT(heurExitRandrounding)
SCIP_Bool SCIPisFeasEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
public methods for SCIP parameter handling
SCIP_RETCODE SCIPincludeHeurRandrounding(SCIP *scip)
public methods for memory management
SCIP_Real SCIPgetCutoffbound(SCIP *scip)
unsigned int SCIP_HEURTIMING
Definition: type_timing.h:97
SCIP_RETCODE SCIPsetHeurExit(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEUREXIT((*heurexit)))
Definition: scip_heur.c:280
static SCIP_RETCODE performRandRounding(SCIP *scip, SCIP_HEURDATA *heurdata, SCIP_SOL *sol, SCIP_VAR **cands, int ncands, SCIP_Bool propagate, SCIP_RESULT *result)
SCIP_Real SCIPvarGetLbLocal(SCIP_VAR *var)
Definition: var.c:17400
SCIP_Bool SCIPisGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
#define DEFAULT_RANDSEED
SCIP_Bool SCIPisFeasGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
#define FALSE
Definition: def.h:72
#define TRUE
Definition: def.h:71
void SCIPrandomPermuteArray(SCIP_RANDNUMGEN *randnumgen, void **array, int begin, int end)
Definition: misc.c:9679
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:53
static SCIP_DECL_HEUREXEC(heurExecRandrounding)
struct SCIP_HeurData SCIP_HEURDATA
Definition: type_heur.h:51
public methods for problem variables
#define SCIPfreeBlockMemory(scip, ptr)
Definition: scip_mem.h:114
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:187
SCIP_RETCODE SCIPchgVarLbProbing(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound)
Definition: scip_probing.c:356
#define SCIP_HEURTIMING_DURINGPRICINGLOOP
Definition: type_timing.h:85
#define HEUR_DESC
#define SCIPduplicateBufferArray(scip, ptr, source, num)
Definition: scip_mem.h:138
#define SCIPfreeBufferArray(scip, ptr)
Definition: scip_mem.h:142
void SCIPheurSetData(SCIP_HEUR *heur, SCIP_HEURDATA *heurdata)
Definition: heur.c:1175
#define SCIPallocBlockMemory(scip, ptr)
Definition: scip_mem.h:97
public methods for SCIP variables
#define SCIPdebugMsg
Definition: scip_message.h:88
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:155
SCIP_Real SCIPfeasCeil(SCIP *scip, SCIP_Real val)
public methods for numerical tolerances
SCIP_Real SCIPfeasFloor(SCIP *scip, SCIP_Real val)
public methods for querying solving statistics
public methods for the branch-and-bound tree
SCIP_RETCODE SCIPsetHeurInitsol(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURINITSOL((*heurinitsol)))
Definition: scip_heur.c:296
const char * SCIPheurGetName(SCIP_HEUR *heur)
Definition: heur.c:1254
static SCIP_DECL_HEURCOPY(heurCopyRandrounding)
SCIP_RETCODE SCIPsetHeurFree(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURFREE((*heurfree)))
Definition: scip_heur.c:248
SCIP_Bool SCIPisLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_RETCODE SCIPpropagateProbing(SCIP *scip, int maxproprounds, SCIP_Bool *cutoff, SCIP_Longint *ndomredsfound)
Definition: scip_probing.c:630
#define SCIP_HEURTIMING_AFTERLPNODE
Definition: type_timing.h:73
static SCIP_DECL_HEUREXITSOL(heurExitsolRandrounding)
SCIP_RETCODE SCIPendProbing(SCIP *scip)
Definition: scip_probing.c:315
const char * SCIPvarGetName(SCIP_VAR *var)
Definition: var.c:16730
#define HEUR_USESSUBSCIP
#define SCIP_CALL(x)
Definition: def.h:358
SCIP_Bool SCIPisFeasLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
static SCIP_DECL_HEURFREE(heurFreeRandrounding)
#define DEFAULT_USESIMPLEROUNDING
SCIP_Bool SCIPhasCurrentNodeLP(SCIP *scip)
Definition: scip_lp.c:141
public methods for primal heuristic plugins and divesets
#define HEUR_NAME
SCIP_RETCODE SCIPcreateRandom(SCIP *scip, SCIP_RANDNUMGEN **randnumgen, unsigned int initialseed, SCIP_Bool useglobalseed)
SCIP_RETCODE SCIPsetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var, SCIP_Real val)
Definition: scip_sol.c:1270
public data structures and miscellaneous methods
#define SCIP_Bool
Definition: def.h:69
SCIP_LPSOLSTAT SCIPgetLPSolstat(SCIP *scip)
Definition: scip_lp.c:226
#define HEUR_PRIORITY
#define DEFAULT_ONCEPERNODE
int SCIPgetDepth(SCIP *scip)
Definition: scip_tree.c:715
static SCIP_RETCODE performLPRandRounding(SCIP *scip, SCIP_HEURDATA *heurdata, SCIP_HEURTIMING heurtiming, SCIP_Bool propagate, SCIP_RESULT *result)
#define HEUR_TIMING
SCIP_RETCODE SCIPfreeSol(SCIP *scip, SCIP_SOL **sol)
Definition: scip_sol.c:1034
void SCIPenableVarHistory(SCIP *scip)
Definition: scip_var.c:8550
SCIP_Real SCIPvarGetObj(SCIP_VAR *var)
Definition: var.c:17192
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:3182
#define SCIP_MAXTREEDEPTH
Definition: def.h:294
SCIP_Real SCIPrandomGetReal(SCIP_RANDNUMGEN *randnumgen, SCIP_Real minrandval, SCIP_Real maxrandval)
Definition: misc.c:9630
SCIP_Bool SCIPinProbing(SCIP *scip)
Definition: scip_probing.c:152
public methods for the LP relaxation, rows and columns
#define HEUR_MAXDEPTH
public methods for branching rule plugins and branching
general public methods
SCIP_Real SCIPgetLPObjval(SCIP *scip)
Definition: scip_lp.c:305
SCIP_Bool SCIPisGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
public methods for solutions
public methods for random numbers
public methods for the probing mode
SCIP_Bool SCIPisRelaxSolValid(SCIP *scip)
Definition: scip_var.c:2529
#define HEUR_DISPCHAR
public methods for message output
SCIP_RETCODE SCIPsetHeurInit(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURINIT((*heurinit)))
Definition: scip_heur.c:264
#define DEFAULT_MAXPROPROUNDS
SCIP_VARSTATUS SCIPvarGetStatus(SCIP_VAR *var)
Definition: var.c:16849
#define SCIP_Real
Definition: def.h:157
SCIP_Bool SCIPisStopped(SCIP *scip)
Definition: scip_general.c:738
static SCIP_DECL_HEURINIT(heurInitRandrounding)
public methods for message handling
void SCIPheurSetTimingmask(SCIP_HEUR *heur, SCIP_HEURTIMING timingmask)
Definition: heur.c:1294
#define SCIP_Longint
Definition: def.h:142
SCIP_Bool SCIPallColsInLP(SCIP *scip)
Definition: scip_lp.c:652
#define HEUR_FREQ
randomized LP rounding heuristic which also generates conflicts via an auxiliary probing tree ...
SCIP_RETCODE SCIPsetHeurCopy(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURCOPY((*heurcopy)))
Definition: scip_heur.c:232
SCIP_Real SCIPvarGetUbLocal(SCIP_VAR *var)
Definition: var.c:17410
SCIP_RETCODE SCIPnewProbingNode(SCIP *scip)
Definition: scip_probing.c:220
SCIP_Bool SCIPisFeasIntegral(SCIP *scip, SCIP_Real val)
SCIP_RETCODE SCIPstartProbing(SCIP *scip)
Definition: scip_probing.c:174
public methods for primal heuristics
SCIP_HEURDATA * SCIPheurGetData(SCIP_HEUR *heur)
Definition: heur.c:1165
SCIP_Longint SCIPgetNLPs(SCIP *scip)
SCIP_RETCODE SCIPchgVarUbProbing(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound)
Definition: scip_probing.c:400
SCIP_Real SCIPgetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var)
Definition: scip_sol.c:1410
SCIP_Bool SCIPvarMayRoundUp(SCIP_VAR *var)
Definition: var.c:3330
SCIP_Bool SCIPvarMayRoundDown(SCIP_VAR *var)
Definition: var.c:3319
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:129
static SCIP_DECL_HEURINITSOL(heurInitsolRandrounding)
#define DEFAULT_PROPAGATEONLYROOT
SCIP_RETCODE SCIPcreateSol(SCIP *scip, SCIP_SOL **sol, SCIP_HEUR *heur)
Definition: scip_sol.c:377
memory allocation routines
SCIP_RETCODE SCIPprintSol(SCIP *scip, SCIP_SOL *sol, FILE *file, SCIP_Bool printzeros)
Definition: scip_sol.c:1824