prop_probing.h File Reference

Detailed Description

probing propagator

Author

Tobias Achterberg

Definition in file prop_probing.h.

#include "scip/scip.h"

Go to the source code of this file.

Functions
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)

Function Documentation

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