SCIP Doxygen Documentation
 
Loading...
Searching...
No Matches

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.

Topics

 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.h
 generalized variable bounds propagator
 
file  prop_nlobbt.h
 nonlinear OBBT 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_symmetry.h
 propagator for symmetry handling
 
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 2139 of file prop_genvbounds.c.

References addNewGenVBound(), assert(), FALSE, getGenVBound(), i, initPropdata(), NULL, PROP_NAME, SCIP_CALL, SCIP_INVALIDDATA, SCIP_OKAY, SCIPallocBlockMemory, SCIPcaptureVar(), SCIPdebug, SCIPdebugMsg, SCIPduplicateBlockMemoryArray, SCIPerrorMessage, SCIPfreeBlockMemoryArray, SCIPgetTransObjoffset(), SCIPgetTransObjscale(), SCIPisInfinity(), SCIPisNegative(), SCIPisPositive(), SCIPpropGetData(), SCIPpropGetName(), SCIPreallocBlockMemoryArray, SCIPreleaseVar(), SCIPvarIsRelaxationOnly(), TRUE, var, and vars.

Referenced by addGenVBound(), and createGenVBound().

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

References assert(), bound, cutoff, FALSE, i, NULL, nvars, SCIP_BOUNDTYPE_LOWER, SCIP_BOUNDTYPE_UPPER, SCIP_CALL, SCIP_LOCKTYPE_MODEL, SCIP_OKAY, SCIPchgVarLbProbing(), SCIPchgVarUbProbing(), SCIPdebugMsg, SCIPenableVarHistory(), SCIPendProbing(), SCIPisGE(), SCIPisGT(), SCIPisLE(), SCIPisLT(), SCIPpropagateProbing(), SCIPpropagateProbingImplications(), SCIPstartProbing(), SCIPvarGetLbGlobal(), SCIPvarGetLbLocal(), SCIPvarGetName(), SCIPvarGetNCliques(), SCIPvarGetNImpls(), SCIPvarGetNLocksDownType(), SCIPvarGetNLocksUpType(), SCIPvarGetUbGlobal(), SCIPvarGetUbLocal(), TRUE, and vars.

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

References assert(), cutoff, FALSE, i, MAX, MAXDNOM, MIN, NULL, nvars, SCIP_BOUNDTYPE_LOWER, SCIP_BOUNDTYPE_UPPER, SCIP_CALL, SCIP_LOCKTYPE_MODEL, SCIP_OKAY, 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(), SCIPvarGetNLocksDownType(), SCIPvarGetNLocksUpType(), SCIPvarGetType(), SCIPvarGetUbLocal(), SCIPvarIsBinary(), TRUE, var, and vars.

Referenced by applyProbing().

◆ 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 3808 of file prop_pseudoobj.c.

References objval, propagateCutoffboundVar(), SCIP_CALL, SCIP_OKAY, SCIPvarGetObj(), TRUE, and var.

◆ 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 323 of file prop_sync.c.

References assert(), i, NULL, PROP_NAME, SCIP_CALL, SCIP_OKAY, SCIPcalcMemGrowSize(), SCIPpropGetData(), SCIPpropGetName(), SCIPpropSetFreq(), SCIPreallocBlockMemoryArray, and var.

Referenced by SCIPaddConcurrentBndchg().

◆ 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 363 of file prop_sync.c.

References assert(), NULL, and SCIPpropGetData().

Referenced by SCIPgetConcurrentNTightenedBnds().

◆ 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 378 of file prop_sync.c.

References assert(), NULL, and SCIPpropGetData().

Referenced by SCIPgetConcurrentNTightenedIntBnds().

◆ 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 3189 of file prop_vbounds.c.

References assert(), 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
scipSCIP data structure
forceshould domain changes for continuous variables be forced
resultpointer to store result

Definition at line 3206 of file prop_vbounds.c.

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