Detailed Description
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.
#include "blockmemshell/memory.h"
#include "scip/prop_pseudoobj.h"
#include "scip/pub_event.h"
#include "scip/pub_implics.h"
#include "scip/pub_message.h"
#include "scip/pub_misc.h"
#include "scip/pub_misc_sort.h"
#include "scip/pub_prop.h"
#include "scip/pub_var.h"
#include "scip/scip_conflict.h"
#include "scip/scip_event.h"
#include "scip/scip_general.h"
#include "scip/scip_lp.h"
#include "scip/scip_mem.h"
#include "scip/scip_message.h"
#include "scip/scip_numerics.h"
#include "scip/scip_param.h"
#include "scip/scip_pricer.h"
#include "scip/scip_prob.h"
#include "scip/scip_probing.h"
#include "scip/scip_prop.h"
#include "scip/scip_solvingstats.h"
#include "scip/scip_tree.h"
#include "scip/scip_var.h"
#include "scip/dbldblarith.h"
#include <string.h>
Go to the source code of this file.
Data Structures | |
struct | SCIP_ObjImplics |
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 |
Macro Definition Documentation
◆ PROP_NAME
#define PROP_NAME "pseudoobj" |
Definition at line 68 of file prop_pseudoobj.c.
◆ PROP_DESC
#define PROP_DESC "pseudo objective function propagator" |
Definition at line 69 of file prop_pseudoobj.c.
◆ PROP_TIMING
#define PROP_TIMING SCIP_PROPTIMING_BEFORELP | SCIP_PROPTIMING_DURINGLPLOOP | SCIP_PROPTIMING_AFTERLPLOOP |
Definition at line 70 of file prop_pseudoobj.c.
◆ PROP_PRIORITY
#define PROP_PRIORITY 3000000 |
propagator priority
Definition at line 71 of file prop_pseudoobj.c.
◆ PROP_FREQ
#define PROP_FREQ 1 |
propagator frequency
Definition at line 72 of file prop_pseudoobj.c.
◆ PROP_DELAY
#define PROP_DELAY FALSE |
should propagation method be delayed, if other propagators found reductions?
Definition at line 73 of file prop_pseudoobj.c.
◆ PROP_PRESOL_PRIORITY
#define PROP_PRESOL_PRIORITY +6000000 |
priority of the presolving method (>= 0: before, < 0: after constraint handlers); combined with presolvers
Definition at line 74 of file prop_pseudoobj.c.
◆ PROP_PRESOL_MAXROUNDS
#define PROP_PRESOL_MAXROUNDS -1 |
maximal number of presolving rounds the presolver participates in (-1: no limit)
Definition at line 75 of file prop_pseudoobj.c.
◆ PROP_PRESOLTIMING
#define PROP_PRESOLTIMING SCIP_PRESOLTIMING_FAST /* timing of the presolving method (fast, medium, or exhaustive) */ |
Definition at line 78 of file prop_pseudoobj.c.
◆ EVENTHDLR_NAME
#define EVENTHDLR_NAME "pseudoobj" |
Definition at line 80 of file prop_pseudoobj.c.
◆ EVENTHDLR_DESC
#define EVENTHDLR_DESC "bound change event handler for pseudo objective function propagator" |
Definition at line 81 of file prop_pseudoobj.c.
◆ DEFAULT_MINUSELESS
#define DEFAULT_MINUSELESS 100 |
minimal number of successive non-binary variable propagator whithout a bound reduction before aborted
Definition at line 83 of file prop_pseudoobj.c.
◆ DEFAULT_MAXVARSFRAC
#define DEFAULT_MAXVARSFRAC 0.1 |
maximal fraction of non-binary variables with non-zero objective without a bound reduction before aborted
Definition at line 86 of file prop_pseudoobj.c.
◆ DEFAULT_PROPFULLINROOT
#define DEFAULT_PROPFULLINROOT TRUE |
do we want to propagate all non-binary variables if we are propagating the root node?
Definition at line 89 of file prop_pseudoobj.c.
◆ DEFAULT_PROPCUTOFFBOUND
#define DEFAULT_PROPCUTOFFBOUND TRUE |
propagate new cutoff bound directly globally
Definition at line 90 of file prop_pseudoobj.c.
◆ DEFAULT_FORCE
#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 91 of file prop_pseudoobj.c.
◆ DEFAULT_MAXNEWVARS
#define DEFAULT_MAXNEWVARS 1000 |
number of variable added after the propagator is reinitialized?
Definition at line 98 of file prop_pseudoobj.c.
◆ DEFAULT_PROPUSEIMPLICS
#define DEFAULT_PROPUSEIMPLICS TRUE |
use implications to strengthen the propagation of binary variable (increasing the objective change)?
Definition at line 99 of file prop_pseudoobj.c.
◆ DEFAULT_RESPROPUSEIMPLICS
#define DEFAULT_RESPROPUSEIMPLICS TRUE |
use implications to strengthen the resolve propagation of binary variable (increasing the objective change)?
Definition at line 100 of file prop_pseudoobj.c.
◆ DEFAULT_MAXIMPLVARS
#define DEFAULT_MAXIMPLVARS 50000 |
maximum number of binary variables the implications are used if turned on (-1: unlimited)?
Definition at line 101 of file prop_pseudoobj.c.
◆ MAX_CLIQUELENGTH
#define MAX_CLIQUELENGTH 50 |
Definition at line 839 of file prop_pseudoobj.c.
Referenced by collectMinactImplicVars(), and getMaxactImplicObjchg().
Typedef Documentation
◆ SCIP_OBJIMPLICS
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 118 of file prop_pseudoobj.c.
Function Documentation
◆ checkImplicsApplied()
check that the implications are applied for a globally fixed variable
- Parameters
-
scip SCIP data structure var variable to check the implications
Definition at line 174 of file prop_pseudoobj.c.
◆ checkGlbfirstnonfixed()
|
static |
check if the global fixed indices are correct
- Parameters
-
propdata propagator data
Definition at line 221 of file prop_pseudoobj.c.
References NULL, SCIP_DECL_SORTPTRCOMP(), SCIPvarGetLbGlobal(), and SCIPvarGetUbGlobal().
Referenced by propagateCutoffboundBinvars(), propagateCutoffboundGlobally(), and resolvePropagation().
◆ SCIP_DECL_SORTPTRCOMP() [1/2]
|
static |
compares objective implications w.r.t. their maximum contribution
Definition at line 252 of file prop_pseudoobj.c.
Referenced by checkGlbfirstnonfixed().
◆ SCIP_DECL_SORTPTRCOMP() [2/2]
|
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 278 of file prop_pseudoobj.c.
◆ SCIP_DECL_HASHGETKEY()
|
static |
hash key retrieval function for cliques
Definition at line 335 of file prop_pseudoobj.c.
◆ SCIP_DECL_HASHKEYEQ()
|
static |
returns TRUE iff the cliques are equal
Definition at line 342 of file prop_pseudoobj.c.
References SCIPcliqueGetId().
◆ SCIP_DECL_HASHKEYVAL()
|
static |
returns the hash value of the key
Definition at line 351 of file prop_pseudoobj.c.
◆ objimplicsCreate()
|
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
- Parameters
-
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 364 of file prop_pseudoobj.c.
References FALSE, MAX, SCIP_ObjImplics::nlbimpls, SCIP_ObjImplics::nubimpls, NULL, objimplicsFree(), SCIP_Bool, SCIP_BOUNDTYPE_LOWER, SCIP_CALL, SCIP_OKAY, SCIPallocBlockMemory, SCIPallocBlockMemoryArray, SCIPcaptureVar(), SCIPdebugMsg, SCIPhashmapExists(), SCIPhashmapGetImageInt(), SCIPisNegative(), SCIPisZero(), SCIPtightenVarLbGlobal(), SCIPtightenVarUbGlobal(), SCIPvarGetBestBoundType(), SCIPvarGetLbGlobal(), SCIPvarGetName(), SCIPvarGetObj(), SCIPvarGetUbGlobal(), and SCIPvarIsBinary().
Referenced by collectMinactVar().
◆ objimplicsFree()
|
static |
frees an objective implication data structure
- Parameters
-
scip SCIP data structure objimplics pointer to objective implication data structure
Definition at line 498 of file prop_pseudoobj.c.
Referenced by objimplicsCreate().
◆ objimplicsDelPos()
|
static |
remove the given variable at the given pos from the objective implication data structure
- Parameters
-
scip SCIP data structure objimplics objective implication data structure pos position
Definition at line 526 of file prop_pseudoobj.c.
Referenced by getMinactImplicObjchg().
◆ catchObjEvent()
|
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
- Parameters
-
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 577 of file prop_pseudoobj.c.
References dropObjEvent(), NULL, SCIP_CALL, SCIP_EVENTTYPE_GLBCHANGED, SCIP_EVENTTYPE_GUBCHANGED, SCIP_OKAY, SCIP_Real, SCIPcatchVarEvent(), SCIPisZero(), and SCIPvarGetObj().
◆ dropObjEvent()
|
static |
drop variable event w.r.t. objective coefficient
- Parameters
-
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 608 of file prop_pseudoobj.c.
References dropVarEvents(), NULL, SCIP_CALL, SCIP_EVENTTYPE_GLBCHANGED, SCIP_EVENTTYPE_GUBCHANGED, SCIP_OKAY, SCIP_Real, SCIPdropVarEvent(), SCIPisZero(), and SCIPvarGetObj().
Referenced by catchObjEvent().
◆ dropVarEvents()
|
static |
drop all variable events
- Parameters
-
scip SCIP data structure propdata propagator data
Definition at line 639 of file prop_pseudoobj.c.
Referenced by dropObjEvent().
◆ propdataReset()
|
static |
reset propagatore data structure
- Parameters
-
propdata propagator data
Definition at line 702 of file prop_pseudoobj.c.
◆ propdataExit()
|
static |
free propagator data
- Parameters
-
scip SCIP data structure propdata propagator data
Definition at line 734 of file prop_pseudoobj.c.
Referenced by SCIP_DECL_PROPEXEC(), and SCIP_DECL_PROPEXITSOL().
◆ getVarObjchg()
|
static |
returns the objective change for the given binary variable
- Parameters
-
var variable to get objective change for boundtype bound type to consider bound fixing bound
Definition at line 770 of file prop_pseudoobj.c.
Referenced by adjustCutoffbound(), collectMinactObjchg(), collectMinactVar(), getMaxactObjchg(), and getMinactObjchg().
◆ collectMinactImplicVar()
|
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;
- Parameters
-
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 789 of file prop_pseudoobj.c.
References NULL, REALABS, SCIP_Real, SCIPhashmapExists(), SCIPhashmapGetImageInt(), SCIPisZero(), SCIPvarGetLbGlobal(), SCIPvarGetObj(), SCIPvarGetUbGlobal(), and TRUE.
Referenced by collectMinactImplicVars().
◆ 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) \]
- Parameters
-
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 856 of file prop_pseudoobj.c.
References collectMinactImplicVar(), FALSE, getMinactImplicObjchg(), MAX_CLIQUELENGTH, NULL, 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().
◆ getMinactImplicObjchg()
|
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)
- Parameters
-
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 983 of file prop_pseudoobj.c.
References collectMinactObjchg(), FALSE, SCIP_ObjImplics::nlbimpls, SCIP_ObjImplics::nubimpls, NULL, 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().
◆ collectMinactObjchg()
|
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;
- Parameters
-
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 1068 of file prop_pseudoobj.c.
References collectMinactImplicVars(), getMinactObjchg(), getVarObjchg(), NULL, SCIP_CALL, SCIP_OKAY, SCIPvarGetBestBoundType(), and SCIPvarIsBinary().
Referenced by collectMinactVar(), and getMinactImplicObjchg().
◆ 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; 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)
- Parameters
-
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 1101 of file prop_pseudoobj.c.
References getMaxactImplicObjchg(), getMinactImplicObjchg(), getVarObjchg(), SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPvarGetBestBoundType(), and SCIPvarIsBinary().
Referenced by collectMinactObjchg(), and propagateCutoffboundBinvar().
◆ getMaxactImplicObjchg()
|
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) \]
- Parameters
-
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 1137 of file prop_pseudoobj.c.
References BMSclearMemoryArray, FALSE, getMaxactObjchg(), MAX_CLIQUELENGTH, NULL, 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().
◆ getMaxactObjchg()
|
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
- Parameters
-
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 1327 of file prop_pseudoobj.c.
References getMaxactImplicObjchg(), getVarObjchg(), NULL, resetContributors(), SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIPvarGetWorstBoundType(), and SCIPvarIsBinary().
Referenced by collectMaxactVar(), getMaxactImplicObjchg(), and propagateLowerboundBinvar().
◆ resetContributors()
|
static |
reset variables array which marks variables which are collected
- Parameters
-
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 1356 of file prop_pseudoobj.c.
References collectMinactVar(), FALSE, NULL, SCIP_Bool, SCIPhashmapExists(), and SCIPhashmapGetImageInt().
Referenced by collectMinactVar(), and getMaxactObjchg().
◆ collectMinactVar()
|
static |
check if the given variable should be collected for the minimum activity propagation
- Parameters
-
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 1381 of file prop_pseudoobj.c.
References collectMaxactVar(), collectMinactObjchg(), FALSE, getVarObjchg(), NULL, 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().
◆ collectMaxactVar()
|
static |
check if the given variable should be collected for the maximum activity propagation
- Parameters
-
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 1497 of file prop_pseudoobj.c.
References FALSE, getMaxactObjchg(), NULL, propdataInit(), SCIP_BOUNDTYPE_LOWER, SCIP_BOUNDTYPE_UPPER, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPisPositive(), SCIPisZero(), SCIPvarIsBinary(), and TRUE.
Referenced by collectMinactVar().
◆ propdataInit()
|
static |
initializate the propagator
- Parameters
-
scip SCIP data structure propdata propagator data
Definition at line 1534 of file prop_pseudoobj.c.
Referenced by collectMaxactVar(), and SCIP_DECL_PROPEXEC().
◆ addConflictBounds()
|
static |
adds for the given non-binary variable a conflict bound depending on its objective contribution
- Parameters
-
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 1845 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().
◆ getConflictImplics()
|
static |
check for the given implication variables if they also contribute to the required minimum activity
- Parameters
-
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 1905 of file prop_pseudoobj.c.
References addConflictBinvar(), FALSE, NULL, REALABS, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPdebugMsg, SCIPgetVarLbAtIndex(), SCIPgetVarUbAtIndex(), SCIPhashtableExists(), SCIPhashtableInsert(), SCIPvarGetName(), SCIPvarGetObj(), SCIPvarIsBinary(), and TRUE.
Referenced by addConflictBinvar(), addConflictBounds(), and adjustCutoffbound().
◆ addConflictBinvar()
|
static |
adds for the given binary variable a conflict bound depending on its objective contribution
- Parameters
-
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 1952 of file prop_pseudoobj.c.
References adjustCutoffbound(), FALSE, getConflictImplics(), MAX, SCIP_ObjImplics::nlbimpls, SCIP_ObjImplics::nubimpls, NULL, 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().
◆ adjustCutoffbound()
|
static |
resolves a propagation by supplying the variables whose bound changes increased the pseudo objective value above the cutoff bound
- Parameters
-
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 2040 of file prop_pseudoobj.c.
References FALSE, getConflictImplics(), getVarObjchg(), SCIP_ObjImplics::nlbimpls, SCIP_ObjImplics::nubimpls, NULL, 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().
◆ resolvePropagation()
|
static |
resolves a propagation by supplying the variables whose bound changes increased the pseudo objective value above the cutoff bound
- Parameters
-
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 2136 of file prop_pseudoobj.c.
References addConflictBinvar(), addConflictBounds(), adjustCutoffbound(), checkGlbfirstnonfixed(), FALSE, infinity, NULL, propagateCutoffboundVar(), SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPdebugMsg, SCIPgetGlobalPseudoObjval(), SCIPhashtableExists(), SCIPhashtableRemoveAll(), SCIPisInfinity(), SCIPisPositive(), SCIPisZero(), SCIPvarGetObj(), and TRUE.
Referenced by adjustCutoffbound(), and propagateCutoffboundBinvar().
◆ propagateCutoffboundVar()
|
static |
propagates the given variable against the cutoff bound
- Parameters
-
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 2282 of file prop_pseudoobj.c.
References FALSE, NULL, propagateCutoffboundBinvar(), QUAD, QUAD_TO_DBL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPdebugMsg, SCIPinferVarLbProp(), SCIPinferVarUbProp(), SCIPisFeasEQ(), SCIPisInfinity(), SCIPisLT(), SCIPisZero(), SCIPquadprecDivQD, SCIPquadprecSumDD, SCIPquadprecSumQD, SCIPtightenVarLbGlobal(), SCIPtightenVarUbGlobal(), SCIPvarGetLbGlobal(), SCIPvarGetLbLocal(), SCIPvarGetName(), SCIPvarGetUbGlobal(), and SCIPvarGetUbLocal().
Referenced by propagateCutoffboundBinvar(), propagateCutoffboundGlobally(), resolvePropagation(), and SCIPpropagateCutoffboundVar().
◆ propagateCutoffboundBinvar()
|
static |
propagates the given binary variable against the cutoff bound
- Parameters
-
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 2396 of file prop_pseudoobj.c.
References FALSE, getMinactObjchg(), NULL, 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().
◆ propagateCutoffboundGlobally()
|
static |
globally propagates if a new cutoff bound or global pseudo objective value (minimum activity of the objective function) is available
- Parameters
-
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 2480 of file prop_pseudoobj.c.
References checkGlbfirstnonfixed(), FALSE, MAX, NULL, 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().
◆ propagateCutoffboundBinvars()
|
static |
propagates the cutoff bound for binary variables (c*x <= cutoff)
- Parameters
-
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 2637 of file prop_pseudoobj.c.
References checkGlbfirstnonfixed(), FALSE, NULL, propagateCutoffbound(), propagateCutoffboundBinvar(), SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIPdebugMsg, SCIPpropGetData(), SCIPvarGetLbLocal(), SCIPvarGetUbLocal(), and TRUE.
Referenced by propagateCutoffboundGlobally().
◆ propagateCutoffbound()
|
static |
propagates the cutoff bound c*x <= cutoff
- Parameters
-
scip SCIP data structure prop propagator result pointer to store the result of the callback method
Definition at line 2770 of file prop_pseudoobj.c.
Referenced by propagateCutoffboundBinvars(), and SCIP_DECL_PROPEXEC().
◆ calcMaxObjPseudoactivity()
|
static |
recalculates the maximum objective pseudoactivity
- Parameters
-
scip SCIP data structure propdata propagator data
Definition at line 2966 of file prop_pseudoobj.c.
◆ updateMaxObjPseudoactivity()
|
static |
updates the pseudo objective activity if necessary
- Parameters
-
scip SCIP data structure propdata propagator data
Definition at line 3016 of file prop_pseudoobj.c.
◆ getMaxObjPseudoactivityResidualValue()
|
static |
returns the residual pseudo objective activity without the given value
- Parameters
-
scip SCIP data structure propdata propagator data contrib value to eliminate from pseudo objective activity
Definition at line 3031 of file prop_pseudoobj.c.
◆ getMaxObjPseudoactivityResidual()
|
static |
returns the residual pseudo objective activity
- Parameters
-
scip SCIP data structure propdata propagator data var variable to get residual activity for
Definition at line 3069 of file prop_pseudoobj.c.
Referenced by propagateLowerboundVar().
◆ getMaxObjPseudoactivity()
|
static |
returns the maximum pseudo objective activity of the objective function
- Parameters
-
scip SCIP data structure propdata propagator data
Definition at line 3102 of file prop_pseudoobj.c.
◆ propagateLowerboundBinvar()
|
static |
propagates the global domain of the given binary variable against the lower bound (c*x >= lowerbound)
- Parameters
-
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 3112 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.
◆ propagateLowerboundVar()
|
static |
propagates the global domains of the given variable with non-zero objective coefficient against the lower bound (c*x >= lowerbound)
- Note
- In case the variable is integral we force the update of the new bound
- Parameters
-
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 3170 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().
◆ propagateLowerbound()
|
static |
propagates the global lower (dual) bound c*x >= lowerbound
- Parameters
-
scip SCIP data structure prop propagator result pointer to store the result of the callback method
Definition at line 3235 of file prop_pseudoobj.c.
Referenced by propagateLowerboundVar(), and SCIP_DECL_PROPEXEC().
◆ SCIP_DECL_PROPCOPY()
|
static |
copy method for propagator plugins (called when SCIP copies plugins)
Definition at line 3436 of file prop_pseudoobj.c.
◆ SCIP_DECL_PROPFREE()
|
static |
destructor of propagator to free user data (called when SCIP is exiting)
Definition at line 3450 of file prop_pseudoobj.c.
◆ SCIP_DECL_PROPINITSOL()
|
static |
solving process initialization method of propagator (called when branch and bound process is about to begin)
Definition at line 3465 of file prop_pseudoobj.c.
References NULL, SCIP_CALL, SCIP_DECL_PROPEXITSOL(), SCIP_EVENTTYPE_VARADDED, SCIP_OKAY, SCIPcatchEvent(), SCIPpropGetData(), and TRUE.
◆ SCIP_DECL_PROPEXITSOL()
|
static |
solving process deinitialization method of propagator (called before branch and bound process data is freed)
Definition at line 3489 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().
◆ SCIP_DECL_PROPPRESOL()
|
static |
presolving method of propagator
Definition at line 3512 of file prop_pseudoobj.c.
Referenced by SCIP_DECL_PROPEXITSOL().
◆ SCIP_DECL_PROPEXEC()
|
static |
execution method of propagator
Definition at line 3595 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().
◆ SCIP_DECL_PROPRESPROP()
|
static |
propagation conflict resolving method of propagator
Definition at line 3651 of file prop_pseudoobj.c.
Referenced by SCIP_DECL_PROPEXEC().
◆ SCIP_DECL_EVENTEXEC()
|
static |
execution method of bound change event handler
Definition at line 3684 of file prop_pseudoobj.c.