Scippy

SCIP

Solving Constraint Integer Programs

heur_randrounding.c File Reference

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 <assert.h>
#include <string.h>
#include "scip/heur_randrounding.h"

Go to the source code of this file.

Macros

#define HEUR_NAME   "randrounding"
 
#define HEUR_DESC   "fast LP rounding heuristic"
 
#define HEUR_DISPCHAR   'G'
 
#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   14081986
 
#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

#define HEUR_DESC   "fast LP rounding heuristic"

Definition at line 37 of file heur_randrounding.c.

Referenced by SCIPincludeHeurRandrounding().

#define HEUR_DISPCHAR   'G'

Definition at line 38 of file heur_randrounding.c.

Referenced by SCIPincludeHeurRandrounding().

#define HEUR_PRIORITY   -200

Definition at line 39 of file heur_randrounding.c.

Referenced by SCIPincludeHeurRandrounding().

#define HEUR_FREQ   20

Definition at line 40 of file heur_randrounding.c.

Referenced by SCIPincludeHeurRandrounding().

#define HEUR_FREQOFS   0

Definition at line 41 of file heur_randrounding.c.

Referenced by SCIPincludeHeurRandrounding().

#define HEUR_MAXDEPTH   -1

Definition at line 42 of file heur_randrounding.c.

Referenced by SCIPincludeHeurRandrounding().

#define HEUR_TIMING   SCIP_HEURTIMING_DURINGLPLOOP

Definition at line 43 of file heur_randrounding.c.

Referenced by SCIP_DECL_HEUREXITSOL(), and SCIPincludeHeurRandrounding().

#define HEUR_USESSUBSCIP   FALSE

does the heuristic use a secondary SCIP instance?

Definition at line 44 of file heur_randrounding.c.

Referenced by SCIPincludeHeurRandrounding().

#define DEFAULT_ONCEPERNODE   FALSE

should the heuristic only be called once per node?

Definition at line 46 of file heur_randrounding.c.

Referenced by SCIPincludeHeurRandrounding().

#define DEFAULT_RANDSEED   14081986

default random seed

Definition at line 47 of file heur_randrounding.c.

Referenced by SCIP_DECL_HEURINIT().

#define DEFAULT_USESIMPLEROUNDING   FALSE

should the heuristic apply the variable lock strategy of simple rounding, if possible?

Definition at line 48 of file heur_randrounding.c.

Referenced by SCIPincludeHeurRandrounding().

#define DEFAULT_MAXPROPROUNDS   1

limit of rounds for each propagation call

Definition at line 51 of file heur_randrounding.c.

Referenced by SCIPincludeHeurRandrounding().

#define DEFAULT_PROPAGATEONLYROOT   TRUE

should the probing part of the heuristic be applied exclusively at the root node

Definition at line 52 of file heur_randrounding.c.

Referenced by SCIPincludeHeurRandrounding().

Function Documentation

static SCIP_RETCODE performRandRounding ( SCIP scip,
SCIP_HEURDATA heurdata,
SCIP_SOL sol,
SCIP_VAR **  cands,
int  ncands,
SCIP_Bool  propagate,
SCIP_RESULT result 
)
static
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 278 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, SCIPdebugMessage, SCIPgetCutoffbound(), SCIPgetLPBranchCands(), SCIPgetLPObjval(), SCIPgetLPSolstat(), SCIPgetNLPs(), SCIPisGE(), and SCIPlinkLPSol().

Referenced by performRandRounding(), and SCIP_DECL_HEUREXEC().

static SCIP_DECL_HEURCOPY ( heurCopyRandrounding  )
static

copy method for primal heuristic plugins (called when SCIP copies plugins)

Definition at line 335 of file heur_randrounding.c.

References HEUR_NAME, NULL, SCIP_CALL, SCIP_DECL_HEURFREE(), SCIP_OKAY, SCIPheurGetName(), and SCIPincludeHeurRandrounding().

Referenced by performLPRandRounding().

static SCIP_DECL_HEURFREE ( heurFreeRandrounding  )
static

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

Definition at line 349 of file heur_randrounding.c.

References HEUR_NAME, NULL, SCIP_DECL_HEURINIT(), SCIP_OKAY, SCIPfreeMemory, SCIPheurGetData(), SCIPheurGetName(), and SCIPheurSetData().

Referenced by SCIP_DECL_HEURCOPY().

static SCIP_DECL_HEURINIT ( heurInitRandrounding  )
static

initialization method of primal heuristic (called after problem was transformed)

Definition at line 368 of file heur_randrounding.c.

References DEFAULT_RANDSEED, HEUR_NAME, NULL, SCIP_CALL, SCIP_DECL_HEUREXIT(), SCIP_OKAY, SCIPcreateSol(), SCIPheurGetData(), and SCIPheurGetName().

Referenced by SCIP_DECL_HEURFREE().

static SCIP_DECL_HEUREXIT ( heurExitRandrounding  )
static

deinitialization method of primal heuristic (called before transformed problem is freed)

Definition at line 386 of file heur_randrounding.c.

References HEUR_NAME, NULL, SCIP_CALL, SCIP_DECL_HEURINITSOL(), SCIP_OKAY, SCIPfreeSol(), SCIPheurGetData(), and SCIPheurGetName().

Referenced by SCIP_DECL_HEURINIT().

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

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 422 of file heur_randrounding.c.

References HEUR_TIMING, SCIP_DECL_HEUREXEC(), SCIP_OKAY, and SCIPheurSetTimingmask().

Referenced by SCIP_DECL_HEURINITSOL().