Scippy

SCIP

Solving Constraint Integer Programs

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
scipSCIP data structure
genvboundpropgenvbound propagator
varsarray of RHSs variables
varLHSs variable
coefsarray of coefficients for the RHSs variables
ncoefssize of coefs array
coefcutoffboundnonpositive value of the cutoff bounds multiplier
constantconstant term
boundtypetype of bound provided by the genvbound

Definition at line 2059 of file prop_genvbounds.c.

References addNewGenVBound(), GenVBound::boundtype, GenVBound::coefs, GenVBound::coefssize, GenVBound::constant, GenVBound::cutoffcoef, FALSE, getGenVBound(), initPropdata(), GenVBound::ncoefs, 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
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, 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
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, 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
scipSCIP data structure
proppropagator, or NULL
varvariables to propagate
cutoffboundcutoff bound to use
pseudoobjvalpseudo objective value to use
tightenedpointer to if the domain was tightened

Definition at line 3775 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
scipSCIP data structure
propsync propagator
varvariable for bound
valvalue of bound
bndtypetype of bound

Definition at line 305 of file prop_sync.c.

References 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
propsync propagator

Definition at line 345 of file prop_sync.c.

References 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
propsync propagator

Definition at line 360 of file prop_sync.c.

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

Definition at line 3132 of file prop_vbounds.c.

References PROP_NAME, SCIP_Bool, SCIPexecPropVbounds(), SCIPfindProp(), SCIPpqueueNElems(), and SCIPpropGetData().

Referenced by SCIPincludePropVbounds().

◆ SCIPexecPropVbounds()

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

performs propagation of variables lower and upper bounds

Parameters
scipSCIP data structure
forceshould domain changes for continuous variables be forced
resultpointer to store result

Definition at line 3149 of file prop_vbounds.c.

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

Referenced by SCIPisPropagatedVbounds().