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

Referenced by SCIPincludeHeurRandrounding().

◆ HEUR_DISPCHAR

#define HEUR_DISPCHAR SCIP_HEURDISPCHAR_ROUNDING

Definition at line 64 of file heur_randrounding.c.

Referenced by SCIPincludeHeurRandrounding().

◆ HEUR_PRIORITY

#define HEUR_PRIORITY -200

Definition at line 65 of file heur_randrounding.c.

Referenced by SCIPincludeHeurRandrounding().

◆ HEUR_FREQ

#define HEUR_FREQ 20

Definition at line 66 of file heur_randrounding.c.

Referenced by SCIPincludeHeurRandrounding().

◆ HEUR_FREQOFS

#define HEUR_FREQOFS 0

Definition at line 67 of file heur_randrounding.c.

Referenced by SCIPincludeHeurRandrounding().

◆ HEUR_MAXDEPTH

#define HEUR_MAXDEPTH -1

Definition at line 68 of file heur_randrounding.c.

Referenced by SCIPincludeHeurRandrounding().

◆ HEUR_TIMING

#define HEUR_TIMING SCIP_HEURTIMING_DURINGLPLOOP

Definition at line 69 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 70 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 72 of file heur_randrounding.c.

Referenced by SCIPincludeHeurRandrounding().

◆ DEFAULT_RANDSEED

#define DEFAULT_RANDSEED 23

default random seed

Definition at line 73 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 74 of file heur_randrounding.c.

Referenced by SCIPincludeHeurRandrounding().

◆ DEFAULT_MAXPROPROUNDS

#define DEFAULT_MAXPROPROUNDS 1

limit of rounds for each propagation call

Definition at line 77 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 78 of file heur_randrounding.c.

Referenced by SCIPincludeHeurRandrounding().

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

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 101 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 SCIP_RETCODE performLPRandRounding	(	SCIP *	scip,
		SCIP_HEURDATA *	heurdata,
		SCIP_HEURTIMING	heurtiming,
		SCIP_Bool	propagate,
		SCIP_RESULT *	result
	)

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