randomized LP rounding heuristic which also generates conflicts via an auxiliary probing tree
Randomized LP rounding uses a random variable from a uniform distribution over [0,1] to determine whether the fractional LP value x should be rounded up with probability x - floor(x) or down with probability ceil(x) - x.
This implementation uses domain propagation techniques to tighten the variable domains after every rounding step.
Definition in file heur_randrounding.c.
#include "blockmemshell/memory.h"
#include "scip/heur_randrounding.h"
#include "scip/pub_heur.h"
#include "scip/pub_message.h"
#include "scip/pub_misc.h"
#include "scip/pub_var.h"
#include "scip/scip_branch.h"
#include "scip/scip_general.h"
#include "scip/scip_heur.h"
#include "scip/scip_lp.h"
#include "scip/scip_mem.h"
#include "scip/scip_message.h"
#include "scip/scip_numerics.h"
#include "scip/scip_param.h"
#include "scip/scip_probing.h"
#include "scip/scip_randnumgen.h"
#include "scip/scip_sol.h"
#include "scip/scip_solvingstats.h"
#include "scip/scip_tree.h"
#include "scip/scip_var.h"
#include <string.h>
Go to the source code of this file.
Macros | |
#define | HEUR_NAME "randrounding" |
#define | HEUR_DESC "fast LP rounding heuristic" |
#define | HEUR_DISPCHAR SCIP_HEURDISPCHAR_ROUNDING |
#define | HEUR_PRIORITY -200 |
#define | HEUR_FREQ 20 |
#define | HEUR_FREQOFS 0 |
#define | HEUR_MAXDEPTH -1 |
#define | HEUR_TIMING SCIP_HEURTIMING_DURINGLPLOOP |
#define | HEUR_USESSUBSCIP FALSE |
#define | DEFAULT_ONCEPERNODE FALSE |
#define | DEFAULT_RANDSEED 23 |
#define | DEFAULT_USESIMPLEROUNDING FALSE |
#define | DEFAULT_MAXPROPROUNDS 1 |
#define | DEFAULT_PROPAGATEONLYROOT TRUE |
Functions | |
static SCIP_RETCODE | performRandRounding (SCIP *scip, SCIP_HEURDATA *heurdata, SCIP_SOL *sol, SCIP_VAR **cands, int ncands, SCIP_Bool propagate, SCIP_RESULT *result) |
static SCIP_RETCODE | performLPRandRounding (SCIP *scip, SCIP_HEURDATA *heurdata, SCIP_HEURTIMING heurtiming, SCIP_Bool propagate, SCIP_RESULT *result) |
static | SCIP_DECL_HEURCOPY (heurCopyRandrounding) |
static | assert (heur !=NULL) |
assert (strcmp(SCIPheurGetName(heur), HEUR_NAME)==0) | |
assert (scip !=NULL) | |
assert (heurdata !=NULL) | |
SCIPfreeBlockMemory (scip, &heurdata) | |
SCIPheurSetData (heur, NULL) | |
SCIPcreateSol (scip, &heurdata->sol, heur)) | |
SCIPcreateRandom (scip, &heurdata->randnumgen, DEFAULT_RANDSEED, TRUE)) | |
SCIPfreeSol (scip, &heurdata->sol)) | |
SCIPfreeRandom (scip, &heurdata->randnumgen) | |
static | SCIP_DECL_HEURINITSOL (heurInitsolRandrounding) |
static | SCIP_DECL_HEUREXITSOL (heurExitsolRandrounding) |
assert (result !=NULL) | |
assert (SCIPhasCurrentNodeLP(scip)) | |
if (SCIPgetLPSolstat(scip) !=SCIP_LPSOLSTAT_OPTIMAL) |
Variables | |
heurdata = SCIPheurGetData(heur) | |
return | SCIP_OKAY |
heurdata | lastlp = -1 |
static SCIP_Bool | propagate |
* | result = SCIP_DIDNOTRUN |
#define HEUR_NAME "randrounding" |
Definition at line 62 of file heur_randrounding.c.
#define HEUR_DESC "fast LP rounding heuristic" |
Definition at line 63 of file heur_randrounding.c.
#define HEUR_DISPCHAR SCIP_HEURDISPCHAR_ROUNDING |
Definition at line 64 of file heur_randrounding.c.
#define HEUR_PRIORITY -200 |
Definition at line 65 of file heur_randrounding.c.
#define HEUR_FREQ 20 |
Definition at line 66 of file heur_randrounding.c.
#define HEUR_FREQOFS 0 |
Definition at line 67 of file heur_randrounding.c.
#define HEUR_MAXDEPTH -1 |
Definition at line 68 of file heur_randrounding.c.
#define HEUR_TIMING SCIP_HEURTIMING_DURINGLPLOOP |
Definition at line 69 of file heur_randrounding.c.
#define HEUR_USESSUBSCIP FALSE |
does the heuristic use a secondary SCIP instance?
Definition at line 70 of file heur_randrounding.c.
#define DEFAULT_ONCEPERNODE FALSE |
should the heuristic only be called once per node?
Definition at line 72 of file heur_randrounding.c.
Referenced by SCIPincludeHeurRounding(), and SCIPincludeHeurSimplerounding().
#define DEFAULT_RANDSEED 23 |
default random seed
Definition at line 73 of file heur_randrounding.c.
#define DEFAULT_USESIMPLEROUNDING FALSE |
should the heuristic apply the variable lock strategy of simple rounding, if possible?
Definition at line 74 of file heur_randrounding.c.
#define DEFAULT_MAXPROPROUNDS 1 |
limit of rounds for each propagation call
Definition at line 76 of file heur_randrounding.c.
#define DEFAULT_PROPAGATEONLYROOT TRUE |
should the probing part of the heuristic be applied exclusively at the root node
Definition at line 77 of file heur_randrounding.c.
|
static |
perform randomized rounding of the given solution. Domain propagation is optionally applied after every rounding step
scip | SCIP main data structure |
heurdata | heuristic data |
sol | solution to round |
cands | candidate variables |
ncands | number of candidates |
propagate | should the rounding be propagated? |
result | pointer to store the result of the heuristic call |
Definition at line 100 of file heur_randrounding.c.
References assert(), c, cutoff, FALSE, heurdata, mayrounddown, mayroundup, NULL, propagate, result, SCIP_Bool, SCIP_CALL, SCIP_FOUNDSOL, SCIP_Longint, SCIP_MAXTREEDEPTH, SCIP_OKAY, SCIP_Real, SCIP_VARSTATUS_COLUMN, SCIPallColsInLP(), SCIPchgVarLbProbing(), SCIPchgVarUbProbing(), SCIPdebugMsg, SCIPduplicateBufferArray, SCIPenableVarHistory(), SCIPendProbing(), SCIPfeasCeil(), SCIPfeasFloor(), SCIPfreeBufferArray, SCIPgetDepth(), SCIPgetSolVal(), SCIPinProbing(), SCIPisFeasEQ(), SCIPisFeasGE(), SCIPisFeasIntegral(), SCIPisFeasLE(), SCIPisGT(), SCIPisLT(), SCIPisStopped(), SCIPnewProbingNode(), SCIPprintSol(), SCIPpropagateProbing(), SCIPrandomGetReal(), SCIPrandomPermuteArray(), SCIPsetSolVal(), SCIPstartProbing(), SCIPtrySol(), SCIPvarGetLbLocal(), SCIPvarGetName(), SCIPvarGetObj(), SCIPvarGetStatus(), SCIPvarGetUbLocal(), SCIPvarMayRoundDown(), SCIPvarMayRoundUp(), sol, TRUE, and var.
Referenced by performLPRandRounding().
|
static |
perform randomized LP-rounding
scip | SCIP main data structure |
heurdata | heuristic data |
heurtiming | heuristic timing mask |
propagate | should the heuristic apply SCIP's propagation? |
result | pointer to store the result of the heuristic call |
Definition at line 303 of file heur_randrounding.c.
References assert(), heurdata, lpcands, nlpcands, nlps, NULL, performRandRounding(), propagate, result, SCIP_Bool, SCIP_CALL, SCIP_DIDNOTFIND, SCIP_HEURTIMING_DURINGPRICINGLOOP, SCIP_Longint, SCIP_LPSOLSTAT_OPTIMAL, SCIP_OKAY, SCIPdebugMsg, SCIPgetCutoffbound(), SCIPgetLPBranchCands(), SCIPgetLPObjval(), SCIPgetLPSolstat(), SCIPgetNLPs(), SCIPisGE(), SCIPlinkLPSol(), and sol.
|
static |
copy method for primal heuristic plugins (called when SCIP copies plugins)
Definition at line 359 of file heur_randrounding.c.
References assert(), HEUR_NAME, NULL, SCIP_CALL, SCIP_OKAY, SCIPheurGetName(), and SCIPincludeHeurRandrounding().
assert | ( | heur ! | = NULL | ) |
assert | ( | strcmp(SCIPheurGetName(heur), HEUR_NAME) | = =0 | ) |
initialization method of primal heuristic (called after problem was transformed)
deinitialization method of primal heuristic (called before transformed problem is freed)
References HEUR_NAME.
SCIPfreeBlockMemory | ( | scip | , |
& | heurdata ) |
References heurdata.
SCIPcreateRandom | ( | scip | , |
&heurdata-> | randnumgen, | ||
DEFAULT_RANDSEED | , | ||
TRUE | ) |
References DEFAULT_RANDSEED, heurdata, SCIP_OKAY, and TRUE.
|
static |
solving process initialization method of primal heuristic (called when branch and bound process is about to begin)
Definition at line 432 of file heur_randrounding.c.
References assert(), HEUR_NAME, heurdata, NULL, SCIP_HEURTIMING_AFTERLPNODE, SCIP_OKAY, SCIPheurGetData(), SCIPheurGetName(), and SCIPheurSetTimingmask().
|
static |
solving process deinitialization method of primal heuristic (called before branch and bound process data is freed)
Definition at line 452 of file heur_randrounding.c.
References HEUR_TIMING, SCIP_OKAY, and SCIPheurSetTimingmask().
assert | ( | SCIPhasCurrentNodeLP(scip) | ) |
if | ( | SCIPgetLPSolstat(scip) ! | = SCIP_LPSOLSTAT_OPTIMAL | ) |
creates the rand rounding heuristic and includes it in SCIP SCIP data structure
Definition at line 474 of file heur_randrounding.c.
References heurdata, NULL, propagate, result, SCIP_LPSOLSTAT_OPTIMAL, and SCIP_OKAY.
heurdata = SCIPheurGetData(heur) |
Definition at line 382 of file heur_randrounding.c.
return SCIP_OKAY |
Definition at line 387 of file heur_randrounding.c.
heurdata lastlp = -1 |
Definition at line 402 of file heur_randrounding.c.
SCIP_Bool propagate |
execution method of primal heuristic
Definition at line 465 of file heur_randrounding.c.
Referenced by copyConsPseudoboolean(), createAndAddAndCons(), createAndAddLinearCons(), createBinaryConstraint(), createCons(), createConsCumulative(), createConsSetppc(), createConsXorIntvar(), createIndicatorConstraint(), createNormalizedKnapsack(), createNormalizedLogicor(), createNormalizedSetppc(), execRelpscost(), extractGates(), getConstraint(), if(), orbisackUpgrade(), performLPRandRounding(), performRandRounding(), performStrongbranchWithPropagation(), propAndSolve(), readConstraints(), readConstraints(), readConstraints(), readIndicators(), readObjective(), readQMatrix(), readRows(), readSOS(), readSos(), readSOScons(), SCIP_DECL_CONSCOPY(), SCIP_DECL_CONSCOPY(), SCIP_DECL_CONSCOPY(), SCIP_DECL_CONSCOPY(), SCIP_DECL_CONSCOPY(), SCIP_DECL_CONSCOPY(), SCIP_DECL_CONSCOPY(), SCIP_DECL_CONSCOPY(), SCIP_DECL_CONSCOPY(), SCIP_DECL_CONSCOPY(), SCIP_DECL_CONSCOPY(), SCIP_DECL_CONSCOPY(), SCIP_DECL_CONSCOPY(), SCIP_DECL_CONSCOPY(), SCIP_DECL_CONSCOPY(), SCIP_DECL_CONSCOPY(), SCIP_DECL_CONSCOPY(), SCIP_DECL_CONSCOPY(), SCIP_DECL_CONSCOPY(), SCIP_DECL_CONSCOPY(), SCIP_DECL_CONSCOPY(), SCIP_DECL_CONSCOPY(), SCIP_DECL_CONSCOPY(), SCIP_DECL_CONSCOPY(), SCIP_DECL_CONSCOPY(), SCIP_DECL_CONSPARSE(), SCIP_DECL_CONSPARSE(), SCIP_DECL_CONSPARSE(), SCIP_DECL_CONSPARSE(), SCIP_DECL_CONSPARSE(), SCIP_DECL_CONSPARSE(), SCIP_DECL_CONSPARSE(), SCIP_DECL_CONSPARSE(), SCIP_DECL_CONSPARSE(), SCIP_DECL_CONSPARSE(), SCIP_DECL_CONSPARSE(), SCIP_DECL_CONSPARSE(), SCIP_DECL_CONSPARSE(), SCIP_DECL_CONSPARSE(), SCIP_DECL_CONSPARSE(), SCIP_DECL_CONSPARSE(), SCIP_DECL_CONSPARSE(), SCIP_DECL_CONSPARSE(), SCIP_DECL_CONSPARSE(), SCIP_DECL_CONSPARSE(), SCIP_DECL_CONSPARSE(), SCIP_DECL_CONSPARSE(), SCIP_DECL_CONSPARSE(), SCIP_DECL_NLHDLRENFO(), SCIP_DECL_PRESOLEXEC(), SCIPapplyLockFixings(), SCIPconsCopy(), SCIPconsCreate(), SCIPconsParse(), SCIPconsSetPropagated(), SCIPcopyConsLinear(), SCIPcreateCons(), SCIPcreateConsAbspower(), SCIPcreateConsAnd(), SCIPcreateConsBounddisjunction(), SCIPcreateConsBounddisjunctionRedundant(), SCIPcreateConsCardinality(), SCIPcreateConsCumulative(), SCIPcreateConsIndicator(), SCIPcreateConsIndicatorGeneric(), SCIPcreateConsIndicatorGenericLinCons(), SCIPcreateConsIndicatorGenericLinConsPure(), SCIPcreateConsIndicatorLinCons(), SCIPcreateConsIndicatorLinConsPure(), SCIPcreateConsKnapsack(), SCIPcreateConsLinear(), SCIPcreateConsLinking(), SCIPcreateConsLogicor(), SCIPcreateConsLOP(), SCIPcreateConsNonlinear(), SCIPcreateConsOptcumulative(), SCIPcreateConsOr(), SCIPcreateConsOrbisack(), SCIPcreateConsOrbitope(), SCIPcreateConsPseudoboolean(), SCIPcreateConsPseudobooleanWithConss(), SCIPcreateConsQuadratic(), SCIPcreateConsQuadraticNonlinear(), SCIPcreateConsSetcover(), SCIPcreateConsSetpack(), SCIPcreateConsSetpart(), SCIPcreateConsSOC(), SCIPcreateConsSOS1(), SCIPcreateConsSOS2(), tsp::SCIPcreateConsSubtour(), SCIPcreateConsSuperindicator(), SCIPcreateConsSymresack(), SCIPcreateConsVarbound(), SCIPcreateConsXor(), SCIPcreateSymbreakCons(), SCIPgetConsCopy(), SCIPgetVarStrongbranchWithPropagation(), SCIPparseCons(), SCIPselectVarStrongBranching(), SCIPsetConsPropagated(), solveNode(), and startProbing().
* result = SCIP_DIDNOTRUN |
Definition at line 471 of file heur_randrounding.c.