SCIP
Solving Constraint Integer Programs
Solving Constraint Integer Programs
Pseudo objective propagator.
This propagator propagates the objective function using the cutoff bound and the pseudo objective value. The pseudo objective value can be seen as minimum activity of the linear objective function. Using this, this propagator checks if variables with non-zero objective coefficients can exceed the cutoff bound. If this is the case the corresponding bound can be tightened.
Definition in file prop_pseudoobj.c.
Go to the source code of this file.
Macros | |
| #define | PROP_NAME "pseudoobj" |
| #define | PROP_DESC "pseudo objective function propagator" |
| #define | PROP_TIMING SCIP_PROPTIMING_BEFORELP | SCIP_PROPTIMING_DURINGLPLOOP | SCIP_PROPTIMING_AFTERLPLOOP |
| #define | PROP_PRIORITY 3000000 |
| #define | PROP_FREQ 1 |
| #define | PROP_DELAY FALSE |
| #define | PROP_PRESOL_PRIORITY +6000000 |
| #define | PROP_PRESOL_MAXROUNDS -1 |
| #define | PROP_PRESOLTIMING SCIP_PRESOLTIMING_FAST /* timing of the presolving method (fast, medium, or exhaustive) */ |
| #define | EVENTHDLR_NAME "pseudoobj" |
| #define | EVENTHDLR_DESC "bound change event handler for pseudo objective function propagator" |
| #define | DEFAULT_MINUSELESS 100 |
| #define | DEFAULT_MAXVARSFRAC 0.1 |
| #define | DEFAULT_PROPFULLINROOT TRUE |
| #define | DEFAULT_PROPCUTOFFBOUND TRUE |
| #define | DEFAULT_FORCE FALSE |
| #define | DEFAULT_MAXNEWVARS 1000 |
| #define | DEFAULT_PROPUSEIMPLICS TRUE |
| #define | DEFAULT_RESPROPUSEIMPLICS TRUE |
| #define | DEFAULT_MAXIMPLVARS 50000 |
| #define | MAX_CLIQUELENGTH 50 |
Typedefs | |
| typedef struct SCIP_ObjImplics | SCIP_OBJIMPLICS |
| #define PROP_NAME "pseudoobj" |
Definition at line 37 of file prop_pseudoobj.c.
| #define PROP_DESC "pseudo objective function propagator" |
Definition at line 38 of file prop_pseudoobj.c.
| #define PROP_TIMING SCIP_PROPTIMING_BEFORELP | SCIP_PROPTIMING_DURINGLPLOOP | SCIP_PROPTIMING_AFTERLPLOOP |
Definition at line 39 of file prop_pseudoobj.c.
| #define PROP_PRIORITY 3000000 |
propagator priority
Definition at line 40 of file prop_pseudoobj.c.
| #define PROP_FREQ 1 |
propagator frequency
Definition at line 41 of file prop_pseudoobj.c.
| #define PROP_DELAY FALSE |
should propagation method be delayed, if other propagators found reductions?
Definition at line 42 of file prop_pseudoobj.c.
| #define PROP_PRESOL_PRIORITY +6000000 |
priority of the presolving method (>= 0: before, < 0: after constraint handlers); combined with presolvers
Definition at line 43 of file prop_pseudoobj.c.
| #define PROP_PRESOL_MAXROUNDS -1 |
maximal number of presolving rounds the presolver participates in (-1: no limit)
Definition at line 44 of file prop_pseudoobj.c.
| #define PROP_PRESOLTIMING SCIP_PRESOLTIMING_FAST /* timing of the presolving method (fast, medium, or exhaustive) */ |
Definition at line 47 of file prop_pseudoobj.c.
| #define EVENTHDLR_NAME "pseudoobj" |
Definition at line 49 of file prop_pseudoobj.c.
| #define EVENTHDLR_DESC "bound change event handler for pseudo objective function propagator" |
Definition at line 50 of file prop_pseudoobj.c.
| #define DEFAULT_MINUSELESS 100 |
minimal number of successive non-binary variable propagator whithout a bound reduction before aborted
Definition at line 52 of file prop_pseudoobj.c.
| #define DEFAULT_MAXVARSFRAC 0.1 |
maximal fraction of non-binary variables with non-zero objective without a bound reduction before aborted
Definition at line 55 of file prop_pseudoobj.c.
| #define DEFAULT_PROPFULLINROOT TRUE |
do we want to propagate all non-binary variables if we are propagating the root node?
Definition at line 58 of file prop_pseudoobj.c.
| #define DEFAULT_PROPCUTOFFBOUND TRUE |
propagate new cutoff bound directly globally
Definition at line 59 of file prop_pseudoobj.c.
| #define DEFAULT_FORCE FALSE |
should the propagator be forced even if active pricer are present? Note that can be done if it is known that the pseudo objective activity is given by the zero bound for all variables which are currently not present in the problem
Definition at line 60 of file prop_pseudoobj.c.
| #define DEFAULT_MAXNEWVARS 1000 |
number of variable added after the propagator is reinitialized?
Definition at line 67 of file prop_pseudoobj.c.
| #define DEFAULT_PROPUSEIMPLICS TRUE |
use implications to strengthen the propagation of binary variable (increasing the objective change)?
Definition at line 68 of file prop_pseudoobj.c.
| #define DEFAULT_RESPROPUSEIMPLICS TRUE |
use implications to strengthen the resolve propagation of binary variable (increasing the objective change)?
Definition at line 69 of file prop_pseudoobj.c.
| #define DEFAULT_MAXIMPLVARS 50000 |
maximum number of binary variables the implications are used if turned on (-1: unlimited)?
Definition at line 70 of file prop_pseudoobj.c.
| #define MAX_CLIQUELENGTH 50 |
Definition at line 810 of file prop_pseudoobj.c.
Referenced by collectMinactImplicVars(), and getMaxactImplicObjchg().
| typedef struct SCIP_ObjImplics SCIP_OBJIMPLICS |
implications in the form x == 0 or x == 1 ==> y == 0 or y == 1 for (x and y binary)
Definition at line 87 of file prop_pseudoobj.c.
check that the implications are applied for a globally fixed variable
| scip | SCIP data structure |
| var | variable to check the implications |
Definition at line 143 of file prop_pseudoobj.c.
|
static |
check if the global fixed indices are correct
| scip | SCIP data structure |
| propdata | propagator data |
Definition at line 190 of file prop_pseudoobj.c.
References SCIP_DECL_SORTPTRCOMP(), SCIPvarGetLbGlobal(), and SCIPvarGetUbGlobal().
Referenced by propagateCutoffboundBinvars(), propagateCutoffboundGlobally(), and resolvePropagation().
|
static |
compares objective implications w.r.t. their maximum contribution
Definition at line 222 of file prop_pseudoobj.c.
Referenced by checkGlbfirstnonfixed().
|
static |
compare variables w.r.t. (i) the absolute value the objective coefficient; (ii) the locks which indicate most effect – for the variables with a positive (negative) objective coefficient the down (up) lock is used since this lock indicates that tightened of the upper (lower) bound will triegger further domain propagations; (iii) the other locks; (iv) variable problem index;
Definition at line 248 of file prop_pseudoobj.c.
|
static |
hash key retrieval function for cliques
Definition at line 305 of file prop_pseudoobj.c.
|
static |
returns TRUE iff the cliques are equal
Definition at line 312 of file prop_pseudoobj.c.
References SCIPcliqueGetId().
|
static |
returns the hash value of the key
Definition at line 321 of file prop_pseudoobj.c.
|
static |
creates an objective implication data structure, fixes (globally) variables which are implied by lower and upper bound fixing, and clears the collected arrays for lower and upper bound
| scip | SCIP data structure |
| objimplics | pointer to objective implication data structure |
| objvars | objective contributor variables, or NULL |
| binobjvarmap | hash map mapping binary variables with none-zero objective to position in collected variables arrays, or NULL |
| collectedlbvars | temporary buffer to mark collected variables for lower bound fixing, or NULL |
| collectedubvars | temporary buffer to mark collected variables for upper bound fixing, or NULL |
| maxlbobjchg | maximum objective contributor if variables id fixed to zero |
| maxubobjchg | maximum objective contributor if variables id fixed to one |
| nlbimpls | number of variables contributing to to lower bound fix |
| nubimpls | number of variables contributing to to upper bound fix |
Definition at line 334 of file prop_pseudoobj.c.
References FALSE, MAX, SCIP_ObjImplics::nlbimpls, SCIP_ObjImplics::nubimpls, objimplicsFree(), SCIP_Bool, SCIP_BOUNDTYPE_LOWER, SCIP_CALL, SCIP_OKAY, SCIPallocBlockMemory, SCIPallocBlockMemoryArray, SCIPcaptureVar(), SCIPdebugMsg, SCIPhashmapExists(), SCIPhashmapGetImage(), SCIPisNegative(), SCIPisZero(), SCIPtightenVarLbGlobal(), SCIPtightenVarUbGlobal(), SCIPvarGetBestBoundType(), SCIPvarGetLbGlobal(), SCIPvarGetName(), SCIPvarGetObj(), SCIPvarGetUbGlobal(), and SCIPvarIsBinary().
Referenced by collectMinactVar().
|
static |
frees an objective implication data structure
| scip | SCIP data structure |
| objimplics | pointer to objective implication data structure |
Definition at line 468 of file prop_pseudoobj.c.
Referenced by objimplicsCreate().
|
static |
remove the given variable at the given pos from the objective implication data structure
| scip | SCIP data structure |
| objimplics | objective implication data structure |
| pos | position |
Definition at line 496 of file prop_pseudoobj.c.
Referenced by getMinactImplicObjchg().
|
static |
catch bound change events if the variable has a non-zero objective coefficient to check if the maximum activity of the objective function changed
| scip | SCIP data structure |
| propdata | propagator data |
| eventhdlr | event handler for global bound change events |
| var | variable for which the event should be dropped |
Definition at line 547 of file prop_pseudoobj.c.
References dropObjEvent(), SCIP_CALL, SCIP_EVENTTYPE_GLBCHANGED, SCIP_EVENTTYPE_GUBCHANGED, SCIP_OKAY, SCIP_Real, SCIPcatchVarEvent(), SCIPisZero(), and SCIPvarGetObj().
|
static |
drop variable event w.r.t. objective coefficient
| scip | SCIP data structure |
| propdata | propagator data |
| eventhdlr | event handler for global bound change events |
| var | variable for which the event should be dropped |
Definition at line 578 of file prop_pseudoobj.c.
References dropVarEvents(), SCIP_CALL, SCIP_EVENTTYPE_GLBCHANGED, SCIP_EVENTTYPE_GUBCHANGED, SCIP_OKAY, SCIP_Real, SCIPdropVarEvent(), SCIPisZero(), and SCIPvarGetObj().
Referenced by catchObjEvent().
|
static |
drop all variable events
| scip | SCIP data structure |
| propdata | propagator data |
Definition at line 609 of file prop_pseudoobj.c.
Referenced by dropObjEvent().
|
static |
reset propagatore data structure
| scip | SCIP data structure |
| propdata | propagator data |
Definition at line 672 of file prop_pseudoobj.c.
|
static |
free propagator data
| scip | SCIP data structure |
| propdata | propagator data |
Definition at line 705 of file prop_pseudoobj.c.
Referenced by SCIP_DECL_PROPEXEC(), and SCIP_DECL_PROPEXITSOL().
|
static |
returns the objective change for the given binary variable
| var | variable to get objective change for |
| boundtype | bound type to consider |
| bound | fixing bound |
Definition at line 741 of file prop_pseudoobj.c.
Referenced by adjustCutoffbound(), collectMinactObjchg(), collectMinactVar(), getMaxactObjchg(), and getMinactObjchg().
|
static |
returns the objective change provided by the implication variable by fixing it to the given bound w.r.t. minimum activity of the objective function; additionally it collects all contributors for that objective change;
| scip | SCIP data structure |
| var | variable to computes the objective contribution |
| binobjvarmap | hash map mapping binary variables with none-zero objective to position in collected variables arrays |
| collectedvars | temporary buffer to mark collected variables |
| nbinobjvars | number of binary variables with non-zero objective coefficient |
| contributors | array to store the contributors |
| ncontributors | pointer to store number of contributor to the objective contribution |
Definition at line 760 of file prop_pseudoobj.c.
References REALABS, SCIP_Real, SCIPhashmapExists(), SCIPhashmapGetImage(), SCIPisZero(), SCIPvarGetLbGlobal(), SCIPvarGetObj(), SCIPvarGetUbGlobal(), and TRUE.
Referenced by collectMinactImplicVars().
|
static |
returns the objective change provided by the implications of the given variable by fixing it to the given bound w.r.t. minimum activity of the objective function; additionally it collects all contributors for that objective change;
Let I(0) and I(1) be all implications of the given variable which follow by fixing it to given bound and evaluate to fixing the implication variable to zero (I(0)) or one (I(1)), respectively. The objective change provided by the implications are:
\[ \displaystyle sum_{x\in I(1)} (1 - \mbox{bestbound}(x)) \cdot \mbox{objval}(x) - sum_{x\in I(1)} \mbox{bestbound}(x) \cdot \mbox{objval}(x) = sum_{x\in I(0) \cup I(1)} (\mbox{impliedbound}(x) - \mbox{bestbound}(x)) \cdot \mbox{objval}(x) \]
| scip | SCIP data structure |
| var | variable to computes the objective contribution |
| bound | bound to check for |
| binobjvarmap | hash map mapping binary variables with none-zero objective to position in collected variables arrays |
| collectedvars | temporary buffer to mark collected variables |
| nbinobjvars | number of binary variables with non-zero objective coefficient |
| contributors | array to store the contributors |
| uselesscliques | hash table to store useless cliques, or NULL |
| ncontributors | pointer to store number of contributor to the objective contribution |
| objchg | pointer to store the objective change |
Definition at line 827 of file prop_pseudoobj.c.
References collectMinactImplicVar(), FALSE, getMinactImplicObjchg(), MAX_CLIQUELENGTH, SCIP_Bool, SCIP_BOUNDTYPE_LOWER, SCIP_BOUNDTYPE_UPPER, SCIP_CALL, SCIP_INVALIDDATA, SCIP_OKAY, SCIP_Real, SCIPcliqueGetNVars(), SCIPcliqueGetValues(), SCIPcliqueGetVars(), SCIPhashtableExists(), SCIPhashtableInsert(), SCIPisZero(), SCIPvarGetBestBoundType(), SCIPvarGetCliques(), SCIPvarGetLbGlobal(), SCIPvarGetNCliques(), SCIPvarGetObj(), SCIPvarGetUbGlobal(), SCIPvarIsBinary(), and TRUE.
Referenced by collectMinactObjchg().
|
static |
returns the objective change provided by the implications of the given variable by fixing it to the given bound w.r.t. minimum activity of the objective function
Let I(0) and I(1) be all implications of the given variable which follow by fixing it to given bound and evaluate to fixing the implication variable to zero (I(0)) or one (I(1)), respectively. The objective change provided by the implications are:
\[ \displaystyle sum_{x\in I(1)} (1 - \mbox{bestbound}(x)) \cdot \mbox{objval}(x) - sum_{x\in I(1)} \mbox{bestbound}(x) \cdot \mbox{objval}(x) = sum_{x\in I(0) \cup I(1)} (\mbox{impliedbound}(x) - \mbox{bestbound}(x)) \cdot \mbox{objval}(x) \]
This can be done w.r.t. global variable bounds (local == FALSE), w.r.t. local variable bounds (local == TRUE && bdchgidx == NULL), and w.r.t. given time stamp (local == TRUE && bdchgidx != NULL)
| scip | SCIP data structure |
| var | variable to computes the objective contribution |
| objimplics | objective implication data for the given variable |
| bdchgidx | bound change index representing time on path to current node, or NULL |
| bound | bound to check for |
| local | propagate local bounds, otherwise global bounds |
| objchg | pointer to store the objective change |
Definition at line 954 of file prop_pseudoobj.c.
References collectMinactObjchg(), FALSE, SCIP_ObjImplics::nlbimpls, SCIP_ObjImplics::nubimpls, objimplicsDelPos(), SCIP_ObjImplics::objvars, REALABS, SCIP_Bool, SCIP_BOUNDTYPE_LOWER, SCIP_BOUNDTYPE_UPPER, SCIP_CALL, SCIP_OKAY, SCIPgetVarLbAtIndex(), SCIPgetVarUbAtIndex(), SCIPisZero(), SCIPvarGetLbGlobal(), SCIPvarGetObj(), SCIPvarGetUbGlobal(), SCIPvarIsBinary(), SCIPvarsHaveCommonClique(), and TRUE.
Referenced by collectMinactImplicVars(), and getMinactObjchg().
|
static |
computes for the given binary variable the objective contribution by fixing it to given bound w.r.t. minimum activity of the objective function; additionally it collects all contributors for that objective change;
| scip | SCIP data structure |
| var | variable to computes the objective contribution |
| bound | bound to check for |
| binobjvarmap | hash map mapping binary variables with none-zero objective to position in collected variables arrays |
| collectedvars | temporary buffer to mark collected variables |
| nbinobjvars | number of binary variables with non-zero objective coefficient |
| contributors | array to store the contriboters |
| uselesscliques | hash table to store useless cliques, or NULL |
| ncontributors | pointer to store number of contributor to the objective contribution |
| objchg | pointer to store the objective change |
Definition at line 1039 of file prop_pseudoobj.c.
References collectMinactImplicVars(), getMinactObjchg(), getVarObjchg(), SCIP_CALL, SCIP_OKAY, SCIPvarGetBestBoundType(), and SCIPvarIsBinary().
Referenced by collectMinactVar(), and getMinactImplicObjchg().
|
static |
computes for the given binary variable the objective contribution by fixing it to given bound w.r.t. minimum activity of the objective function; this can be done w.r.t. global variable bounds (local == FALSE), w.r.t. local variable bounds (local == TRUE && bdchgidx == NULL), and w.r.t. given time stamp (local == TRUE && bdchgidx != NULL)
| scip | SCIP data structure |
| var | variable to computes the objective contribution |
| objimplics | objective implication data for the given variable |
| bdchgidx | bound change index representing time on path to current node, or NULL |
| bound | bound to check for |
| local | propagate local bounds, otherwise global bounds |
| objchg | pointer to store the objective change |
Definition at line 1072 of file prop_pseudoobj.c.
References getMaxactImplicObjchg(), getMinactImplicObjchg(), getVarObjchg(), SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPvarGetBestBoundType(), and SCIPvarIsBinary().
Referenced by collectMinactObjchg(), and propagateCutoffboundBinvar().
|
static |
returns the global (that means w.r.t. global bounds of the variables) objective change provided by all cliques of the given variable by fixing it to the given bound w.r.t. maximum activity of the objective function
Let I(0) and I(1) be all implications of the given variable which follow by fixing it to given bound and evaluate to fixing the implication variable to zero (I(0)) or one (I(1)), respectively. The objective change provided by these implications are:
\[ \displaystyle sum_{x\in I(1)} (1 - \mbox{worstbound}(x)) \cdot \mbox{objval}(x) - sum_{x\in I(1)} \mbox{worst}(x) \cdot \mbox{objval}(x) = sum_{x\in I(0) \cup I(1)} (\mbox{impliedbound}(x) - \mbox{worstbound}(x)) \cdot \mbox{objval}(x) \]
| scip | SCIP data structure |
| var | variable to computes the objective contribution |
| bound | bound to check for |
| objchg | pointer to store the objective change |
Definition at line 1108 of file prop_pseudoobj.c.
References BMSclearMemoryArray, FALSE, getMaxactObjchg(), MAX_CLIQUELENGTH, SCIP_Bool, SCIP_BOUNDTYPE_LOWER, SCIP_BOUNDTYPE_UPPER, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPcliqueGetNVars(), SCIPcliqueGetValues(), SCIPcliqueGetVars(), SCIPdebugMsg, SCIPfreeBufferArray, SCIPgetNContVars(), SCIPgetNVars(), SCIPgetVars(), SCIPisFeasGT(), SCIPisFeasLT(), SCIPisTransformed(), SCIPisZero(), SCIPvarGetCliques(), SCIPvarGetImplBounds(), SCIPvarGetImplTypes(), SCIPvarGetImplVars(), SCIPvarGetLbGlobal(), SCIPvarGetLbLocal(), SCIPvarGetName(), SCIPvarGetNCliques(), SCIPvarGetNImpls(), SCIPvarGetObj(), SCIPvarGetProbindex(), SCIPvarGetUbGlobal(), SCIPvarGetUbLocal(), SCIPvarGetWorstBoundType(), SCIPvarIsActive(), SCIPvarIsBinary(), and TRUE.
Referenced by getMaxactObjchg(), and getMinactObjchg().
|
static |
computes for the given binary variable the gloabl (that means w.r.t. global bounds of the variables) objective contribution by fixing it to given bound w.r.t. maximum activity of the objective function
| scip | SCIP data structure |
| var | variable to computes the objective contribution |
| bound | bound to check for |
| useimplics | should implications be used |
| objchg | pointer to store the objective change |
Definition at line 1298 of file prop_pseudoobj.c.
References getMaxactImplicObjchg(), getVarObjchg(), resetContributors(), SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIPvarGetWorstBoundType(), and SCIPvarIsBinary().
Referenced by collectMaxactVar(), getMaxactImplicObjchg(), and propagateLowerboundBinvar().
|
static |
reset variables array which marks variables which are collected
| binobjvarmap | hash map mapping binary variables with none-zero objective to position in collected variables arrays |
| collectedvars | temporary buffer to mark collected variables which should be reset |
| contributors | temporary buffer to use for collecting contributors |
| ncontributors | number of contributors |
Definition at line 1327 of file prop_pseudoobj.c.
References collectMinactVar(), FALSE, SCIP_Bool, SCIPhashmapExists(), and SCIPhashmapGetImage().
Referenced by collectMinactVar(), and getMaxactObjchg().
|
static |
check if the given variable should be collected for the minimum activity propagation
| scip | SCIP data structure |
| var | variable to check |
| objimplics | pointer to store the objective implication data structure w.r.t. minimum activity |
| useimplics | should implications be used |
| binobjvarmap | hash map mapping binary variables with none-zero objective to position in collected variables arrays |
| collectedlbvars | temporary buffer to mark collected variables for lower bound fixing |
| collectedubvars | temporary buffer to mark collected variables for upper bound fixing |
| nbinobjvars | number of binary variables with non-zero objective coefficient |
| contributors | temporary buffer to use for collecting contributors |
| uselesscliques | hash table to store useless cliques, or NULL |
| collect | pointer to store if the variable should be stored |
Definition at line 1352 of file prop_pseudoobj.c.
References collectMaxactVar(), collectMinactObjchg(), FALSE, getVarObjchg(), objimplicsCreate(), resetContributors(), SCIP_Bool, SCIP_BOUNDTYPE_LOWER, SCIP_BOUNDTYPE_UPPER, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPdebugMsg, SCIPisNegative(), SCIPisZero(), SCIPvarGetBestBoundType(), SCIPvarGetName(), SCIPvarGetNCliques(), SCIPvarGetObj(), and TRUE.
Referenced by resetContributors().
|
static |
check if the given variable should be collected for the maximum activity propagation
| scip | SCIP data structure |
| var | variable to check |
| useimplics | should implications be used |
| objchg | pointer to store the objective change w.r.t. maximum activity |
| isnotzero | pointer to store if the objective change is unequal to zero or not |
Definition at line 1468 of file prop_pseudoobj.c.
References FALSE, getMaxactObjchg(), propdataInit(), SCIP_BOUNDTYPE_LOWER, SCIP_BOUNDTYPE_UPPER, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPisPositive(), SCIPisZero(), SCIPvarIsBinary(), and TRUE.
Referenced by collectMinactVar().
|
static |
initializate the propagator
| scip | SCIP data structure |
| propdata | propagator data |
Definition at line 1505 of file prop_pseudoobj.c.
Referenced by collectMaxactVar(), and SCIP_DECL_PROPEXEC().
|
static |
adds for the given non-binary variable a conflict bound depending on its objective contribution
| scip | SCIP data structure |
| var | variable to check for objective contribution |
| bdchgidx | bound change index (time stamp of bound change), or NULL for current time |
| reqpseudoobjval | pointer to store the remaining minimum activity which has to be proven |
Definition at line 1817 of file prop_pseudoobj.c.
References FALSE, getConflictImplics(), SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPaddConflictLb(), SCIPaddConflictUb(), SCIPdebugMsg, SCIPgetVarLbAtIndex(), SCIPgetVarUbAtIndex(), SCIPisFeasGE(), SCIPisFeasLE(), SCIPisGT(), SCIPisLT(), SCIPisZero(), SCIPvarGetLbGlobal(), SCIPvarGetName(), SCIPvarGetObj(), and SCIPvarGetUbGlobal().
Referenced by resolvePropagation().
|
static |
check for the given implication variables if they also contribute to the required minimum activity
| scip | SCIP data structure |
| vars | variable to check for objective contribution |
| start | start index |
| end | end index |
| bdchgidx | bound change index (time stamp of bound change), or NULL for current time |
| addedvars | hash table containing variables which are already added directly or implicitly due to implications |
| reqpseudoobjval | pointer to store the remaining minimum activity which has to be proven |
| foundimplics | pointer to store if an implication is found |
Definition at line 1877 of file prop_pseudoobj.c.
References addConflictBinvar(), FALSE, REALABS, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPdebugMsg, SCIPgetVarLbAtIndex(), SCIPgetVarUbAtIndex(), SCIPhashtableExists(), SCIPhashtableInsert(), SCIPvarGetName(), SCIPvarGetObj(), SCIPvarIsBinary(), and TRUE.
Referenced by addConflictBinvar(), addConflictBounds(), and adjustCutoffbound().
|
static |
adds for the given binary variable a conflict bound depending on its objective contribution
| scip | SCIP data structure |
| var | variable to check for objective contribution |
| bdchgidx | bound change index (time stamp of bound change), or NULL for current time |
| objimplics | objective implication data for the given variable |
| addedvars | hash table containing variables which are already add directly or implicitly due to implications |
| respropuseimplics | should implications be used |
| reqpseudoobjval | pointer to store the remaining minimum activity which has to be proven |
Definition at line 1924 of file prop_pseudoobj.c.
References adjustCutoffbound(), FALSE, getConflictImplics(), MAX, SCIP_ObjImplics::nlbimpls, SCIP_ObjImplics::nubimpls, SCIP_ObjImplics::objvars, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPaddConflictLb(), SCIPaddConflictUb(), SCIPdebugMsg, SCIPgetVarLbAtIndex(), SCIPgetVarUbAtIndex(), SCIPhashtableExists(), SCIPhashtableInsert(), SCIPisNegative(), SCIPisPositive(), SCIPvarGetLbGlobal(), SCIPvarGetName(), SCIPvarGetObj(), SCIPvarGetUbGlobal(), and SCIPvarIsBinary().
Referenced by getConflictImplics(), and resolvePropagation().
|
static |
resolves a propagation by supplying the variables whose bound changes increased the pseudo objective value above the cutoff bound
| scip | SCIP data structure |
| propdata | propagator data |
| var | variable that was deduced |
| inferinfo | inference information |
| boundtype | the type of the changed bound (lower or upper bound) |
| bdchgidx | bound change index (time stamp of bound change), or NULL for current time |
| addedvars | hash table which contains variables which are already added or implicitly given as reason for the resolve, or NULL |
| cutoffbound | pointer to store the adjusted cutoff bound |
Definition at line 2010 of file prop_pseudoobj.c.
References FALSE, getConflictImplics(), getVarObjchg(), SCIP_ObjImplics::nlbimpls, SCIP_ObjImplics::nubimpls, SCIP_ObjImplics::objvars, resolvePropagation(), SCIP_Bool, SCIP_BOUNDTYPE_LOWER, SCIP_BOUNDTYPE_UPPER, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPfeastol(), SCIPgetVarLbAtIndex(), SCIPgetVarUbAtIndex(), SCIPisEQ(), SCIPisNegative(), SCIPisZero(), SCIPvarGetBestBoundType(), SCIPvarGetLbGlobal(), SCIPvarGetObj(), SCIPvarGetUbGlobal(), SCIPvarIsBinary(), SCIPvarIsIntegral(), and TRUE.
Referenced by addConflictBinvar(), and resolvePropagation().
|
static |
resolves a propagation by supplying the variables whose bound changes increased the pseudo objective value above the cutoff bound
| scip | SCIP data structure |
| propdata | propagator data |
| cutoffbound | the global cutoff |
| infervar | variable that was deduced, or NULL for conflict analysis initialization |
| inferinfo | inference information |
| boundtype | the type of the changed bound (lower or upper bound) |
| bdchgidx | bound change index (time stamp of bound change), or NULL for current time |
Definition at line 2107 of file prop_pseudoobj.c.
References addConflictBinvar(), addConflictBounds(), adjustCutoffbound(), checkGlbfirstnonfixed(), FALSE, infinity, propagateCutoffboundVar(), SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPdebugMsg, SCIPgetGlobalPseudoObjval(), SCIPhashtableExists(), SCIPhashtableRemoveAll(), SCIPisInfinity(), SCIPisPositive(), SCIPisZero(), SCIPvarGetObj(), and TRUE.
Referenced by adjustCutoffbound(), and propagateCutoffboundBinvar().
|
static |
propagates the given variable against the cutoff bound
| scip | SCIP data structure |
| prop | propagator, or NULL |
| var | variable to propagate |
| inferinfo | inference information to store with the bound change |
| objchg | objective change |
| cutoffbound | cutoff bound to use |
| pseudoobjval | pseudo objective value to use |
| local | local or global propagation |
| tightened | pointer to store if the variable domain was tightened |
Definition at line 2253 of file prop_pseudoobj.c.
References FALSE, propagateCutoffboundBinvar(), SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPdebugMsg, SCIPinferVarLbProp(), SCIPinferVarUbProp(), SCIPisFeasEQ(), SCIPisInfinity(), SCIPisLT(), SCIPisZero(), SCIPtightenVarLbGlobal(), SCIPtightenVarUbGlobal(), SCIPvarGetLbGlobal(), SCIPvarGetLbLocal(), SCIPvarGetName(), SCIPvarGetUbGlobal(), and SCIPvarGetUbLocal().
Referenced by propagateCutoffboundBinvar(), propagateCutoffboundGlobally(), resolvePropagation(), and SCIPpropagateCutoffboundVar().
|
static |
propagates the given binary variable against the cutoff bound
| scip | SCIP data structure |
| prop | propagator, or NULL |
| var | variable to propagate |
| pos | position of the variable in the corresponding propdata variable array |
| cutoffbound | cutoff bound to use |
| pseudoobjval | pseudo objective value to use |
| tightened | pointer to store if the variable domain was tightened |
| cutoff | pointer to store if a cutoff was detected |
| local | propagate local bounds, otherwise global bounds |
Definition at line 2355 of file prop_pseudoobj.c.
References FALSE, getMinactObjchg(), propagateCutoffboundGlobally(), propagateCutoffboundVar(), resolvePropagation(), SCIP_Bool, SCIP_BOUNDTYPE_LOWER, SCIP_BOUNDTYPE_UPPER, SCIP_CALL, SCIP_CONFTYPE_PROPAGATION, SCIP_OKAY, SCIP_Real, SCIPanalyzeConflict(), SCIPgetDepth(), SCIPinitConflictAnalysis(), SCIPisConflictAnalysisApplicable(), SCIPisFeasLT(), SCIPisNegative(), SCIPisZero(), SCIPpropGetData(), SCIPvarIsBinary(), and TRUE.
Referenced by propagateCutoffboundBinvars(), propagateCutoffboundGlobally(), and propagateCutoffboundVar().
|
static |
globally propagates if a new cutoff bound or global pseudo objective value (minimum activity of the objective function) is available
| scip | SCIP data structure |
| prop | propagator |
| nchgbds | pointer to store the number of bound changes |
| cutoff | pointer to store if a cutoff was detected |
Definition at line 2439 of file prop_pseudoobj.c.
References checkGlbfirstnonfixed(), FALSE, MAX, propagateCutoffboundBinvar(), propagateCutoffboundBinvars(), propagateCutoffboundVar(), SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPdebugMsg, SCIPgetDepth(), SCIPgetGlobalPseudoObjval(), SCIPisGE(), SCIPisInfinity(), SCIPisZero(), SCIPpropGetData(), SCIPvarGetLbGlobal(), SCIPvarGetObj(), SCIPvarGetUbGlobal(), and TRUE.
Referenced by propagateCutoffboundBinvar().
|
static |
propagates the cutoff bound for binary variables (c*x <= cutoff)
| scip | SCIP data structure |
| prop | propagator |
| cutoffbound | cutoff bound to use |
| pseudoobjval | pseudo objective value to use |
| nfixedvars | pointer to store the number of fixed variables |
| cutoff | pointer to store if a cutoff was detected |
Definition at line 2596 of file prop_pseudoobj.c.
References checkGlbfirstnonfixed(), FALSE, propagateCutoffbound(), propagateCutoffboundBinvar(), SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIPdebugMsg, SCIPpropGetData(), SCIPvarGetLbLocal(), SCIPvarGetUbLocal(), and TRUE.
Referenced by propagateCutoffboundGlobally().
|
static |
propagates the cutoff bound c*x <= cutoff
| scip | SCIP data structure |
| prop | propagator |
| result | pointer to store the result of the callback method |
Definition at line 2729 of file prop_pseudoobj.c.
Referenced by propagateCutoffboundBinvars(), and SCIP_DECL_PROPEXEC().
|
static |
recalculates the maximum objective pseudoactivity
| scip | SCIP data structure |
| propdata | propagator data |
Definition at line 2925 of file prop_pseudoobj.c.
|
static |
updates the pseudo objective activity if necessary
| scip | SCIP data structure |
| propdata | propagator data |
Definition at line 2975 of file prop_pseudoobj.c.
|
static |
returns the residual pseudo objective activity without the given value
| scip | SCIP data structure |
| propdata | propagator data |
| contrib | value to eliminate from pseudo objective activity |
Definition at line 2990 of file prop_pseudoobj.c.
|
static |
returns the residual pseudo objective activity
| scip | SCIP data structure |
| propdata | propagator data |
| var | variable to get residual activity for |
Definition at line 3028 of file prop_pseudoobj.c.
Referenced by propagateLowerboundVar().
|
static |
returns the maximum pseudo objective activity of the objective function
| scip | SCIP data structure |
| propdata | propagator data |
Definition at line 3061 of file prop_pseudoobj.c.
|
static |
propagates the global domain of the given binary variable against the lower bound (c*x >= lowerbound)
| scip | SCIP data structure |
| var | variable to propagate |
| lowerbound | lower bound to use |
| maxpseudoobjact | maximum pseudo objective activity |
| useimplics | should implications be used |
| infeasible | pointer to store if the variable domain got empty, infeasible |
| tightened | pointer to store if the variable domain was tightened |
Definition at line 3071 of file prop_pseudoobj.c.
References FALSE, getMaxactObjchg(), propagateLowerboundVar(), SCIP_Bool, SCIP_BOUNDTYPE_LOWER, SCIP_BOUNDTYPE_UPPER, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPisDualfeasLE(), SCIPisFeasLT(), SCIPisInfinity(), SCIPisPositive(), SCIPtightenVarLbGlobal(), SCIPvarIsBinary(), and TRUE.
|
static |
propagates the global domains of the given variable with non-zero objective coefficient against the lower bound (c*x >= lowerbound)
| scip | SCIP data structure |
| propdata | propagator data |
| var | variable to propagate |
| lowerbound | lower bound to use |
| infeasible | pointer to store if the variable domain got empty, infeasible |
| tightened | pointer to store if the variable domain was tightened |
Definition at line 3129 of file prop_pseudoobj.c.
References FALSE, getMaxObjPseudoactivityResidual(), propagateLowerbound(), SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPisFeasGT(), SCIPisFeasLT(), SCIPisInfinity(), SCIPisZero(), SCIPtightenVarLbGlobal(), SCIPtightenVarUbGlobal(), SCIPvarGetLbGlobal(), SCIPvarGetObj(), SCIPvarGetUbGlobal(), SCIPvarIsIntegral(), and TRUE.
Referenced by propagateLowerboundBinvar().
|
static |
propagates the global lower (dual) bound c*x >= lowerbound
| scip | SCIP data structure |
| prop | propagator |
| result | pointer to store the result of the callback method |
Definition at line 3194 of file prop_pseudoobj.c.
Referenced by propagateLowerboundVar(), and SCIP_DECL_PROPEXEC().
|
static |
copy method for propagator plugins (called when SCIP copies plugins)
Definition at line 3395 of file prop_pseudoobj.c.
|
static |
destructor of propagator to free user data (called when SCIP is exiting)
Definition at line 3409 of file prop_pseudoobj.c.
|
static |
solving process initialization method of propagator (called when branch and bound process is about to begin)
Definition at line 3424 of file prop_pseudoobj.c.
References SCIP_CALL, SCIP_DECL_PROPEXITSOL(), SCIP_EVENTTYPE_VARADDED, SCIP_OKAY, SCIPcatchEvent(), SCIPpropGetData(), and TRUE.
|
static |
solving process deinitialization method of propagator (called before branch and bound process data is freed)
Definition at line 3448 of file prop_pseudoobj.c.
References FALSE, propdataExit(), SCIP_CALL, SCIP_DECL_PROPPRESOL(), SCIP_EVENTTYPE_VARADDED, SCIP_OKAY, SCIP_Real, and SCIPdropEvent().
Referenced by SCIP_DECL_PROPINITSOL().
|
static |
presolving method of propagator
Definition at line 3471 of file prop_pseudoobj.c.
Referenced by SCIP_DECL_PROPEXITSOL().
|
static |
execution method of propagator
Definition at line 3555 of file prop_pseudoobj.c.
References propagateCutoffbound(), propagateLowerbound(), propdataExit(), propdataInit(), SCIP_CALL, SCIP_CUTOFF, SCIP_DECL_PROPRESPROP(), SCIP_OKAY, SCIP_Real, SCIP_REDUCEDDOM, SCIP_STAGE_SOLVING, SCIPgetStage(), SCIPisEQ(), SCIPvarGetLbGlobal(), and SCIPvarGetUbGlobal().
|
static |
propagation conflict resolving method of propagator
Definition at line 3611 of file prop_pseudoobj.c.
Referenced by SCIP_DECL_PROPEXEC().
|
static |
execution method of bound change event handler
Definition at line 3644 of file prop_pseudoobj.c.