prop_probing.c File Reference

Detailed Description

probing propagator

Author

Tobias Achterberg

Matthias Miltenberger

Michael Winkler

Definition in file prop_probing.c.

#include <assert.h>
#include <string.h>
#include "scip/prop_probing.h"

Go to the source code of this file.

Macros
#define	PROP_NAME   "probing"
#define	PROP_DESC   "probing propagator on binary variables"
#define	PROP_TIMING   SCIP_PROPTIMING_AFTERLPLOOP
#define	PROP_PRIORITY   -100000
#define	PROP_FREQ   -1
#define	PROP_DELAY   TRUE
#define	PROP_PRESOL_PRIORITY   -100000
#define	PROP_PRESOL_DELAY   TRUE
#define	PROP_PRESOL_MAXROUNDS   -1
#define	MAXDNOM   10000LL
#define	DEFAULT_MAXRUNS   1
#define	DEFAULT_PROPROUNDS   -1
#define	DEFAULT_MAXFIXINGS   25
#define	DEFAULT_MAXUSELESS   1000
#define	DEFAULT_MAXTOTALUSELESS   50
#define	DEFAULT_MAXSUMUSELESS   0
#define	DEFAULT_MAXDEPTH   -1

Functions
static void	initPropdata (SCIP_PROPDATA *propdata)
static SCIP_RETCODE	freeSortedvars (SCIP *scip, SCIP_PROPDATA *propdata)
static SCIP_RETCODE	sortVariables (SCIP *scip, SCIP_PROPDATA *propdata, SCIP_VAR **vars, int nvars, int firstidx)
static SCIP_RETCODE	applyProbing (SCIP *scip, SCIP_PROPDATA *propdata, SCIP_VAR **vars, int nvars, int nbinvars, int *startidx, int *nfixedvars, int *naggrvars, int *nchgbds, int oldnfixedvars, int oldnaggrvars, SCIP_Bool *delay, SCIP_Bool *cutoff)
static	SCIP_DECL_PROPCOPY (propCopyProbing)
static	SCIP_DECL_PROPFREE (propFreeProbing)
static	SCIP_DECL_PROPINIT (propInitProbing)
static	SCIP_DECL_PROPEXIT (propExitProbing)
static	SCIP_DECL_PROPINITPRE (propInitpreProbing)
static	SCIP_DECL_PROPEXITPRE (propExitpreProbing)
static	SCIP_DECL_PROPINITSOL (propInitsolProbing)
static	SCIP_DECL_PROPPRESOL (propPresolProbing)
static	SCIP_DECL_PROPEXEC (propExecProbing)
static	SCIP_DECL_PROPRESPROP (propRespropProbing)
SCIP_RETCODE	SCIPincludePropProbing (SCIP *scip)
SCIP_RETCODE	SCIPapplyProbingVar (SCIP *scip, SCIP_VAR **vars, int nvars, int probingpos, SCIP_BOUNDTYPE boundtype, SCIP_Real bound, int maxproprounds, SCIP_Real *impllbs, SCIP_Real *implubs, SCIP_Real *proplbs, SCIP_Real *propubs, SCIP_Bool *cutoff)
SCIP_RETCODE	SCIPanalyzeDeductionsProbing (SCIP *scip, SCIP_VAR *probingvar, SCIP_Real leftub, SCIP_Real rightlb, int nvars, SCIP_VAR **vars, SCIP_Real *leftimpllbs, SCIP_Real *leftimplubs, SCIP_Real *leftproplbs, SCIP_Real *leftpropubs, SCIP_Real *rightimpllbs, SCIP_Real *rightimplubs, SCIP_Real *rightproplbs, SCIP_Real *rightpropubs, int *nfixedvars, int *naggrvars, int *nimplications, int *nchgbds, SCIP_Bool *cutoff)

Macro Definition Documentation

#define PROP_NAME   "probing"

Definition at line 31 of file prop_probing.c.

Referenced by SCIP_DECL_PROPCOPY(), and SCIPincludePropProbing().

#define PROP_DESC   "probing propagator on binary variables"

Definition at line 32 of file prop_probing.c.

Referenced by SCIPincludePropProbing().

#define PROP_TIMING   SCIP_PROPTIMING_AFTERLPLOOP

Definition at line 33 of file prop_probing.c.

Referenced by SCIPincludePropProbing().

#define PROP_PRIORITY   -100000

propagation priority

Definition at line 34 of file prop_probing.c.

Referenced by SCIPincludePropProbing().

#define PROP_FREQ   -1

propagation frequency

Definition at line 35 of file prop_probing.c.

Referenced by SCIPincludePropProbing().

#define PROP_DELAY   TRUE

should propagation method be delayed, if other propagators found reductions?

Definition at line 36 of file prop_probing.c.

Referenced by SCIPincludePropProbing().

#define PROP_PRESOL_PRIORITY   -100000

priority of the presolving method (>= 0: before, < 0: after constraint handlers); combined with presolvers

Definition at line 38 of file prop_probing.c.

Referenced by SCIPincludePropProbing().

#define PROP_PRESOL_DELAY   TRUE

should presolving be delay, if other presolvers found reductions?

Definition at line 39 of file prop_probing.c.

Referenced by SCIPincludePropProbing().

#define PROP_PRESOL_MAXROUNDS   -1

maximal number of presolving rounds the presolver participates in (-1: no limit)

Definition at line 40 of file prop_probing.c.

Referenced by SCIPincludePropProbing().

#define MAXDNOM   10000LL

maximal denominator for simple rational fixed values

Definition at line 42 of file prop_probing.c.

Referenced by SCIPanalyzeDeductionsProbing().

#define DEFAULT_MAXRUNS   1

maximal number of runs, probing participates in (-1: no limit)

Definition at line 55 of file prop_probing.c.

Referenced by SCIPincludePropProbing().

#define DEFAULT_PROPROUNDS   -1

maximal number of propagation rounds in probing subproblems

Definition at line 56 of file prop_probing.c.

Referenced by SCIPincludePropProbing().

#define DEFAULT_MAXFIXINGS   25

maximal number of fixings found, until probing is interrupted (0: don't interrupt)

Definition at line 57 of file prop_probing.c.

Referenced by SCIPincludePropProbing().

#define DEFAULT_MAXUSELESS   1000

maximal number of successive probings without fixings, until probing is aborted (0: don't abort)

Definition at line 59 of file prop_probing.c.

Referenced by SCIPincludePropProbing().

#define DEFAULT_MAXTOTALUSELESS   50

maximal number of successive probings without fixings, bound changes, and implications, until probing is aborted (0: don't abort)

Definition at line 61 of file prop_probing.c.

Referenced by SCIPincludePropProbing().

#define DEFAULT_MAXSUMUSELESS   0

maximal number of probings without fixings, until probing is aborted (0: don't abort)

Definition at line 63 of file prop_probing.c.

Referenced by SCIPincludePropProbing().

#define DEFAULT_MAXDEPTH   -1

maximal depth until propagation is executed(-1: no limit)

Definition at line 65 of file prop_probing.c.

Referenced by SCIPincludePropProbing().

Function Documentation

static void initPropdata ( SCIP_PROPDATA *  propdata )

static

initializes the propagator data

Parameters

propdata

propagator data

Definition at line 108 of file prop_probing.c.

References NULL.

Referenced by SCIP_DECL_PROPINIT(), and SCIPincludePropProbing().

static SCIP_RETCODE freeSortedvars ( SCIP *  scip, SCIP_PROPDATA *  propdata  )

static

frees the sorted vars array

Parameters

scip	SCIP data structure
propdata	propagator data

Definition at line 133 of file prop_probing.c.

References NULL, SCIP_CALL, SCIP_OKAY, SCIPfreeMemoryArray, SCIPfreeMemoryArrayNull, and SCIPreleaseVar().

Referenced by SCIP_DECL_PROPEXIT(), and SCIP_DECL_PROPEXITPRE().

static SCIP_RETCODE sortVariables ( SCIP *  scip, SCIP_PROPDATA *  propdata, SCIP_VAR **  vars, int  nvars, int  firstidx  )

static

sorts the binary variables starting with the given index by rounding locks and implications

Parameters

scip	SCIP data structure
propdata	propagator data
vars	problem variables to be sorted
nvars	number of problem variables to be sorted
firstidx	first index that should be subject to sorting

Definition at line 162 of file prop_probing.c.

References FALSE, MAX, MIN, NULL, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPdebugMessage, SCIPfreeBufferArray, SCIPgetNOrigVars(), SCIPinfinity(), SCIPsortDownRealPtr(), SCIPvarGetIndex(), SCIPvarGetNCliques(), SCIPvarGetNImpls(), SCIPvarGetNLocksDown(), SCIPvarGetNLocksUp(), SCIPvarIsActive(), SCIPvarIsBinary(), and TRUE.

Referenced by applyProbing(), SCIP_DECL_PROPEXEC(), and SCIP_DECL_PROPPRESOL().

static SCIP_RETCODE applyProbing ( SCIP *  scip, SCIP_PROPDATA *  propdata, SCIP_VAR **  vars, int  nvars, int  nbinvars, int *  startidx, int *  nfixedvars, int *  naggrvars, int *  nchgbds, int  oldnfixedvars, int  oldnaggrvars, SCIP_Bool *  delay, SCIP_Bool *  cutoff  )

static

the main probing loop

Parameters

scip	SCIP data structure
propdata	propagator data
vars	problem variables
nvars	number of problem variables
nbinvars	number of binary variables
startidx	pointer to store starting variable index of next call
nfixedvars	pointer to store number of fixed variables
naggrvars	pointer to store number of aggregated variables
nchgbds	pointer to store number of changed bounds
oldnfixedvars	number of previously fixed variables
oldnaggrvars	number of previously aggregated variables
delay	pointer to store whether propagator should be delayed
cutoff	pointer to store whether cutoff occured

Definition at line 329 of file prop_probing.c.

References FALSE, MAX, NULL, SCIP_Bool, SCIP_BOUNDTYPE_LOWER, SCIP_BOUNDTYPE_UPPER, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIP_STAGE_PRESOLVING, SCIP_STAGE_SOLVING, SCIP_VERBLEVEL_FULL, SCIP_VERBLEVEL_HIGH, SCIPallocBufferArray, SCIPanalyzeDeductionsProbing(), SCIPapplyProbingVar(), SCIPcaptureVar(), SCIPdebugMessage, SCIPduplicateMemoryArray, SCIPfixVar(), SCIPfreeBufferArray, SCIPfreeMemoryArray, SCIPgetCurrentNode(), SCIPgetNBinVars(), SCIPgetNImplVars(), SCIPgetNIntVars(), SCIPgetNVars(), SCIPgetSolvingTime(), SCIPgetStage(), SCIPgetVars(), SCIPisStopped(), SCIPnodeGetDepth(), SCIPreallocBufferArray, SCIPreleaseVar(), SCIPswapPointers(), SCIPtightenVarLb(), SCIPtightenVarUb(), SCIPvarGetIndex(), SCIPvarGetLbLocal(), SCIPvarGetName(), SCIPvarGetNLocksDown(), SCIPvarGetNLocksUp(), SCIPvarGetUbLocal(), SCIPvarIsActive(), SCIPvarIsBinary(), SCIPvarIsDeleted(), SCIPverbMessage(), sortVariables(), and TRUE.

Referenced by SCIP_DECL_PROPEXEC(), and SCIP_DECL_PROPPRESOL().

static SCIP_DECL_PROPCOPY ( propCopyProbing  )

static

copy method for constraint handler plugins (called when SCIP copies plugins)

Definition at line 706 of file prop_probing.c.

References NULL, PROP_NAME, SCIP_CALL, SCIP_OKAY, SCIPincludePropProbing(), and SCIPpropGetName().

static SCIP_DECL_PROPFREE ( propFreeProbing  )

static

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

Definition at line 721 of file prop_probing.c.

References NULL, SCIP_OKAY, SCIPfreeMemory, SCIPpropGetData(), and SCIPpropSetData().

static SCIP_DECL_PROPINIT ( propInitProbing  )

static

initialization method of propagator (called after problem was transformed)

Definition at line 741 of file prop_probing.c.

References initPropdata(), NULL, SCIP_OKAY, and SCIPpropGetData().

static SCIP_DECL_PROPEXIT ( propExitProbing  )

static

deinitialization method of propagator (called before transformed problem is freed)

Definition at line 756 of file prop_probing.c.

References freeSortedvars(), NULL, SCIP_CALL, SCIP_OKAY, and SCIPpropGetData().

static SCIP_DECL_PROPINITPRE ( propInitpreProbing  )

static

presolving initialization method of propagator (called when presolving is about to begin)

Definition at line 774 of file prop_probing.c.

References NULL, SCIP_OKAY, and SCIPpropGetData().

static SCIP_DECL_PROPEXITPRE ( propExitpreProbing  )

static

presolving deinitialization method of propagator (called after presolving has been finished)

Definition at line 789 of file prop_probing.c.

References freeSortedvars(), NULL, SCIP_CALL, SCIP_OKAY, SCIPgetNRuns(), and SCIPpropGetData().

static SCIP_DECL_PROPINITSOL ( propInitsolProbing  )

static

solving process initialization method of propagator (called when branch and bound process is about to begin)

Definition at line 811 of file prop_probing.c.

References NULL, SCIP_OKAY, and SCIPpropGetData().

static SCIP_DECL_PROPPRESOL ( propPresolProbing  )

static

presolve method of propagator

Definition at line 836 of file prop_probing.c.

References applyProbing(), BMSclearMemoryArray, NULL, SCIP_Bool, SCIP_CALL, SCIP_CUTOFF, SCIP_DELAYED, SCIP_DIDNOTFIND, SCIP_DIDNOTRUN, SCIP_OKAY, SCIP_SUCCESS, SCIPcaptureVar(), SCIPdebugMessage, SCIPduplicateMemoryArray, SCIPgetNBinVars(), SCIPgetNImplVars(), SCIPgetNIntVars(), SCIPgetNRuns(), SCIPgetNTotalVars(), SCIPgetNVars(), SCIPgetVars(), SCIPpropGetData(), SCIPpropGetTime(), SCIPreallocMemoryArray, SCIPswapPointers(), SCIPvarIsBinary(), and sortVariables().

static SCIP_DECL_PROPEXEC ( propExecProbing  )

static

execution method of propagator

Definition at line 965 of file prop_probing.c.

References applyProbing(), BMSclearMemoryArray, NULL, SCIP_Bool, SCIP_CALL, SCIP_CUTOFF, SCIP_DIDNOTFIND, SCIP_DIDNOTRUN, SCIP_LPSOLSTAT_OPTIMAL, SCIP_OKAY, SCIP_REDUCEDDOM, SCIPallocBufferArray, SCIPdebugMessage, SCIPfreeBufferArray, SCIPgetCurrentNode(), SCIPgetDepth(), SCIPgetLPBranchCands(), SCIPgetLPSolstat(), SCIPgetNTotalVars(), SCIPgetProbName(), SCIPinProbing(), SCIPnodeGetNumber(), SCIPpropGetData(), SCIPreallocMemoryArray, SCIPvarGetLbLocal(), SCIPvarGetUbLocal(), SCIPvarIsBinary(), and sortVariables().

static SCIP_DECL_PROPRESPROP ( propRespropProbing  )

static

propagation conflict resolving method of propagator

Definition at line 1091 of file prop_probing.c.

References SCIP_DIDNOTRUN, and SCIP_OKAY.

SCIP_RETCODE SCIPincludePropProbing

(

SCIP *

scip

)

creates the probing propagator and includes it in SCIP

Parameters

scip	SCIP data structure

Definition at line 1104 of file prop_probing.c.

References DEFAULT_MAXDEPTH, DEFAULT_MAXFIXINGS, DEFAULT_MAXRUNS, DEFAULT_MAXSUMUSELESS, DEFAULT_MAXTOTALUSELESS, DEFAULT_MAXUSELESS, DEFAULT_PROPROUNDS, FALSE, initPropdata(), NULL, PROP_DELAY, PROP_DESC, PROP_FREQ, PROP_NAME, PROP_PRESOL_DELAY, PROP_PRESOL_MAXROUNDS, PROP_PRESOL_PRIORITY, PROP_PRIORITY, PROP_TIMING, SCIP_CALL, SCIP_OKAY, SCIPaddIntParam(), SCIPallocMemory, SCIPincludePropBasic(), SCIPsetPropCopy(), SCIPsetPropExit(), SCIPsetPropExitpre(), SCIPsetPropFree(), SCIPsetPropInit(), SCIPsetPropInitpre(), SCIPsetPropInitsol(), SCIPsetPropPresol(), SCIPsetPropResprop(), and TRUE.

Referenced by SCIP_DECL_PROPCOPY(), and SCIPincludeDefaultPlugins().

SCIP_RETCODE SCIPapplyProbingVar	(	SCIP *	scip,
		SCIP_VAR **	vars,
		int	nvars,
		int	probingpos,
		SCIP_BOUNDTYPE	boundtype,
		SCIP_Real	bound,
		int	maxproprounds,
		SCIP_Real *	impllbs,
		SCIP_Real *	implubs,
		SCIP_Real *	proplbs,
		SCIP_Real *	propubs,
		SCIP_Bool *	cutoff
	)

applies and evaluates probing of a single variable in the given direction and bound

Parameters

scip	SCIP data structure
vars	problem variables
nvars	number of problem variables
probingpos	variable number to apply probing on
boundtype	which bound should be changed
bound	which bound should be set
maxproprounds	maximal number of propagation rounds (-1: no limit, 0: parameter settings)
impllbs	array to store lower bounds after applying implications and cliques
implubs	array to store upper bounds after applying implications and cliques
proplbs	array to store lower bounds after full propagation
propubs	array to store upper bounds after full propagation
cutoff	pointer to store whether the probing direction is infeasible

Definition at line 1168 of file prop_probing.c.

References FALSE, NULL, SCIP_BOUNDTYPE_LOWER, SCIP_BOUNDTYPE_UPPER, SCIP_CALL, SCIP_OKAY, SCIPchgVarLbProbing(), SCIPchgVarUbProbing(), SCIPdebugMessage, SCIPenableVarHistory(), SCIPendProbing(), SCIPisGE(), SCIPisGT(), SCIPisLE(), SCIPisLT(), SCIPpropagateProbing(), SCIPpropagateProbingImplications(), SCIPstartProbing(), SCIPvarGetLbGlobal(), SCIPvarGetLbLocal(), SCIPvarGetName(), SCIPvarGetNCliques(), SCIPvarGetNImpls(), SCIPvarGetNLocksDown(), SCIPvarGetNLocksUp(), SCIPvarGetUbGlobal(), SCIPvarGetUbLocal(), and TRUE.

Referenced by applyProbing(), and applyProbingVar().

SCIP_RETCODE SCIPanalyzeDeductionsProbing	(	SCIP *	scip,
		SCIP_VAR *	probingvar,
		SCIP_Real	leftub,
		SCIP_Real	rightlb,
		int	nvars,
		SCIP_VAR **	vars,
		SCIP_Real *	leftimpllbs,
		SCIP_Real *	leftimplubs,
		SCIP_Real *	leftproplbs,
		SCIP_Real *	leftpropubs,
		SCIP_Real *	rightimpllbs,
		SCIP_Real *	rightimplubs,
		SCIP_Real *	rightproplbs,
		SCIP_Real *	rightpropubs,
		int *	nfixedvars,
		int *	naggrvars,
		int *	nimplications,
		int *	nchgbds,
		SCIP_Bool *	cutoff
	)

analyses boundchanges resulting from probing on a variable and performs deduced fixations, aggregations, and domain tightenings Given a variable probingvar with domain [l,u] and bound tightening results from reducing the domain once to [l,leftub] and once to [rightlb,u], the method computes and applies resulting variable fixations, aggregations, implications, and bound changes. Variable probingvar does not need to be binary. The whole domain of probingvar need to be covered by the left and right branches, i.e., we assume leftub >= rightlb for continuous variables or floor(leftub) >= ceil(rightlb)-1 for discrete variables. Bounds after applying implications and cliques do not need to be provided, but if they are omitted and probingvar is a binary variable, then already existing implications may be added.

Parameters

scip	SCIP data structure
probingvar	the probing variable
leftub	upper bound of probing variable in left branch
rightlb	lower bound of probing variable in right branch
nvars	number of variables which bound changes should be analyzed
vars	variables which bound changes should be analyzed
leftimpllbs	lower bounds after applying implications and cliques in left branch, or NULL
leftimplubs	upper bounds after applying implications and cliques in left branch, or NULL
leftproplbs	lower bounds after applying domain propagation in left branch
leftpropubs	upper bounds after applying domain propagation in left branch
rightimpllbs	lower bounds after applying implications and cliques in right branch, or NULL
rightimplubs	upper bounds after applying implications and cliques in right branch, or NULL
rightproplbs	lower bounds after applying domain propagation in right branch
rightpropubs	upper bounds after applying domain propagation in right branch
nfixedvars	pointer to counter which is increased by the number of deduced variable fixations
naggrvars	pointer to counter which is increased by the number of deduced variable aggregations
nimplications	pointer to counter which is increased by the number of deduced implications
nchgbds	pointer to counter which is increased by the number of deduced bound tightenings
cutoff	buffer to store whether a cutoff is detected

Definition at line 1290 of file prop_probing.c.

References FALSE, MAX, MAXDNOM, MIN, NULL, SCIP_Bool, SCIP_BOUNDTYPE_LOWER, SCIP_BOUNDTYPE_UPPER, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIP_STAGE_PRESOLVING, SCIP_STAGE_SOLVING, SCIP_VARTYPE_BINARY, SCIP_VARTYPE_CONTINUOUS, SCIPaddVarImplication(), SCIPaddVarVlb(), SCIPaddVarVub(), SCIPaggregateVars(), SCIPceil(), SCIPdebugMessage, SCIPepsilon(), SCIPfixVar(), SCIPfloor(), SCIPgetCurrentNode(), SCIPgetStage(), SCIPisEQ(), SCIPisGE(), SCIPisLbBetter(), SCIPisLE(), SCIPisUbBetter(), SCIPisZero(), SCIPnodeGetDepth(), SCIPselectSimpleValue(), SCIPtightenVarLb(), SCIPtightenVarUb(), SCIPvarGetLbLocal(), SCIPvarGetName(), SCIPvarGetNLocksDown(), SCIPvarGetNLocksUp(), SCIPvarGetType(), SCIPvarGetUbLocal(), SCIPvarIsBinary(), and TRUE.

Referenced by applyProbing().