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 2002-2022 Zuse Institute Berlin */
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 
40 #include "blockmemshell/memory.h"
41 #include "scip/heur_randrounding.h"
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"
55 #include "scip/scip_randnumgen.h"
56 #include "scip/scip_sol.h"
57 #include "scip/scip_solvingstats.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 */
80 struct 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  */
99 static
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  {
120  SCIP_CALL( SCIPstartProbing(scip) );
121  SCIPenableVarHistory(scip);
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  */
234  if( SCIPgetDepth(scip) < SCIP_MAXTREEDEPTH )
235  {
236  SCIP_CALL( SCIPnewProbingNode(scip) );
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");
282  SCIP_CALL( SCIPprintSol(scip, sol, NULL, FALSE) );
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  {
293  SCIP_CALL( SCIPendProbing(scip) );
294  }
295 
296  SCIPfreeBufferArray(scip, &permutedcands);
297 
298  return SCIP_OKAY;
299 }
300 
301 /** perform randomized LP-rounding */
302 static
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 */
317  assert(SCIPgetLPSolstat(scip) == SCIP_LPSOLSTAT_OPTIMAL);
318 
319  /* only call heuristic, if the LP objective value is smaller than the cutoff bound */
320  if( SCIPisGE(scip, SCIPgetLPObjval(scip), SCIPgetCutoffbound(scip)) )
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 */
336  SCIP_CALL( SCIPlinkLPSol(scip, sol) );
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) */
358 static
359 SCIP_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) */
372 static
373 SCIP_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) */
391 static
392 SCIP_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) */
412 static
413 SCIP_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) */
431 static
432 SCIP_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) */
451 static
452 SCIP_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 */
461 static
462 SCIP_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 */
478  if( SCIPisGE(scip, SCIPgetLPObjval(scip), SCIPgetCutoffbound(scip)) )
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 */
513  SCIP_CALL( SCIPincludeHeurBasic(scip, &heur,
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 }
enum SCIP_Result SCIP_RESULT
Definition: type_result.h:61
SCIP_RETCODE SCIPsetHeurExitsol(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEUREXITSOL((*heurexitsol)))
Definition: scip_heur.c:242
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
void SCIPfreeRandom(SCIP *scip, SCIP_RANDNUMGEN **randnumgen)
#define HEUR_FREQOFS
SCIP_RETCODE SCIPlinkLPSol(SCIP *scip, SCIP_SOL *sol)
Definition: scip_sol.c:1026
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:106
SCIP_RETCODE SCIPsetHeurExit(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEUREXIT((*heurexit)))
Definition: scip_heur.c:210
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:17975
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:96
#define TRUE
Definition: def.h:95
void SCIPrandomPermuteArray(SCIP_RANDNUMGEN *randnumgen, void **array, int begin, int end)
Definition: misc.c:10083
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:63
static SCIP_DECL_HEUREXEC(heurExecRandrounding)
struct SCIP_HeurData SCIP_HEURDATA
Definition: type_heur.h:76
public methods for problem variables
#define SCIPfreeBlockMemory(scip, ptr)
Definition: scip_mem.h:108
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 SCIPchgVarLbProbing(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound)
Definition: scip_probing.c:301
#define SCIP_HEURTIMING_DURINGPRICINGLOOP
Definition: type_timing.h:94
#define HEUR_DESC
#define SCIPduplicateBufferArray(scip, ptr, source, num)
Definition: scip_mem.h:132
#define SCIPfreeBufferArray(scip, ptr)
Definition: scip_mem.h:136
void SCIPheurSetData(SCIP_HEUR *heur, SCIP_HEURDATA *heurdata)
Definition: heur.c:1371
#define SCIPallocBlockMemory(scip, ptr)
Definition: scip_mem.h:89
public methods for SCIP variables
#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_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:226
const char * SCIPheurGetName(SCIP_HEUR *heur)
Definition: heur.c:1450
static SCIP_DECL_HEURCOPY(heurCopyRandrounding)
SCIP_RETCODE SCIPsetHeurFree(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURFREE((*heurfree)))
Definition: scip_heur.c:178
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:580
#define SCIP_HEURTIMING_AFTERLPNODE
Definition: type_timing.h:82
static SCIP_DECL_HEUREXITSOL(heurExitsolRandrounding)
SCIP_RETCODE SCIPendProbing(SCIP *scip)
Definition: scip_probing.c:260
const char * SCIPvarGetName(SCIP_VAR *var)
Definition: var.c:17260
#define NULL
Definition: lpi_spx1.cpp:164
#define HEUR_USESSUBSCIP
#define SCIP_CALL(x)
Definition: def.h:393
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:83
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:1221
public data structures and miscellaneous methods
#define SCIP_Bool
Definition: def.h:93
SCIP_LPSOLSTAT SCIPgetLPSolstat(SCIP *scip)
Definition: scip_lp.c:168
#define HEUR_PRIORITY
#define DEFAULT_ONCEPERNODE
int SCIPgetDepth(SCIP *scip)
Definition: scip_tree.c:670
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:985
void SCIPenableVarHistory(SCIP *scip)
Definition: scip_var.c:8747
SCIP_Real SCIPvarGetObj(SCIP_VAR *var)
Definition: var.c:17767
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:3134
#define SCIP_MAXTREEDEPTH
Definition: def.h:329
SCIP_Real SCIPrandomGetReal(SCIP_RANDNUMGEN *randnumgen, SCIP_Real minrandval, SCIP_Real maxrandval)
Definition: misc.c:10034
SCIP_Bool SCIPinProbing(SCIP *scip)
Definition: scip_probing.c:97
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:247
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
#define HEUR_DISPCHAR
public methods for message output
SCIP_RETCODE SCIPsetHeurInit(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURINIT((*heurinit)))
Definition: scip_heur.c:194
#define DEFAULT_MAXPROPROUNDS
SCIP_VARSTATUS SCIPvarGetStatus(SCIP_VAR *var)
Definition: var.c:17379
#define SCIP_Real
Definition: def.h:186
SCIP_Bool SCIPisStopped(SCIP *scip)
Definition: scip_general.c:703
static SCIP_DECL_HEURINIT(heurInitRandrounding)
public methods for message handling
void SCIPheurSetTimingmask(SCIP_HEUR *heur, SCIP_HEURTIMING timingmask)
Definition: heur.c:1490
#define SCIP_Longint
Definition: def.h:171
SCIP_Bool SCIPallColsInLP(SCIP *scip)
Definition: scip_lp.c:649
#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:162
SCIP_Real SCIPvarGetUbLocal(SCIP_VAR *var)
Definition: var.c:17985
SCIP_RETCODE SCIPnewProbingNode(SCIP *scip)
Definition: scip_probing.c:165
SCIP_Bool SCIPisFeasIntegral(SCIP *scip, SCIP_Real val)
SCIP_RETCODE SCIPstartProbing(SCIP *scip)
Definition: scip_probing.c:119
public methods for primal heuristics
SCIP_HEURDATA * SCIPheurGetData(SCIP_HEUR *heur)
Definition: heur.c:1361
SCIP_Longint SCIPgetNLPs(SCIP *scip)
SCIP_RETCODE SCIPchgVarUbProbing(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound)
Definition: scip_probing.c:345
SCIP_Real SCIPgetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var)
Definition: scip_sol.c:1361
SCIP_Bool SCIPvarMayRoundUp(SCIP_VAR *var)
Definition: var.c:3454
SCIP_Bool SCIPvarMayRoundDown(SCIP_VAR *var)
Definition: var.c:3443
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
static SCIP_DECL_HEURINITSOL(heurInitsolRandrounding)
#define DEFAULT_PROPAGATEONLYROOT
SCIP_RETCODE SCIPcreateSol(SCIP *scip, SCIP_SOL **sol, SCIP_HEUR *heur)
Definition: scip_sol.c:328
memory allocation routines
SCIP_RETCODE SCIPprintSol(SCIP *scip, SCIP_SOL *sol, FILE *file, SCIP_Bool printzeros)
Definition: scip_sol.c:1775