Detailed Description
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 | SCIP_DECL_HEURFREE (heurFreeRandrounding) |
static | SCIP_DECL_HEURINIT (heurInitRandrounding) |
static | SCIP_DECL_HEUREXIT (heurExitRandrounding) |
static | SCIP_DECL_HEURINITSOL (heurInitsolRandrounding) |
static | SCIP_DECL_HEUREXITSOL (heurExitsolRandrounding) |
static | SCIP_DECL_HEUREXEC (heurExecRandrounding) |
SCIP_RETCODE | SCIPincludeHeurRandrounding (SCIP *scip) |
Macro Definition Documentation
◆ HEUR_NAME
#define HEUR_NAME "randrounding" |
Definition at line 53 of file heur_randrounding.c.
Referenced by SCIP_DECL_HEURCOPY(), SCIP_DECL_HEUREXEC(), SCIP_DECL_HEUREXIT(), SCIP_DECL_HEURFREE(), SCIP_DECL_HEURINIT(), SCIP_DECL_HEURINITSOL(), and SCIPincludeHeurRandrounding().
◆ HEUR_DESC
#define HEUR_DESC "fast LP rounding heuristic" |
Definition at line 54 of file heur_randrounding.c.
Referenced by SCIPincludeHeurRandrounding().
◆ HEUR_DISPCHAR
#define HEUR_DISPCHAR SCIP_HEURDISPCHAR_ROUNDING |
Definition at line 55 of file heur_randrounding.c.
Referenced by SCIPincludeHeurRandrounding().
◆ HEUR_PRIORITY
#define HEUR_PRIORITY -200 |
Definition at line 56 of file heur_randrounding.c.
Referenced by SCIPincludeHeurRandrounding().
◆ HEUR_FREQ
#define HEUR_FREQ 20 |
Definition at line 57 of file heur_randrounding.c.
Referenced by SCIPincludeHeurRandrounding().
◆ HEUR_FREQOFS
#define HEUR_FREQOFS 0 |
Definition at line 58 of file heur_randrounding.c.
Referenced by SCIPincludeHeurRandrounding().
◆ HEUR_MAXDEPTH
#define HEUR_MAXDEPTH -1 |
Definition at line 59 of file heur_randrounding.c.
Referenced by SCIPincludeHeurRandrounding().
◆ HEUR_TIMING
#define HEUR_TIMING SCIP_HEURTIMING_DURINGLPLOOP |
Definition at line 60 of file heur_randrounding.c.
Referenced by SCIP_DECL_HEUREXITSOL(), and SCIPincludeHeurRandrounding().
◆ HEUR_USESSUBSCIP
#define HEUR_USESSUBSCIP FALSE |
does the heuristic use a secondary SCIP instance?
Definition at line 61 of file heur_randrounding.c.
Referenced by SCIPincludeHeurRandrounding().
◆ DEFAULT_ONCEPERNODE
#define DEFAULT_ONCEPERNODE FALSE |
should the heuristic only be called once per node?
Definition at line 63 of file heur_randrounding.c.
Referenced by SCIPincludeHeurRandrounding().
◆ DEFAULT_RANDSEED
#define DEFAULT_RANDSEED 23 |
default random seed
Definition at line 64 of file heur_randrounding.c.
Referenced by SCIP_DECL_HEURINIT().
◆ DEFAULT_USESIMPLEROUNDING
#define DEFAULT_USESIMPLEROUNDING FALSE |
should the heuristic apply the variable lock strategy of simple rounding, if possible?
Definition at line 65 of file heur_randrounding.c.
Referenced by SCIPincludeHeurRandrounding().
◆ DEFAULT_MAXPROPROUNDS
#define DEFAULT_MAXPROPROUNDS 1 |
limit of rounds for each propagation call
Definition at line 68 of file heur_randrounding.c.
Referenced by SCIPincludeHeurRandrounding().
◆ DEFAULT_PROPAGATEONLYROOT
#define DEFAULT_PROPAGATEONLYROOT TRUE |
should the probing part of the heuristic be applied exclusively at the root node
Definition at line 69 of file heur_randrounding.c.
Referenced by SCIPincludeHeurRandrounding().
Function Documentation
◆ performRandRounding()
|
static |
perform randomized rounding of the given solution. Domain propagation is optionally applied after every rounding step
- Parameters
-
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 92 of file heur_randrounding.c.
References FALSE, NULL, performLPRandRounding(), 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(), and TRUE.
Referenced by performLPRandRounding().
◆ performLPRandRounding()
|
static |
perform randomized LP-rounding
- Parameters
-
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 295 of file heur_randrounding.c.
References NULL, performRandRounding(), SCIP_CALL, SCIP_DECL_HEURCOPY(), SCIP_DIDNOTFIND, SCIP_HEURTIMING_DURINGPRICINGLOOP, SCIP_Longint, SCIP_LPSOLSTAT_OPTIMAL, SCIP_OKAY, SCIPdebugMsg, SCIPgetCutoffbound(), SCIPgetLPBranchCands(), SCIPgetLPObjval(), SCIPgetLPSolstat(), SCIPgetNLPs(), SCIPisGE(), and SCIPlinkLPSol().
Referenced by performRandRounding(), and SCIP_DECL_HEUREXEC().
◆ SCIP_DECL_HEURCOPY()
|
static |
copy method for primal heuristic plugins (called when SCIP copies plugins)
Definition at line 351 of file heur_randrounding.c.
References HEUR_NAME, NULL, SCIP_CALL, SCIP_DECL_HEURFREE(), SCIP_OKAY, SCIPheurGetName(), and SCIPincludeHeurRandrounding().
Referenced by performLPRandRounding().
◆ SCIP_DECL_HEURFREE()
|
static |
destructor of primal heuristic to free user data (called when SCIP is exiting)
Definition at line 365 of file heur_randrounding.c.
References HEUR_NAME, NULL, SCIP_DECL_HEURINIT(), SCIP_OKAY, SCIPfreeBlockMemory, SCIPheurGetData(), SCIPheurGetName(), and SCIPheurSetData().
Referenced by SCIP_DECL_HEURCOPY().
◆ SCIP_DECL_HEURINIT()
|
static |
initialization method of primal heuristic (called after problem was transformed)
Definition at line 384 of file heur_randrounding.c.
References DEFAULT_RANDSEED, HEUR_NAME, NULL, SCIP_CALL, SCIP_DECL_HEUREXIT(), SCIP_OKAY, SCIPcreateRandom(), SCIPcreateSol(), SCIPheurGetData(), SCIPheurGetName(), and TRUE.
Referenced by SCIP_DECL_HEURFREE().
◆ SCIP_DECL_HEUREXIT()
|
static |
deinitialization method of primal heuristic (called before transformed problem is freed)
Definition at line 405 of file heur_randrounding.c.
References HEUR_NAME, NULL, SCIP_CALL, SCIP_DECL_HEURINITSOL(), SCIP_OKAY, SCIPfreeRandom(), SCIPfreeSol(), SCIPheurGetData(), and SCIPheurGetName().
Referenced by SCIP_DECL_HEURINIT().
◆ SCIP_DECL_HEURINITSOL()
|
static |
solving process initialization method of primal heuristic (called when branch and bound process is about to begin)
Definition at line 424 of file heur_randrounding.c.
References HEUR_NAME, NULL, SCIP_DECL_HEUREXITSOL(), SCIP_HEURTIMING_AFTERLPNODE, SCIP_OKAY, SCIPheurGetData(), SCIPheurGetName(), and SCIPheurSetTimingmask().
Referenced by SCIP_DECL_HEUREXIT().
◆ SCIP_DECL_HEUREXITSOL()
|
static |
solving process deinitialization method of primal heuristic (called before branch and bound process data is freed)
Definition at line 444 of file heur_randrounding.c.
References HEUR_TIMING, SCIP_DECL_HEUREXEC(), SCIP_OKAY, and SCIPheurSetTimingmask().
Referenced by SCIP_DECL_HEURINITSOL().
◆ SCIP_DECL_HEUREXEC()
|
static |
execution method of primal heuristic
Definition at line 454 of file heur_randrounding.c.
References HEUR_NAME, NULL, performLPRandRounding(), SCIP_Bool, SCIP_CALL, SCIP_DIDNOTRUN, SCIP_LPSOLSTAT_OPTIMAL, SCIP_OKAY, SCIPgetCutoffbound(), SCIPgetDepth(), SCIPgetLPObjval(), SCIPgetLPSolstat(), SCIPgetNLPs(), SCIPhasCurrentNodeLP(), SCIPheurGetData(), SCIPheurGetName(), SCIPincludeHeurRandrounding(), and SCIPisGE().
Referenced by SCIP_DECL_HEUREXITSOL().