Scippy

SCIP

Solving Constraint Integer Programs

prop_pseudoobj.c File Reference

Detailed Description

Pseudo objective propagator.

Author
Tobias Achterberg
Stefan Heinz

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 <assert.h>
#include <string.h>
#include "scip/prop_pseudoobj.h"

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_AFTERLPLOOP | SCIP_PROPTIMING_DURINGLPLOOP
 
#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
 

Functions

static void checkImplicsApplied (SCIP *scip, SCIP_VAR *var)
 
static void checkGlbfirstnonfixed (SCIP *scip, SCIP_PROPDATA *propdata)
 
static SCIP_DECL_SORTPTRCOMP (objimplicsComp)
 
static SCIP_DECL_SORTPTRCOMP (varCompObj)
 
static SCIP_DECL_HASHGETKEY (cliqueGetHashkey)
 
static SCIP_DECL_HASHKEYEQ (cliqueIsHashkeyEq)
 
static SCIP_DECL_HASHKEYVAL (cliqueGetHashkeyVal)
 
static SCIP_RETCODE objimplicsCreate (SCIP *scip, SCIP_OBJIMPLICS **objimplics, SCIP_VAR **objvars, SCIP_HASHMAP *binobjvarmap, SCIP_Bool *collectedlbvars, SCIP_Bool *collectedubvars, SCIP_Real maxlbobjchg, SCIP_Real maxubobjchg, int nlbimpls, int nubimpls)
 
static SCIP_RETCODE objimplicsFree (SCIP *scip, SCIP_OBJIMPLICS **objimplics)
 
static SCIP_RETCODE objimplicsDelPos (SCIP *scip, SCIP_OBJIMPLICS *objimplics, int pos)
 
static SCIP_RETCODE catchObjEvent (SCIP *scip, SCIP_PROPDATA *propdata, SCIP_EVENTHDLR *eventhdlr, SCIP_VAR *var)
 
static SCIP_RETCODE dropObjEvent (SCIP *scip, SCIP_PROPDATA *propdata, SCIP_EVENTHDLR *eventhdlr, SCIP_VAR *var)
 
static SCIP_RETCODE dropVarEvents (SCIP *scip, SCIP_PROPDATA *propdata)
 
static void propdataReset (SCIP *scip, SCIP_PROPDATA *propdata)
 
static SCIP_RETCODE propdataExit (SCIP *scip, SCIP_PROPDATA *propdata)
 
static SCIP_Real getVarObjchg (SCIP_VAR *var, SCIP_BOUNDTYPE boundtype, SCIP_BOUNDTYPE bound)
 
static SCIP_Real collectMinactImplicVar (SCIP *scip, SCIP_VAR *var, SCIP_HASHMAP *binobjvarmap, SCIP_Bool *collectedvars, int nbinobjvars, SCIP_VAR **contributors, int *ncontributors)
 
static SCIP_RETCODE collectMinactImplicVars (SCIP *scip, SCIP_VAR *var, SCIP_BOUNDTYPE bound, SCIP_HASHMAP *binobjvarmap, SCIP_Bool *collectedvars, int nbinobjvars, SCIP_VAR **contributors, SCIP_HASHTABLE *uselesscliques, int *ncontributors, SCIP_Real *objchg)
 
static SCIP_RETCODE getMinactImplicObjchg (SCIP *scip, SCIP_VAR *var, SCIP_OBJIMPLICS *objimplics, SCIP_BDCHGIDX *bdchgidx, SCIP_BOUNDTYPE bound, SCIP_Bool local, SCIP_Real *objchg)
 
static SCIP_RETCODE collectMinactObjchg (SCIP *scip, SCIP_VAR *var, SCIP_BOUNDTYPE bound, SCIP_HASHMAP *binobjvarmap, SCIP_Bool *collectedvars, int nbinobjvars, SCIP_VAR **contributors, SCIP_HASHTABLE *uselesscliques, int *ncontributors, SCIP_Real *objchg)
 
static SCIP_RETCODE getMinactObjchg (SCIP *scip, SCIP_VAR *var, SCIP_OBJIMPLICS *objimplics, SCIP_BDCHGIDX *bdchgidx, SCIP_BOUNDTYPE bound, SCIP_Bool local, SCIP_Real *objchg)
 
static SCIP_RETCODE getMaxactImplicObjchg (SCIP *scip, SCIP_VAR *var, SCIP_BOUNDTYPE bound, SCIP_Real *objchg)
 
static SCIP_RETCODE getMaxactObjchg (SCIP *scip, SCIP_VAR *var, SCIP_BOUNDTYPE bound, SCIP_Bool useimplics, SCIP_Real *objchg)
 
static void resetContributors (SCIP_HASHMAP *binobjvarmap, SCIP_Bool *collectedvars, SCIP_VAR **contributors, int ncontributors)
 
static SCIP_RETCODE collectMinactVar (SCIP *scip, SCIP_VAR *var, SCIP_OBJIMPLICS **objimplics, SCIP_Bool useimplics, SCIP_HASHMAP *binobjvarmap, SCIP_Bool *collectedlbvars, SCIP_Bool *collectedubvars, int nbinobjvars, SCIP_VAR **contributors, SCIP_HASHTABLE *uselesscliques, SCIP_Bool *collect)
 
static SCIP_RETCODE collectMaxactVar (SCIP *scip, SCIP_VAR *var, SCIP_Bool useimplics, SCIP_Real *objchg, SCIP_Bool *isnotzero)
 
static SCIP_RETCODE propdataInit (SCIP *scip, SCIP_PROPDATA *propdata)
 
static SCIP_RETCODE addConflictBounds (SCIP *scip, SCIP_VAR *var, SCIP_BDCHGIDX *bdchgidx, SCIP_Real *reqpseudoobjval)
 
static SCIP_RETCODE getConflictImplics (SCIP *scip, SCIP_VAR **vars, int start, int end, SCIP_BDCHGIDX *bdchgidx, SCIP_HASHTABLE *addedvars, SCIP_Real *reqpseudoobjval, SCIP_Bool *foundimplics)
 
static SCIP_RETCODE addConflictBinvar (SCIP *scip, SCIP_VAR *var, SCIP_BDCHGIDX *bdchgidx, SCIP_OBJIMPLICS *objimplics, SCIP_HASHTABLE *addedvars, SCIP_Bool respropuseimplics, SCIP_Real *reqpseudoobjval)
 
static SCIP_RETCODE adjustCutoffbound (SCIP *scip, SCIP_PROPDATA *propdata, SCIP_VAR *var, int inferinfo, SCIP_BOUNDTYPE boundtype, SCIP_BDCHGIDX *bdchgidx, SCIP_HASHTABLE *addedvars, SCIP_Real *cutoffbound)
 
static SCIP_RETCODE resolvePropagation (SCIP *scip, SCIP_PROPDATA *propdata, SCIP_Real cutoffbound, SCIP_VAR *infervar, int inferinfo, SCIP_BOUNDTYPE boundtype, SCIP_BDCHGIDX *bdchgidx)
 
static SCIP_RETCODE propagateCutoffboundVar (SCIP *scip, SCIP_PROP *prop, SCIP_VAR *var, int inferinfo, SCIP_Real objchg, SCIP_Real cutoffbound, SCIP_Real pseudoobjval, SCIP_Bool local, SCIP_Bool *tightened)
 
static SCIP_RETCODE propagateCutoffboundBinvar (SCIP *scip, SCIP_PROP *prop, SCIP_VAR *var, int pos, SCIP_Real cutoffbound, SCIP_Real pseudoobjval, SCIP_Bool *tightened, SCIP_Bool *cutoff, SCIP_Bool local)
 
static SCIP_RETCODE propagateCutoffboundGlobally (SCIP *scip, SCIP_PROP *prop, int *nchgbds, SCIP_Bool *cutoff)
 
static SCIP_RETCODE propagateCutoffboundBinvars (SCIP *scip, SCIP_PROP *prop, SCIP_Real cutoffbound, SCIP_Real pseudoobjval, int *nfixedvars, SCIP_Bool *cutoff)
 
static SCIP_RETCODE propagateCutoffbound (SCIP *scip, SCIP_PROP *prop, SCIP_RESULT *result)
 
static void calcMaxObjPseudoactivity (SCIP *scip, SCIP_PROPDATA *propdata)
 
static void updateMaxObjPseudoactivity (SCIP *scip, SCIP_PROPDATA *propdata)
 
static SCIP_Real getMaxObjPseudoactivityResidualValue (SCIP *scip, SCIP_PROPDATA *propdata, SCIP_Real contrib)
 
static SCIP_Real getMaxObjPseudoactivityResidual (SCIP *scip, SCIP_PROPDATA *propdata, SCIP_VAR *var)
 
static SCIP_Real getMaxObjPseudoactivity (SCIP *scip, SCIP_PROPDATA *propdata)
 
static SCIP_RETCODE propagateLowerboundBinvar (SCIP *scip, SCIP_VAR *var, SCIP_Real lowerbound, SCIP_Real maxpseudoobjact, SCIP_Bool useimplics, SCIP_Bool *infeasible, SCIP_Bool *tightened)
 
static SCIP_RETCODE propagateLowerboundVar (SCIP *scip, SCIP_PROPDATA *propdata, SCIP_VAR *var, SCIP_Real lowerbound, SCIP_Bool *infeasible, SCIP_Bool *tightened)
 
static SCIP_RETCODE propagateLowerbound (SCIP *scip, SCIP_PROP *prop, SCIP_RESULT *result)
 
static SCIP_DECL_PROPCOPY (propCopyPseudoobj)
 
static SCIP_DECL_PROPFREE (propFreePseudoobj)
 
static SCIP_DECL_PROPINITSOL (propInitsolPseudoobj)
 
static SCIP_DECL_PROPEXITSOL (propExitsolPseudoobj)
 
static SCIP_DECL_PROPPRESOL (propPresolPseudoobj)
 
static SCIP_DECL_PROPEXEC (propExecPseudoobj)
 
static SCIP_DECL_PROPRESPROP (propRespropPseudoobj)
 
static SCIP_DECL_EVENTEXEC (eventExecPseudoobj)
 
SCIP_RETCODE SCIPincludePropPseudoobj (SCIP *scip)
 
SCIP_RETCODE SCIPpropagateCutoffboundVar (SCIP *scip, SCIP_PROP *prop, SCIP_VAR *var, SCIP_Real cutoffbound, SCIP_Real pseudoobjval, SCIP_Bool *tightened)
 

Macro Definition Documentation

#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_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 none 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 none 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 802 of file prop_pseudoobj.c.

Referenced by collectMinactImplicVars(), and getMaxactImplicObjchg().

Typedef Documentation

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.

Function Documentation

static void checkImplicsApplied ( SCIP scip,
SCIP_VAR var 
)
static

check that the implications are applied for a globally fixed variable

Parameters
scipSCIP data structure
varvariable to check the implications

Definition at line 137 of file prop_pseudoobj.c.

static void checkGlbfirstnonfixed ( SCIP scip,
SCIP_PROPDATA propdata 
)
static

check if the global fixed indices are correct

Parameters
scipSCIP data structure
propdatapropagator data

Definition at line 184 of file prop_pseudoobj.c.

References NULL, SCIP_DECL_SORTPTRCOMP(), SCIPvarGetLbGlobal(), and SCIPvarGetUbGlobal().

Referenced by propagateCutoffboundBinvars(), propagateCutoffboundGlobally(), and resolvePropagation().

static SCIP_DECL_SORTPTRCOMP ( objimplicsComp  )
static

compares objective implications w.r.t. their maximum contribution

Definition at line 216 of file prop_pseudoobj.c.

Referenced by checkGlbfirstnonfixed().

static SCIP_DECL_SORTPTRCOMP ( varCompObj  )
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 242 of file prop_pseudoobj.c.

static SCIP_DECL_HASHGETKEY ( cliqueGetHashkey  )
static

hash key retrieval function for cliques

Definition at line 299 of file prop_pseudoobj.c.

References FALSE, and TRUE.

static SCIP_DECL_HASHKEYEQ ( cliqueIsHashkeyEq  )
static

returns TRUE iff the cliques are equal

Definition at line 306 of file prop_pseudoobj.c.

References SCIPcliqueGetId().

static SCIP_DECL_HASHKEYVAL ( cliqueGetHashkeyVal  )
static

returns the hash value of the key

Definition at line 315 of file prop_pseudoobj.c.

static SCIP_RETCODE objimplicsCreate ( SCIP scip,
SCIP_OBJIMPLICS **  objimplics,
SCIP_VAR **  objvars,
SCIP_HASHMAP binobjvarmap,
SCIP_Bool collectedlbvars,
SCIP_Bool collectedubvars,
SCIP_Real  maxlbobjchg,
SCIP_Real  maxubobjchg,
int  nlbimpls,
int  nubimpls 
)
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
scipSCIP data structure
objimplicspointer to objective implication data structure
objvarsobjective contributor variables, or NULL
binobjvarmaphash map mapping binary variables with none-zero objective to position in collected variables arrays, or NULL
collectedlbvarstemporary buffer to mark collected variables for lower bound fixing, or NULL
collectedubvarstemporary buffer to mark collected variables for upper bound fixing, or NULL
maxlbobjchgmaximum objective contributor if variables id fixed to zero
maxubobjchgmaximum objective contributor if variables id fixed to one
nlbimplsnumber of variables contributing to to lower bound fix
nubimplsnumber of variables contributing to to upper bound fix

Definition at line 329 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(), SCIPdebugMessage, SCIPhashmapExists(), SCIPhashmapGetImage(), SCIPisNegative(), SCIPisZero(), SCIPtightenVarLbGlobal(), SCIPtightenVarUbGlobal(), SCIPvarGetBestBoundType(), SCIPvarGetLbGlobal(), SCIPvarGetName(), SCIPvarGetObj(), SCIPvarGetUbGlobal(), and SCIPvarIsBinary().

Referenced by collectMinactVar().

static SCIP_RETCODE objimplicsFree ( SCIP scip,
SCIP_OBJIMPLICS **  objimplics 
)
static

frees an objective implication data structure

Parameters
scipSCIP data structure
objimplicspointer to objective implication data structure

Definition at line 463 of file prop_pseudoobj.c.

Referenced by objimplicsCreate().

static SCIP_RETCODE objimplicsDelPos ( SCIP scip,
SCIP_OBJIMPLICS objimplics,
int  pos 
)
static

remove the given variable at the given pos from the objective implication data structure

Parameters
scipSCIP data structure
objimplicsobjective implication data structure
posposition

Definition at line 491 of file prop_pseudoobj.c.

Referenced by getMinactImplicObjchg().

static SCIP_RETCODE catchObjEvent ( SCIP scip,
SCIP_PROPDATA propdata,
SCIP_EVENTHDLR eventhdlr,
SCIP_VAR var 
)
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
scipSCIP data structure
propdatapropagator data
eventhdlrevent handler for global bound change events
varvariable for which the event should be dropped

Definition at line 542 of file prop_pseudoobj.c.

References dropObjEvent(), NULL, SCIP_CALL, SCIP_EVENTTYPE_GLBCHANGED, SCIP_EVENTTYPE_GUBCHANGED, SCIP_OKAY, SCIP_Real, SCIPcatchVarEvent(), SCIPisZero(), and SCIPvarGetObj().

static SCIP_RETCODE dropObjEvent ( SCIP scip,
SCIP_PROPDATA propdata,
SCIP_EVENTHDLR eventhdlr,
SCIP_VAR var 
)
static

drop variable event w.r.t. objective coefficient

Parameters
scipSCIP data structure
propdatapropagator data
eventhdlrevent handler for global bound change events
varvariable for which the event should be dropped

Definition at line 573 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().

static SCIP_RETCODE dropVarEvents ( SCIP scip,
SCIP_PROPDATA propdata 
)
static

drop all variable events

Parameters
scipSCIP data structure
propdatapropagator data

Definition at line 604 of file prop_pseudoobj.c.

Referenced by dropObjEvent().

static void propdataReset ( SCIP scip,
SCIP_PROPDATA propdata 
)
static

reset propagatore data structure

Parameters
scipSCIP data structure
propdatapropagator data

Definition at line 667 of file prop_pseudoobj.c.

static SCIP_RETCODE propdataExit ( SCIP scip,
SCIP_PROPDATA propdata 
)
static

free propagator data

Parameters
scipSCIP data structure
propdatapropagator data

Definition at line 697 of file prop_pseudoobj.c.

Referenced by SCIP_DECL_PROPEXEC(), and SCIP_DECL_PROPEXITSOL().

static SCIP_Real getVarObjchg ( SCIP_VAR var,
SCIP_BOUNDTYPE  boundtype,
SCIP_BOUNDTYPE  bound 
)
static

returns the objective change for the given binary variable

Parameters
varvariable to get objective change for
boundtypebound type to consider
boundfixing bound

Definition at line 733 of file prop_pseudoobj.c.

Referenced by adjustCutoffbound(), collectMinactObjchg(), collectMinactVar(), getMaxactObjchg(), and getMinactObjchg().

static SCIP_Real collectMinactImplicVar ( SCIP scip,
SCIP_VAR var,
SCIP_HASHMAP binobjvarmap,
SCIP_Bool collectedvars,
int  nbinobjvars,
SCIP_VAR **  contributors,
int *  ncontributors 
)
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
scipSCIP data structure
varvariable to computes the objective contribution
binobjvarmaphash map mapping binary variables with none-zero objective to position in collected variables arrays
collectedvarstemporary buffer to mark collected variables
nbinobjvarsnumber of binary variables with non-zero objective coefficient
contributorsarray to store the contributors
ncontributorspointer to store number of contributor to the objective contribution

Definition at line 752 of file prop_pseudoobj.c.

References NULL, REALABS, SCIP_Real, SCIPhashmapExists(), SCIPhashmapGetImage(), SCIPisZero(), SCIPvarGetLbGlobal(), SCIPvarGetObj(), SCIPvarGetUbGlobal(), and TRUE.

Referenced by collectMinactImplicVars().

static SCIP_RETCODE collectMinactImplicVars ( SCIP scip,
SCIP_VAR var,
SCIP_BOUNDTYPE  bound,
SCIP_HASHMAP binobjvarmap,
SCIP_Bool collectedvars,
int  nbinobjvars,
SCIP_VAR **  contributors,
SCIP_HASHTABLE uselesscliques,
int *  ncontributors,
SCIP_Real objchg 
)
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
scipSCIP data structure
varvariable to computes the objective contribution
boundbound to check for
binobjvarmaphash map mapping binary variables with none-zero objective to position in collected variables arrays
collectedvarstemporary buffer to mark collected variables
nbinobjvarsnumber of binary variables with non-zero objective coefficient
contributorsarray to store the contributors
uselesscliqueshash table to store useless cliques, or NULL
ncontributorspointer to store number of contributor to the objective contribution
objchgpointer to store the objective change

Definition at line 819 of file prop_pseudoobj.c.

References collectMinactImplicVar(), FALSE, getMinactImplicObjchg(), MAX_CLIQUELENGTH, NULL, SCIP_Bool, SCIP_BOUNDTYPE_LOWER, SCIP_BOUNDTYPE_UPPER, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPcliqueGetNVars(), SCIPcliqueGetValues(), SCIPcliqueGetVars(), SCIPhashtableExists(), SCIPhashtableInsert(), SCIPisZero(), SCIPvarGetBestBoundType(), SCIPvarGetCliques(), SCIPvarGetLbGlobal(), SCIPvarGetNCliques(), SCIPvarGetObj(), SCIPvarGetUbGlobal(), SCIPvarIsBinary(), and TRUE.

Referenced by collectMinactObjchg().

static SCIP_RETCODE getMinactImplicObjchg ( SCIP scip,
SCIP_VAR var,
SCIP_OBJIMPLICS objimplics,
SCIP_BDCHGIDX bdchgidx,
SCIP_BOUNDTYPE  bound,
SCIP_Bool  local,
SCIP_Real objchg 
)
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
scipSCIP data structure
varvariable to computes the objective contribution
objimplicsobjective implication data for the given variable
bdchgidxbound change index representing time on path to current node, or NULL
boundbound to check for
localpropagate local bounds, otherwise global bounds
objchgpointer to store the objective change

Definition at line 945 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, SCIPisZero(), SCIPvarGetLbAtIndex(), SCIPvarGetLbGlobal(), SCIPvarGetObj(), SCIPvarGetUbAtIndex(), SCIPvarGetUbGlobal(), SCIPvarIsBinary(), SCIPvarsHaveCommonClique(), and TRUE.

Referenced by collectMinactImplicVars(), and getMinactObjchg().

static SCIP_RETCODE collectMinactObjchg ( SCIP scip,
SCIP_VAR var,
SCIP_BOUNDTYPE  bound,
SCIP_HASHMAP binobjvarmap,
SCIP_Bool collectedvars,
int  nbinobjvars,
SCIP_VAR **  contributors,
SCIP_HASHTABLE uselesscliques,
int *  ncontributors,
SCIP_Real objchg 
)
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
scipSCIP data structure
varvariable to computes the objective contribution
boundbound to check for
binobjvarmaphash map mapping binary variables with none-zero objective to position in collected variables arrays
collectedvarstemporary buffer to mark collected variables
nbinobjvarsnumber of binary variables with non-zero objective coefficient
contributorsarray to store the contriboters
uselesscliqueshash table to store useless cliques, or NULL
ncontributorspointer to store number of contributor to the objective contribution
objchgpointer to store the objective change

Definition at line 1030 of file prop_pseudoobj.c.

References collectMinactImplicVars(), getMinactObjchg(), getVarObjchg(), NULL, SCIP_CALL, SCIP_OKAY, SCIPvarGetBestBoundType(), and SCIPvarIsBinary().

Referenced by collectMinactVar(), and getMinactImplicObjchg().

static SCIP_RETCODE getMinactObjchg ( SCIP scip,
SCIP_VAR var,
SCIP_OBJIMPLICS objimplics,
SCIP_BDCHGIDX bdchgidx,
SCIP_BOUNDTYPE  bound,
SCIP_Bool  local,
SCIP_Real objchg 
)
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
scipSCIP data structure
varvariable to computes the objective contribution
objimplicsobjective implication data for the given variable
bdchgidxbound change index representing time on path to current node, or NULL
boundbound to check for
localpropagate local bounds, otherwise global bounds
objchgpointer to store the objective change

Definition at line 1063 of file prop_pseudoobj.c.

References getMaxactImplicObjchg(), getMinactImplicObjchg(), getVarObjchg(), SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPvarGetBestBoundType(), and SCIPvarIsBinary().

Referenced by collectMinactObjchg(), and propagateCutoffboundBinvar().

static SCIP_RETCODE getMaxactImplicObjchg ( SCIP scip,
SCIP_VAR var,
SCIP_BOUNDTYPE  bound,
SCIP_Real objchg 
)
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
scipSCIP data structure
varvariable to computes the objective contribution
boundbound to check for
objchgpointer to store the objective change

Definition at line 1099 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(), SCIPdebugMessage, 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 SCIP_RETCODE getMaxactObjchg ( SCIP scip,
SCIP_VAR var,
SCIP_BOUNDTYPE  bound,
SCIP_Bool  useimplics,
SCIP_Real objchg 
)
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
scipSCIP data structure
varvariable to computes the objective contribution
boundbound to check for
useimplicsshould implications be used
objchgpointer to store the objective change

Definition at line 1289 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().

static void resetContributors ( SCIP_HASHMAP binobjvarmap,
SCIP_Bool collectedvars,
SCIP_VAR **  contributors,
int  ncontributors 
)
static

reset variables array which marks variables which are collected

Parameters
binobjvarmaphash map mapping binary variables with none-zero objective to position in collected variables arrays
collectedvarstemporary buffer to mark collected variables which should be reset
contributorstemporary buffer to use for collecting contributors
ncontributorsnumber of contributors

Definition at line 1318 of file prop_pseudoobj.c.

References collectMinactVar(), FALSE, NULL, SCIP_Bool, SCIPhashmapExists(), and SCIPhashmapGetImage().

Referenced by collectMinactVar(), and getMaxactObjchg().

static SCIP_RETCODE collectMinactVar ( SCIP scip,
SCIP_VAR var,
SCIP_OBJIMPLICS **  objimplics,
SCIP_Bool  useimplics,
SCIP_HASHMAP binobjvarmap,
SCIP_Bool collectedlbvars,
SCIP_Bool collectedubvars,
int  nbinobjvars,
SCIP_VAR **  contributors,
SCIP_HASHTABLE uselesscliques,
SCIP_Bool collect 
)
static

check if the given variable should be collected for the minimum activity propagation

Parameters
scipSCIP data structure
varvariable to check
objimplicspointer to store the objective implication data structure w.r.t. minimum activity
useimplicsshould implications be used
binobjvarmaphash map mapping binary variables with none-zero objective to position in collected variables arrays
collectedlbvarstemporary buffer to mark collected variables for lower bound fixing
collectedubvarstemporary buffer to mark collected variables for upper bound fixing
nbinobjvarsnumber of binary variables with non-zero objective coefficient
contributorstemporary buffer to use for collecting contributors
uselesscliqueshash table to store useless cliques, or NULL
collectpointer to store if the variable should be stored

Definition at line 1343 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, SCIPdebugMessage, SCIPisNegative(), SCIPisZero(), SCIPvarGetBestBoundType(), SCIPvarGetName(), SCIPvarGetNCliques(), SCIPvarGetObj(), and TRUE.

Referenced by resetContributors().

static SCIP_RETCODE collectMaxactVar ( SCIP scip,
SCIP_VAR var,
SCIP_Bool  useimplics,
SCIP_Real objchg,
SCIP_Bool isnotzero 
)
static

check if the given variable should be collected for the maximum activity propagation

Parameters
scipSCIP data structure
varvariable to check
useimplicsshould implications be used
objchgpointer to store the objective change w.r.t. maximum activity
isnotzeropointer to store if the objective change is unequal to zero or not

Definition at line 1459 of file prop_pseudoobj.c.

References FALSE, getMaxactObjchg(), MIN, NULL, propdataInit(), SCIP_BOUNDTYPE_LOWER, SCIP_BOUNDTYPE_UPPER, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPisPositive(), SCIPisZero(), SCIPvarIsBinary(), and TRUE.

Referenced by collectMinactVar().

static SCIP_RETCODE propdataInit ( SCIP scip,
SCIP_PROPDATA propdata 
)
static

initializate the propagator

Parameters
scipSCIP data structure
propdatapropagator data

Definition at line 1496 of file prop_pseudoobj.c.

Referenced by collectMaxactVar(), and SCIP_DECL_PROPEXEC().

static SCIP_RETCODE addConflictBounds ( SCIP scip,
SCIP_VAR var,
SCIP_BDCHGIDX bdchgidx,
SCIP_Real reqpseudoobjval 
)
static

adds for the given none binary variable a conflict bound depending on its objective contribution

Parameters
scipSCIP data structure
varvariable to check for objective contribution
bdchgidxbound change index (time stamp of bound change), or NULL for current time
reqpseudoobjvalpointer to store the remaining minimum activity which has to be proven

Definition at line 1801 of file prop_pseudoobj.c.

References FALSE, getConflictImplics(), SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPaddConflictLb(), SCIPaddConflictUb(), SCIPdebugMessage, SCIPisFeasGE(), SCIPisFeasLE(), SCIPisGT(), SCIPisLT(), SCIPisZero(), SCIPvarGetLbAtIndex(), SCIPvarGetLbGlobal(), SCIPvarGetName(), SCIPvarGetObj(), SCIPvarGetUbAtIndex(), and SCIPvarGetUbGlobal().

Referenced by resolvePropagation().

static SCIP_RETCODE getConflictImplics ( SCIP scip,
SCIP_VAR **  vars,
int  start,
int  end,
SCIP_BDCHGIDX bdchgidx,
SCIP_HASHTABLE addedvars,
SCIP_Real reqpseudoobjval,
SCIP_Bool foundimplics 
)
static

check for the given implication variables of they also contribute to the required minimum activity

Parameters
scipSCIP data structure
varsvariable to check for objective contribution
startstart index
endend index
bdchgidxbound change index (time stamp of bound change), or NULL for current time
addedvarshash table containing variables which are already add directly or implicitly due to implications
reqpseudoobjvalpointer to store the remaining minimum activity which has to be proven
foundimplicspointer to store if an implication is found

Definition at line 1861 of file prop_pseudoobj.c.

References addConflictBinvar(), FALSE, NULL, REALABS, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPdebugMessage, SCIPhashtableExists(), SCIPhashtableInsert(), SCIPvarGetLbAtIndex(), SCIPvarGetName(), SCIPvarGetObj(), SCIPvarGetUbAtIndex(), SCIPvarIsBinary(), and TRUE.

Referenced by addConflictBinvar(), addConflictBounds(), and adjustCutoffbound().

static SCIP_RETCODE addConflictBinvar ( SCIP scip,
SCIP_VAR var,
SCIP_BDCHGIDX bdchgidx,
SCIP_OBJIMPLICS objimplics,
SCIP_HASHTABLE addedvars,
SCIP_Bool  respropuseimplics,
SCIP_Real reqpseudoobjval 
)
static

adds for the given binary variable a conflict bound depending on its objective contribution

Parameters
scipSCIP data structure
varvariable to check for objective contribution
bdchgidxbound change index (time stamp of bound change), or NULL for current time
objimplicsobjective implication data for the given variable
addedvarshash table containing variables which are already add directly or implicitly due to implications
respropuseimplicsshould implications be used
reqpseudoobjvalpointer to store the remaining minimum activity which has to be proven

Definition at line 1905 of file prop_pseudoobj.c.

References adjustCutoffbound(), FALSE, getConflictImplics(), MAX, MIN, SCIP_ObjImplics::nlbimpls, SCIP_ObjImplics::nubimpls, NULL, SCIP_ObjImplics::objvars, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPaddConflictLb(), SCIPaddConflictUb(), SCIPdebugMessage, SCIPhashtableExists(), SCIPhashtableInsert(), SCIPisNegative(), SCIPisPositive(), SCIPvarGetLbAtIndex(), SCIPvarGetLbGlobal(), SCIPvarGetName(), SCIPvarGetObj(), SCIPvarGetUbAtIndex(), SCIPvarGetUbGlobal(), and SCIPvarIsBinary().

Referenced by getConflictImplics(), and resolvePropagation().

static SCIP_RETCODE adjustCutoffbound ( SCIP scip,
SCIP_PROPDATA propdata,
SCIP_VAR var,
int  inferinfo,
SCIP_BOUNDTYPE  boundtype,
SCIP_BDCHGIDX bdchgidx,
SCIP_HASHTABLE addedvars,
SCIP_Real cutoffbound 
)
static

resolves a propagation by supplying the variables whose bound changes increased the pseudo objective value above the cutoff bound

Parameters
scipSCIP data structure
propdatapropagator data
varvariable that was deduced
inferinfoinference information
boundtypethe type of the changed bound (lower or upper bound)
bdchgidxbound change index (time stamp of bound change), or NULL for current time
addedvarshash table which contains variable which are already added or implict given as reason for the resolve, or NULL
cutoffboundpointer to store the adjusted cutoff bound

Definition at line 1991 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(), SCIPisEQ(), SCIPisNegative(), SCIPisZero(), SCIPvarGetBestBoundType(), SCIPvarGetLbAtIndex(), SCIPvarGetLbGlobal(), SCIPvarGetObj(), SCIPvarGetUbAtIndex(), SCIPvarGetUbGlobal(), SCIPvarIsBinary(), SCIPvarIsIntegral(), and TRUE.

Referenced by addConflictBinvar(), and resolvePropagation().

static SCIP_RETCODE resolvePropagation ( SCIP scip,
SCIP_PROPDATA propdata,
SCIP_Real  cutoffbound,
SCIP_VAR infervar,
int  inferinfo,
SCIP_BOUNDTYPE  boundtype,
SCIP_BDCHGIDX bdchgidx 
)
static

resolves a propagation by supplying the variables whose bound changes increased the pseudo objective value above the cutoff bound

Parameters
scipSCIP data structure
propdatapropagator data
cutoffboundthe global cutoff
infervarvariable that was deduced, or NULL for conflict analysis initialization
inferinfoinference information
boundtypethe type of the changed bound (lower or upper bound)
bdchgidxbound change index (time stamp of bound change), or NULL for current time

Definition at line 2085 of file prop_pseudoobj.c.

References addConflictBinvar(), addConflictBounds(), adjustCutoffbound(), checkGlbfirstnonfixed(), FALSE, NULL, propagateCutoffboundVar(), SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPdebugMessage, SCIPgetGlobalPseudoObjval(), SCIPhashtableExists(), SCIPhashtableRemoveAll(), SCIPisInfinity(), SCIPisPositive(), SCIPisZero(), SCIPvarGetObj(), and TRUE.

Referenced by adjustCutoffbound(), and propagateCutoffboundBinvar().

static SCIP_RETCODE propagateCutoffboundVar ( SCIP scip,
SCIP_PROP prop,
SCIP_VAR var,
int  inferinfo,
SCIP_Real  objchg,
SCIP_Real  cutoffbound,
SCIP_Real  pseudoobjval,
SCIP_Bool  local,
SCIP_Bool tightened 
)
static

propagates the given variable against the cutoff bound

Parameters
scipSCIP data structure
proppropagator, or NULL
varvariable to propagate
inferinfoinference information to store with the bound change
objchgobjective change
cutoffboundcutoff bound to use
pseudoobjvalpseudo objective value to use
locallocal or global propagation
tightenedpointer to store if the variable domain was tightened

Definition at line 2231 of file prop_pseudoobj.c.

References FALSE, NULL, propagateCutoffboundBinvar(), SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPdebugMessage, SCIPinferVarLbProp(), SCIPinferVarUbProp(), SCIPisFeasEQ(), SCIPisInfinity(), SCIPisLT(), SCIPisZero(), SCIPtightenVarLbGlobal(), SCIPtightenVarUbGlobal(), SCIPvarGetLbGlobal(), SCIPvarGetLbLocal(), SCIPvarGetName(), SCIPvarGetUbGlobal(), and SCIPvarGetUbLocal().

Referenced by propagateCutoffboundBinvar(), propagateCutoffboundGlobally(), resolvePropagation(), and SCIPpropagateCutoffboundVar().

static SCIP_RETCODE propagateCutoffboundBinvar ( SCIP scip,
SCIP_PROP prop,
SCIP_VAR var,
int  pos,
SCIP_Real  cutoffbound,
SCIP_Real  pseudoobjval,
SCIP_Bool tightened,
SCIP_Bool cutoff,
SCIP_Bool  local 
)
static

propagates the given binary variable against the cutoff bound

Parameters
scipSCIP data structure
proppropagator, or NULL
varvariable to propagate
posposition of the variable in the corresponding propdata variable array
cutoffboundcutoff bound to use
pseudoobjvalpseudo objective value to use
tightenedpointer to store if the variable domain was tightened
cutoffpointer to store if a cutoff was detected
localpropagate local bounds, otherwise global bounds

Definition at line 2333 of file prop_pseudoobj.c.

References FALSE, getMinactObjchg(), NULL, propagateCutoffboundGlobally(), propagateCutoffboundVar(), resolvePropagation(), SCIP_Bool, SCIP_BOUNDTYPE_LOWER, SCIP_BOUNDTYPE_UPPER, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPanalyzeConflict(), SCIPgetDepth(), SCIPinitConflictAnalysis(), SCIPisConflictAnalysisApplicable(), SCIPisFeasLT(), SCIPisNegative(), SCIPisZero(), SCIPpropGetData(), SCIPvarIsBinary(), and TRUE.

Referenced by propagateCutoffboundBinvars(), propagateCutoffboundGlobally(), and propagateCutoffboundVar().

static SCIP_RETCODE propagateCutoffboundGlobally ( SCIP scip,
SCIP_PROP prop,
int *  nchgbds,
SCIP_Bool cutoff 
)
static

globally propagates if a new cutoff bound or global pseudo objective value (minimum activity of the objective function) is available

Parameters
scipSCIP data structure
proppropagator
nchgbdspointer to store the number of bound changes
cutoffpointer to store if a cutoff was detected

Definition at line 2417 of file prop_pseudoobj.c.

References checkGlbfirstnonfixed(), FALSE, MAX, NULL, propagateCutoffboundBinvar(), propagateCutoffboundBinvars(), propagateCutoffboundVar(), SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPdebugMessage, SCIPgetDepth(), SCIPgetGlobalPseudoObjval(), SCIPisGE(), SCIPisInfinity(), SCIPisZero(), SCIPpropGetData(), SCIPvarGetLbGlobal(), SCIPvarGetObj(), SCIPvarGetUbGlobal(), and TRUE.

Referenced by propagateCutoffboundBinvar().

static SCIP_RETCODE propagateCutoffboundBinvars ( SCIP scip,
SCIP_PROP prop,
SCIP_Real  cutoffbound,
SCIP_Real  pseudoobjval,
int *  nfixedvars,
SCIP_Bool cutoff 
)
static

propagates the cutoff bound for binary variables (c*x <= cutoff)

Parameters
scipSCIP data structure
proppropagator
cutoffboundcutoff bound to use
pseudoobjvalpseudo objective value to use
nfixedvarspointer to store the number of fixed variables
cutoffpointer to store if a cutoff was detected

Definition at line 2574 of file prop_pseudoobj.c.

References checkGlbfirstnonfixed(), FALSE, NULL, propagateCutoffbound(), propagateCutoffboundBinvar(), SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIPdebugMessage, SCIPpropGetData(), SCIPvarGetLbLocal(), SCIPvarGetUbLocal(), and TRUE.

Referenced by propagateCutoffboundGlobally().

static SCIP_RETCODE propagateCutoffbound ( SCIP scip,
SCIP_PROP prop,
SCIP_RESULT result 
)
static

propagates the cutoff bound c*x <= cutoff

Parameters
scipSCIP data structure
proppropagator
resultpointer to store the result of the callback method

Definition at line 2707 of file prop_pseudoobj.c.

Referenced by propagateCutoffboundBinvars(), and SCIP_DECL_PROPEXEC().

static void calcMaxObjPseudoactivity ( SCIP scip,
SCIP_PROPDATA propdata 
)
static

recalculates the maximum objective pseudoactivity

Parameters
scipSCIP data structure
propdatapropagator data

Definition at line 2903 of file prop_pseudoobj.c.

static void updateMaxObjPseudoactivity ( SCIP scip,
SCIP_PROPDATA propdata 
)
static

updates the pseudo objective activity if necessary

Parameters
scipSCIP data structure
propdatapropagator data

Definition at line 2953 of file prop_pseudoobj.c.

static SCIP_Real getMaxObjPseudoactivityResidualValue ( SCIP scip,
SCIP_PROPDATA propdata,
SCIP_Real  contrib 
)
static

returns the residual pseudo objective activity without the given value

Parameters
scipSCIP data structure
propdatapropagator data
contribvalue to eliminate from pseudo objective activity

Definition at line 2968 of file prop_pseudoobj.c.

static SCIP_Real getMaxObjPseudoactivityResidual ( SCIP scip,
SCIP_PROPDATA propdata,
SCIP_VAR var 
)
static

returns the residual pseudo objective activity

Parameters
scipSCIP data structure
propdatapropagator data
varvariable to get residual activity for

Definition at line 3006 of file prop_pseudoobj.c.

Referenced by propagateLowerboundVar().

static SCIP_Real getMaxObjPseudoactivity ( SCIP scip,
SCIP_PROPDATA propdata 
)
static

returns the maximum pseudo objective activity of the objective function

Parameters
scipSCIP data structure
propdatapropagator data

Definition at line 3040 of file prop_pseudoobj.c.

static SCIP_RETCODE propagateLowerboundBinvar ( SCIP scip,
SCIP_VAR var,
SCIP_Real  lowerbound,
SCIP_Real  maxpseudoobjact,
SCIP_Bool  useimplics,
SCIP_Bool infeasible,
SCIP_Bool tightened 
)
static

propagates the global domain of the given binary variable against the lower bound (c*x >= lowerbound)

Parameters
scipSCIP data structure
varvariable to propagate
lowerboundlower bound to use
maxpseudoobjactmaximum pseudo objective activity
useimplicsshould implications be used
infeasiblepointer to store if the variable domain got empty, infeasible
tightenedpointer to store if the variable domain was tightened

Definition at line 3050 of file prop_pseudoobj.c.

References FALSE, getMaxactObjchg(), propagateLowerboundVar(), SCIP_Bool, SCIP_BOUNDTYPE_LOWER, SCIP_BOUNDTYPE_UPPER, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPisFeasLT(), SCIPisInfinity(), SCIPisLE(), SCIPisPositive(), SCIPtightenVarLbGlobal(), SCIPvarIsBinary(), and TRUE.

static SCIP_RETCODE propagateLowerboundVar ( SCIP scip,
SCIP_PROPDATA propdata,
SCIP_VAR var,
SCIP_Real  lowerbound,
SCIP_Bool infeasible,
SCIP_Bool tightened 
)
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
scipSCIP data structure
propdatapropagator data
varvariable to propagate
lowerboundlower bound to use
infeasiblepointer to store if the variable domain got empty, infeasible
tightenedpointer to store if the variable domain was tightened

Definition at line 3108 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 SCIP_RETCODE propagateLowerbound ( SCIP scip,
SCIP_PROP prop,
SCIP_RESULT result 
)
static

propagates the global lower (dual) bound c*x >= lowerbound

Parameters
scipSCIP data structure
proppropagator
resultpointer to store the result of the callback method

Definition at line 3173 of file prop_pseudoobj.c.

Referenced by propagateLowerboundVar(), and SCIP_DECL_PROPEXEC().

static SCIP_DECL_PROPCOPY ( propCopyPseudoobj  )
static

copy method for propagator plugins (called when SCIP copies plugins)

Definition at line 3374 of file prop_pseudoobj.c.

static SCIP_DECL_PROPFREE ( propFreePseudoobj  )
static

destructor of propagator to free user data (called when SCIP is exiting)

Definition at line 3388 of file prop_pseudoobj.c.

static SCIP_DECL_PROPINITSOL ( propInitsolPseudoobj  )
static

solving process initialization method of propagator (called when branch and bound process is about to begin)

Definition at line 3403 of file prop_pseudoobj.c.

References NULL, SCIP_CALL, SCIP_DECL_PROPEXITSOL(), SCIP_EVENTTYPE_VARADDED, SCIP_OKAY, SCIPcatchEvent(), SCIPpropGetData(), and TRUE.

static SCIP_DECL_PROPEXITSOL ( propExitsolPseudoobj  )
static

solving process deinitialization method of propagator (called before branch and bound process data is freed)

Definition at line 3427 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 SCIP_DECL_PROPPRESOL ( propPresolPseudoobj  )
static

presolving method of propagator

Definition at line 3450 of file prop_pseudoobj.c.

Referenced by SCIP_DECL_PROPEXITSOL().

static SCIP_DECL_PROPRESPROP ( propRespropPseudoobj  )
static

propagation conflict resolving method of propagator

Definition at line 3590 of file prop_pseudoobj.c.

Referenced by SCIP_DECL_PROPEXEC().

static SCIP_DECL_EVENTEXEC ( eventExecPseudoobj  )
static

execution method of bound change event handler

Definition at line 3623 of file prop_pseudoobj.c.

SCIP_RETCODE SCIPincludePropPseudoobj ( SCIP scip)

creates the pseudo objective function propagator and includes it in SCIP

Parameters
scipSCIP data structure

Definition at line 3665 of file prop_pseudoobj.c.

Referenced by SCIPincludeDefaultPlugins().

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

References propagateCutoffboundVar(), SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPvarGetObj(), and TRUE.