Detailed Description

methods and files provided by the default propagators of SCIP

A detailed description what a propagator does and how to add a propagator to SCIP can be found here.

Modules
	Inclusion methods
	methods to include specific propagators into SCIP

Functions
SCIP_RETCODE	SCIPgenVBoundAdd (SCIP scip, SCIP_PROP genvboundprop, SCIP_VAR *vars, SCIP_VAR var, SCIP_Real *coefs, int ncoefs, SCIP_Real coefprimalbound, SCIP_Real constant, SCIP_BOUNDTYPE boundtype)

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)

SCIP_RETCODE	SCIPpropagateCutoffboundVar (SCIP scip, SCIP_PROP prop, SCIP_VAR var, SCIP_Real cutoffbound, SCIP_Real pseudoobjval, SCIP_Bool tightened)

SCIP_RETCODE	SCIPpropSyncAddBndchg (SCIP scip, SCIP_PROP prop, SCIP_VAR *var, SCIP_Real val, SCIP_BOUNDTYPE bndtype)

SCIP_Longint	SCIPpropSyncGetNTightenedBnds (SCIP_PROP *prop)

SCIP_Longint	SCIPpropSyncGetNTightenedIntBnds (SCIP_PROP *prop)

SCIP_Bool	SCIPisPropagatedVbounds (SCIP *scip)

SCIP_RETCODE	SCIPexecPropVbounds (SCIP scip, SCIP_Bool force, SCIP_RESULT result)

Files
file	prop_dualfix.h
	fixing roundable variables to best bound

file	prop_genvbounds.c
	generalized variable bounds propagator

file	prop_genvbounds.h
	generalized variable bounds propagator

file	prop_nlobbt.h
	nonlinear OBBT propagator

file	prop_obbt.c
	optimization-based bound tightening propagator

file	prop_obbt.h
	optimization-based bound tightening propagator

file	prop_probing.h
	probing propagator

file	prop_pseudoobj.h
	Pseudo objective propagator.

file	prop_redcost.h
	propagator using the LP reduced cost and the cutoff bound

file	prop_rootredcost.h
	reduced cost strengthening using root node reduced costs and the cutoff bound

file	prop_sync.h
	propagator for applying global bound changes that were communicated by other concurrent solvers

file	prop_vbounds.h
	variable upper and lower bound propagator

Function Documentation

◆ SCIPgenVBoundAdd()

SCIP_RETCODE SCIPgenVBoundAdd	(	SCIP *	scip,
		SCIP_PROP *	genvboundprop,
		SCIP_VAR **	vars,
		SCIP_VAR *	var,
		SCIP_Real *	coefs,
		int	ncoefs,
		SCIP_Real	coefcutoffbound,
		SCIP_Real	constant,
		SCIP_BOUNDTYPE	boundtype
	)

adds a generalized variable bound to the genvbounds propagator; if there is already a genvbound for the bound "boundtype" of variable "var", it will be replaced

Parameters

scip	SCIP data structure
genvboundprop	genvbound propagator
vars	array of RHSs variables
var	LHSs variable
coefs	array of coefficients for the RHSs variables
ncoefs	size of coefs array
coefcutoffbound	nonpositive value of the cutoff bounds multiplier
constant	constant term
boundtype	type of bound provided by the genvbound

Definition at line 2005 of file prop_genvbounds.c.

References addNewGenVBound(), GenVBound::boundtype, GenVBound::coefs, GenVBound::coefssize, GenVBound::constant, GenVBound::cutoffcoef, FALSE, getGenVBound(), initPropdata(), GenVBound::ncoefs, NULL, PROP_NAME, SCIP_Bool, SCIP_CALL, SCIP_DECL_PROPCOPY(), SCIP_INVALIDDATA, SCIP_OKAY, SCIPallocBlockMemory, SCIPcaptureVar(), SCIPdebug, SCIPdebugMsg, SCIPduplicateBlockMemoryArray, SCIPerrorMessage, SCIPfreeBlockMemoryArray, SCIPgetTransObjoffset(), SCIPgetTransObjscale(), SCIPisInfinity(), SCIPisNegative(), SCIPisPositive(), SCIPpropGetData(), SCIPpropGetName(), SCIPreallocBlockMemoryArray, SCIPreleaseVar(), GenVBound::var, and GenVBound::vars.

Referenced by addGenVBound(), and createConstraints().

◆ SCIPapplyProbingVar()

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 1177 of file prop_probing.c.

References FALSE, NULL, SCIP_BOUNDTYPE_LOWER, SCIP_BOUNDTYPE_UPPER, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPanalyzeDeductionsProbing(), SCIPchgVarLbProbing(), SCIPchgVarUbProbing(), SCIPdebugMsg, 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().

◆ SCIPanalyzeDeductionsProbing()

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 1301 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(), SCIPdebugMsg, 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(), and SCIPapplyProbingVar().

◆ SCIPpropagateCutoffboundVar()

SCIP_RETCODE SCIPpropagateCutoffboundVar	(	SCIP *	scip,
		SCIP_PROP *	prop,
		SCIP_VAR *	var,
		SCIP_Real	cutoffbound,
		SCIP_Real	pseudoobjval,
		SCIP_Bool *	tightened
	)

propagates the cutoff bound for the given variables

Parameters

scip	SCIP data structure
prop	propagator, or NULL
var	variables to propagate
cutoffbound	cutoff bound to use
pseudoobjval	pseudo objective value to use
tightened	pointer to if the domain was tightened

Definition at line 3772 of file prop_pseudoobj.c.

References propagateCutoffboundVar(), SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPvarGetObj(), and TRUE.

◆ SCIPpropSyncAddBndchg()

SCIP_RETCODE SCIPpropSyncAddBndchg	(	SCIP *	scip,
		SCIP_PROP *	prop,
		SCIP_VAR *	var,
		SCIP_Real	val,
		SCIP_BOUNDTYPE	bndtype
	)

adds a boundchange to the sync propagator

Parameters

scip	SCIP data structure
prop	sync propagator
var	variable for bound
val	value of bound
bndtype	type of bound

Definition at line 305 of file prop_sync.c.

References NULL, PROP_NAME, SCIP_CALL, SCIP_Longint, SCIP_OKAY, SCIPcalcMemGrowSize(), SCIPpropGetData(), SCIPpropGetName(), SCIPpropSetFreq(), SCIPpropSyncGetNTightenedBnds(), and SCIPreallocBlockMemoryArray.

Referenced by SCIPaddConcurrentBndchg(), and SCIPincludePropSync().

◆ SCIPpropSyncGetNTightenedBnds()

SCIP_Longint SCIPpropSyncGetNTightenedBnds ( SCIP_PROP * prop )

gives the total number of tightened bounds found by the sync propagator

Parameters

prop	sync propagator

Definition at line 345 of file prop_sync.c.

References NULL, SCIP_Longint, SCIPpropGetData(), and SCIPpropSyncGetNTightenedIntBnds().

Referenced by SCIPgetConcurrentNTightenedBnds(), and SCIPpropSyncAddBndchg().

◆ SCIPpropSyncGetNTightenedIntBnds()

SCIP_Longint SCIPpropSyncGetNTightenedIntBnds ( SCIP_PROP * prop )

gives the total number of tightened bounds for integer variables found by the sync propagator

Parameters

prop	sync propagator

Definition at line 360 of file prop_sync.c.

References NULL, and SCIPpropGetData().

Referenced by SCIPgetConcurrentNTightenedIntBnds(), and SCIPpropSyncGetNTightenedBnds().

◆ SCIPisPropagatedVbounds()

SCIP_Bool SCIPisPropagatedVbounds ( SCIP * scip )

returns TRUE if the propagator has the status that all variable lower and upper bounds are propagated

returns TRUE if the propagator has the status that all variable lower and upper bounds are propgated

Parameters

scip	SCIP data structure

Definition at line 2305 of file prop_vbounds.c.

References NULL, PROP_NAME, SCIPfindProp(), SCIPpqueueNElems(), and SCIPpropGetData().

◆ SCIPexecPropVbounds()

SCIP_RETCODE SCIPexecPropVbounds	(	SCIP *	scip,
		SCIP_Bool	force,
		SCIP_RESULT *	result
	)

performs propagation of variables lower and upper bounds

Parameters

scip	SCIP data structure
force	should domain changes for continuous variables be forced
result	pointer to store result

Definition at line 2322 of file prop_vbounds.c.

References NULL, PROP_NAME, propagateVbounds(), SCIP_CALL, SCIP_CUTOFF, SCIP_DIDNOTFIND, SCIP_DIDNOTRUN, SCIP_OKAY, SCIP_REDUCEDDOM, and SCIPfindProp().

SCIP

Detailed Description

Modules

Functions

Files

Function Documentation

◆ SCIPgenVBoundAdd()

◆ SCIPapplyProbingVar()

◆ SCIPanalyzeDeductionsProbing()

◆ SCIPpropagateCutoffboundVar()

◆ SCIPpropSyncAddBndchg()

◆ SCIPpropSyncGetNTightenedBnds()

◆ SCIPpropSyncGetNTightenedIntBnds()

◆ SCIPisPropagatedVbounds()

◆ SCIPexecPropVbounds()