Scippy

SCIP

Solving Constraint Integer Programs

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
scipSCIP data structure

Definition at line 1117 of file prop_probing.c.

Referenced by 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
scipSCIP data structure
varsproblem variables
nvarsnumber of problem variables
probingposvariable number to apply probing on
boundtypewhich bound should be changed
boundwhich bound should be set
maxproproundsmaximal number of propagation rounds (-1: no limit, 0: parameter settings)
impllbsarray to store lower bounds after applying implications and cliques
implubsarray to store upper bounds after applying implications and cliques
proplbsarray to store lower bounds after full propagation
propubsarray to store upper bounds after full propagation
cutoffpointer to store whether the probing direction is infeasible

Definition at line 1181 of file prop_probing.c.

References FALSE, NULL, SCIP_BOUNDTYPE_LOWER, SCIP_BOUNDTYPE_UPPER, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPanalyzeDeductionsProbing(), 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
scipSCIP data structure
probingvarthe probing variable
leftubupper bound of probing variable in left branch
rightlblower bound of probing variable in right branch
nvarsnumber of variables which bound changes should be analyzed
varsvariables which bound changes should be analyzed
leftimpllbslower bounds after applying implications and cliques in left branch, or NULL
leftimplubsupper bounds after applying implications and cliques in left branch, or NULL
leftproplbslower bounds after applying domain propagation in left branch
leftpropubsupper bounds after applying domain propagation in left branch
rightimpllbslower bounds after applying implications and cliques in right branch, or NULL
rightimplubsupper bounds after applying implications and cliques in right branch, or NULL
rightproplbslower bounds after applying domain propagation in right branch
rightpropubsupper bounds after applying domain propagation in right branch
nfixedvarspointer to counter which is increased by the number of deduced variable fixations
naggrvarspointer to counter which is increased by the number of deduced variable aggregations
nimplicationspointer to counter which is increased by the number of deduced implications
nchgbdspointer to counter which is increased by the number of deduced bound tightenings
cutoffbuffer to store whether a cutoff is detected

Definition at line 1305 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(), and SCIPapplyProbingVar().