SCIP Doxygen Documentation
 
Loading...
Searching...
No Matches

Detailed Description

randomized LP rounding heuristic which also generates conflicts via an auxiliary probing tree

Author
Gregor Hendel

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
 

Macro Definition Documentation

◆ HEUR_NAME

#define HEUR_NAME   "randrounding"

Definition at line 62 of file heur_randrounding.c.

◆ HEUR_DESC

#define HEUR_DESC   "fast LP rounding heuristic"

Definition at line 63 of file heur_randrounding.c.

◆ HEUR_DISPCHAR

#define HEUR_DISPCHAR   SCIP_HEURDISPCHAR_ROUNDING

Definition at line 64 of file heur_randrounding.c.

◆ HEUR_PRIORITY

#define HEUR_PRIORITY   -200

Definition at line 65 of file heur_randrounding.c.

◆ HEUR_FREQ

#define HEUR_FREQ   20

Definition at line 66 of file heur_randrounding.c.

◆ HEUR_FREQOFS

#define HEUR_FREQOFS   0

Definition at line 67 of file heur_randrounding.c.

◆ HEUR_MAXDEPTH

#define HEUR_MAXDEPTH   -1

Definition at line 68 of file heur_randrounding.c.

◆ HEUR_TIMING

#define HEUR_TIMING   SCIP_HEURTIMING_DURINGLPLOOP

Definition at line 69 of file heur_randrounding.c.

◆ HEUR_USESSUBSCIP

#define HEUR_USESSUBSCIP   FALSE

does the heuristic use a secondary SCIP instance?

Definition at line 70 of file heur_randrounding.c.

◆ DEFAULT_ONCEPERNODE

#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().

◆ DEFAULT_RANDSEED

#define DEFAULT_RANDSEED   23

default random seed

Definition at line 73 of file heur_randrounding.c.

◆ DEFAULT_USESIMPLEROUNDING

#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.

◆ DEFAULT_MAXPROPROUNDS

#define DEFAULT_MAXPROPROUNDS   1

limit of rounds for each propagation call

Definition at line 76 of file heur_randrounding.c.

◆ DEFAULT_PROPAGATEONLYROOT

#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.

Function Documentation

◆ performRandRounding()

static SCIP_RETCODE performRandRounding ( SCIP * scip,
SCIP_HEURDATA * heurdata,
SCIP_SOL * sol,
SCIP_VAR ** cands,
int ncands,
SCIP_Bool propagate,
SCIP_RESULT * result )
static

◆ performLPRandRounding()

static SCIP_RETCODE performLPRandRounding ( SCIP * scip,
SCIP_HEURDATA * heurdata,
SCIP_HEURTIMING heurtiming,
SCIP_Bool propagate,
SCIP_RESULT * result )
static

perform randomized LP-rounding

Parameters
scipSCIP main data structure
heurdataheuristic data
heurtimingheuristic timing mask
propagateshould the heuristic apply SCIP's propagation?
resultpointer 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.

◆ SCIP_DECL_HEURCOPY()

static SCIP_DECL_HEURCOPY ( heurCopyRandrounding )
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() [1/6]

static assert ( heur ! = NULL)

destructor of primal heuristic to free user data (called when SCIP is exiting)

References NULL.

◆ assert() [2/6]

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.

◆ assert() [3/6]

assert ( scip ! = NULL)

References NULL.

◆ assert() [4/6]

assert ( heurdata ! = NULL)

References heurdata, and NULL.

◆ SCIPfreeBlockMemory()

SCIPfreeBlockMemory ( scip ,
& heurdata )

References heurdata.

◆ SCIPheurSetData()

SCIPheurSetData ( heur ,
NULL  )

References NULL.

◆ SCIPcreateSol()

SCIPcreateSol ( scip ,
&heurdata-> sol,
heur  )

References heurdata.

◆ SCIPcreateRandom()

SCIPcreateRandom ( scip ,
&heurdata-> randnumgen,
DEFAULT_RANDSEED ,
TRUE  )

◆ SCIPfreeSol()

SCIPfreeSol ( scip ,
&heurdata-> sol )

References heurdata.

◆ SCIPfreeRandom()

SCIPfreeRandom ( scip ,
&heurdata-> randnumgen )

References heurdata, and SCIP_OKAY.

◆ SCIP_DECL_HEURINITSOL()

static SCIP_DECL_HEURINITSOL ( heurInitsolRandrounding )
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().

◆ SCIP_DECL_HEUREXITSOL()

static SCIP_DECL_HEUREXITSOL ( heurExitsolRandrounding )
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() [5/6]

assert ( result ! = NULL)

References NULL, and result.

◆ assert() [6/6]

assert ( SCIPhasCurrentNodeLP(scip) )

◆ if()

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.

Variable Documentation

◆ heurdata

heurdata = SCIPheurGetData(heur)

Definition at line 382 of file heur_randrounding.c.

◆ SCIP_OKAY

return SCIP_OKAY

Definition at line 387 of file heur_randrounding.c.

◆ lastlp

heurdata lastlp = -1

Definition at line 402 of file heur_randrounding.c.

◆ propagate

SCIP_Bool propagate
Initial value:
{
struct SCIP_HeurData SCIP_HEURDATA
Definition type_heur.h:77

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

* result = SCIP_DIDNOTRUN

Definition at line 471 of file heur_randrounding.c.