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

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 "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
 

Functions

static void checkImplicsApplied (SCIP *scip, SCIP_VAR *var)
 
static void checkGlbfirstnonfixed (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_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

◆ 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

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

◆ EVENTHDLR_NAME

#define EVENTHDLR_NAME   "pseudoobj"

Definition at line 79 of file prop_pseudoobj.c.

◆ EVENTHDLR_DESC

#define EVENTHDLR_DESC   "bound change event handler for pseudo objective function propagator"

Definition at line 80 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 82 of file prop_pseudoobj.c.

Referenced by SCIPincludePropPseudoobj().

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

Referenced by SCIPincludePropPseudoobj().

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

Referenced by SCIPincludePropPseudoobj().

◆ DEFAULT_PROPCUTOFFBOUND

#define DEFAULT_PROPCUTOFFBOUND   TRUE

propagate new cutoff bound directly globally

Definition at line 87 of file prop_pseudoobj.c.

Referenced by SCIPincludePropPseudoobj().

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

Referenced by SCIPincludePropPseudoobj(), SCIPincludePropRedcost(), and SCIPincludePropRootredcost().

◆ DEFAULT_MAXNEWVARS

#define DEFAULT_MAXNEWVARS   1000

number of variable added after the propagator is reinitialized?

Definition at line 92 of file prop_pseudoobj.c.

Referenced by SCIPincludePropPseudoobj().

◆ DEFAULT_PROPUSEIMPLICS

#define DEFAULT_PROPUSEIMPLICS   TRUE

use implications to strengthen the propagation of binary variable (increasing the objective change)?

Definition at line 93 of file prop_pseudoobj.c.

Referenced by SCIPincludePropPseudoobj().

◆ DEFAULT_RESPROPUSEIMPLICS

#define DEFAULT_RESPROPUSEIMPLICS   TRUE

use implications to strengthen the resolve propagation of binary variable (increasing the objective change)?

Definition at line 94 of file prop_pseudoobj.c.

Referenced by SCIPincludePropPseudoobj().

◆ DEFAULT_MAXIMPLVARS

#define DEFAULT_MAXIMPLVARS   50000

maximum number of binary variables the implications are used if turned on (-1: unlimited)?

Definition at line 95 of file prop_pseudoobj.c.

Referenced by SCIPincludePropPseudoobj().

◆ MAX_CLIQUELENGTH

#define MAX_CLIQUELENGTH   50

Definition at line 833 of file prop_pseudoobj.c.

Typedef Documentation

◆ SCIP_OBJIMPLICS

implications in the form x == 0 or x == 1 ==> y == 0 or y == 1 for (x and y binary)

Definition at line 112 of file prop_pseudoobj.c.

Function Documentation

◆ checkImplicsApplied()

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

References assert(), nvars, SCIP_Bool, SCIP_BOUNDTYPE_LOWER, SCIP_BOUNDTYPE_UPPER, SCIP_Real, SCIPisGE(), SCIPisLE(), SCIPvarGetImplBounds(), SCIPvarGetImplTypes(), SCIPvarGetImplVars(), SCIPvarGetLbGlobal(), SCIPvarGetLbLocal(), SCIPvarGetNImpls(), SCIPvarGetUbLocal(), var, and vars.

Referenced by propdataInit().

◆ checkGlbfirstnonfixed()

static void checkGlbfirstnonfixed ( SCIP_PROPDATA * propdata)
static

check if the global fixed indices are correct

Parameters
propdatapropagator data

Definition at line 215 of file prop_pseudoobj.c.

References assert(), NULL, SCIPvarGetLbGlobal(), SCIPvarGetUbGlobal(), and var.

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

◆ SCIP_DECL_SORTPTRCOMP() [1/2]

static SCIP_DECL_SORTPTRCOMP ( objimplicsComp )
static

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

Definition at line 246 of file prop_pseudoobj.c.

References SCIP_ObjImplics::maxobjchg.

◆ SCIP_DECL_SORTPTRCOMP() [2/2]

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

References assert(), REALABS, SCIP_LOCKTYPE_MODEL, SCIPvarCompare(), SCIPvarGetNLocksDownType(), SCIPvarGetNLocksUpType(), and SCIPvarGetObj().

◆ SCIP_DECL_HASHGETKEY()

static SCIP_DECL_HASHGETKEY ( cliqueGetHashkey )
static

hash key retrieval function for cliques

Definition at line 329 of file prop_pseudoobj.c.

◆ SCIP_DECL_HASHKEYEQ()

static SCIP_DECL_HASHKEYEQ ( cliqueIsHashkeyEq )
static

returns TRUE iff the cliques are equal

Definition at line 336 of file prop_pseudoobj.c.

References FALSE, and TRUE.

◆ SCIP_DECL_HASHKEYVAL()

static SCIP_DECL_HASHKEYVAL ( cliqueGetHashkeyVal )
static

returns the hash value of the key

Definition at line 345 of file prop_pseudoobj.c.

References SCIPcliqueGetId().

◆ objimplicsCreate()

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

References assert(), FALSE, MAX, NULL, nvars, SCIP_Bool, SCIP_BOUNDTYPE_LOWER, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBlockMemory, SCIPallocBlockMemoryArray, SCIPcaptureVar(), SCIPdebugMsg, SCIPhashmapExists(), SCIPhashmapGetImageInt(), SCIPisNegative(), SCIPisZero(), SCIPtightenVarLbGlobal(), SCIPtightenVarUbGlobal(), SCIPvarGetBestBoundType(), SCIPvarGetLbGlobal(), SCIPvarGetName(), SCIPvarGetObj(), SCIPvarGetUbGlobal(), SCIPvarIsBinary(), and var.

Referenced by collectMinactVar().

◆ objimplicsFree()

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

References assert(), NULL, SCIP_CALL, SCIP_OKAY, SCIPfreeBlockMemory, SCIPfreeBlockMemoryArrayNull, and SCIPreleaseVar().

Referenced by propdataExit().

◆ objimplicsDelPos()

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

References assert(), SCIP_ObjImplics::nlbimpls, SCIP_ObjImplics::nubimpls, SCIP_ObjImplics::objvars, SCIP_CALL, SCIP_OKAY, SCIPdebugMsg, SCIPdebugMsgPrint, SCIPreleaseVar(), and SCIPvarGetName().

Referenced by getMinactImplicObjchg().

◆ catchObjEvent()

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

References assert(), NULL, objval, SCIP_CALL, SCIP_EVENTTYPE_GLBCHANGED, SCIP_EVENTTYPE_GUBCHANGED, SCIP_OKAY, SCIP_Real, SCIPcatchVarEvent(), SCIPisZero(), SCIPvarGetObj(), and var.

Referenced by propdataInit().

◆ dropObjEvent()

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

References assert(), NULL, objval, SCIP_CALL, SCIP_EVENTTYPE_GLBCHANGED, SCIP_EVENTTYPE_GUBCHANGED, SCIP_OKAY, SCIP_Real, SCIPdropVarEvent(), SCIPisZero(), SCIPvarGetObj(), and var.

Referenced by dropVarEvents().

◆ dropVarEvents()

static SCIP_RETCODE dropVarEvents ( SCIP * scip,
SCIP_PROPDATA * propdata )
static

drop all variable events

Parameters
scipSCIP data structure
propdatapropagator data

Definition at line 633 of file prop_pseudoobj.c.

References assert(), dropObjEvent(), NULL, SCIP_CALL, SCIP_EVENTTYPE_BOUNDRELAXED, SCIP_OKAY, SCIPdropVarEvent(), SCIPreleaseVar(), SCIPvarIsBinary(), and var.

Referenced by propdataExit().

◆ propdataReset()

static void propdataReset ( SCIP_PROPDATA * propdata)
static

reset propagatore data structure

Parameters
propdatapropagator data

Definition at line 696 of file prop_pseudoobj.c.

References FALSE, NULL, and SCIP_INVALID.

Referenced by propdataExit(), and SCIPincludePropPseudoobj().

◆ propdataExit()

static SCIP_RETCODE propdataExit ( SCIP * scip,
SCIP_PROPDATA * propdata )
static

free propagator data

Parameters
scipSCIP data structure
propdatapropagator data

Definition at line 728 of file prop_pseudoobj.c.

References dropVarEvents(), NULL, objimplicsFree(), propdataReset(), SCIP_CALL, SCIP_OKAY, SCIPfreeBlockMemoryArrayNull, and SCIPhashtableFree().

Referenced by SCIP_DECL_PROPEXEC(), and SCIP_DECL_PROPEXITSOL().

◆ getVarObjchg()

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

References assert(), bound, SCIP_BOUNDTYPE_LOWER, SCIP_BOUNDTYPE_UPPER, SCIP_Real, SCIPvarGetObj(), SCIPvarIsBinary(), and var.

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

◆ collectMinactImplicVar()

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

References assert(), NULL, objval, REALABS, SCIP_Bool, SCIP_Real, SCIPhashmapExists(), SCIPhashmapGetImageInt(), SCIPisZero(), SCIPvarGetLbGlobal(), SCIPvarGetObj(), SCIPvarGetUbGlobal(), TRUE, and var.

Referenced by collectMinactImplicVars().

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

References assert(), bound, c, collectMinactImplicVar(), FALSE, MAX_CLIQUELENGTH, nbinvars, NULL, objval, 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(), TRUE, var, and vars.

Referenced by collectMinactObjchg().

◆ getMinactImplicObjchg()

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

References assert(), bound, FALSE, nbinvars, SCIP_ObjImplics::nlbimpls, SCIP_ObjImplics::nubimpls, NULL, objimplicsDelPos(), SCIP_ObjImplics::objvars, REALABS, SCIP_Bool, SCIP_BOUNDTYPE_LOWER, SCIP_BOUNDTYPE_UPPER, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPgetVarLbAtIndex(), SCIPgetVarUbAtIndex(), SCIPisZero(), SCIPvarGetLbGlobal(), SCIPvarGetObj(), SCIPvarGetUbGlobal(), SCIPvarIsBinary(), SCIPvarsHaveCommonClique(), TRUE, and var.

Referenced by getMinactObjchg().

◆ collectMinactObjchg()

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

References assert(), bound, collectMinactImplicVars(), getVarObjchg(), NULL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPvarGetBestBoundType(), SCIPvarIsBinary(), and var.

Referenced by collectMinactVar().

◆ getMinactObjchg()

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

References assert(), bound, getMinactImplicObjchg(), getVarObjchg(), SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPvarGetBestBoundType(), SCIPvarIsBinary(), and var.

Referenced by propagateCutoffboundBinvar().

◆ getMaxactImplicObjchg()

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

References ABS, assert(), BMSclearMemoryArray, bound, c, FALSE, MAX_CLIQUELENGTH, NULL, nvars, obj, 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(), TRUE, var, and vars.

Referenced by getMaxactObjchg().

◆ getMaxactObjchg()

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

References assert(), bound, getMaxactImplicObjchg(), getVarObjchg(), NULL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPvarGetWorstBoundType(), SCIPvarIsBinary(), and var.

Referenced by collectMaxactVar(), and propagateLowerboundBinvar().

◆ resetContributors()

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

References assert(), c, FALSE, NULL, SCIP_Bool, SCIPhashmapExists(), SCIPhashmapGetImageInt(), and var.

Referenced by collectMinactVar().

◆ collectMinactVar()

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

References assert(), collectMinactObjchg(), FALSE, getVarObjchg(), NULL, objimplicsCreate(), objval, resetContributors(), SCIP_Bool, SCIP_BOUNDTYPE_LOWER, SCIP_BOUNDTYPE_UPPER, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPdebugMsg, SCIPisNegative(), SCIPisZero(), SCIPvarGetBestBoundType(), SCIPvarGetName(), SCIPvarGetNCliques(), SCIPvarGetObj(), TRUE, and var.

Referenced by propdataInit().

◆ collectMaxactVar()

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

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

Referenced by propdataInit().

◆ propdataInit()

◆ addConflictBounds()

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

adds for the given non-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 1839 of file prop_pseudoobj.c.

References assert(), FALSE, objval, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPaddConflictLb(), SCIPaddConflictUb(), SCIPdebugMsg, SCIPgetVarLbAtIndex(), SCIPgetVarUbAtIndex(), SCIPisFeasGE(), SCIPisFeasLE(), SCIPisGT(), SCIPisLT(), SCIPisZero(), SCIPvarGetLbGlobal(), SCIPvarGetName(), SCIPvarGetObj(), SCIPvarGetUbGlobal(), and var.

Referenced by resolvePropagation().

◆ getConflictImplics()

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 if 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 added 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 1899 of file prop_pseudoobj.c.

References assert(), FALSE, NULL, REALABS, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPdebugMsg, SCIPgetVarLbAtIndex(), SCIPgetVarUbAtIndex(), SCIPhashtableExists(), SCIPhashtableInsert(), SCIPvarGetName(), SCIPvarGetObj(), SCIPvarIsBinary(), TRUE, var, and vars.

Referenced by addConflictBinvar(), and adjustCutoffbound().

◆ addConflictBinvar()

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

References assert(), FALSE, getConflictImplics(), MAX, MIN, SCIP_ObjImplics::nlbimpls, SCIP_ObjImplics::nubimpls, NULL, objval, SCIP_ObjImplics::objvars, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPaddConflictLb(), SCIPaddConflictUb(), SCIPdebugMsg, SCIPgetVarLbAtIndex(), SCIPgetVarUbAtIndex(), SCIPhashtableExists(), SCIPhashtableInsert(), SCIPisNegative(), SCIPisPositive(), SCIPvarGetLbGlobal(), SCIPvarGetName(), SCIPvarGetObj(), SCIPvarGetUbGlobal(), SCIPvarIsBinary(), and var.

Referenced by resolvePropagation().

◆ adjustCutoffbound()

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 variables which are already added or implicitly given as reason for the resolve, or NULL
cutoffboundpointer to store the adjusted cutoff bound

Definition at line 2034 of file prop_pseudoobj.c.

References assert(), FALSE, getConflictImplics(), getVarObjchg(), SCIP_ObjImplics::nlbimpls, SCIP_ObjImplics::nubimpls, NULL, objval, SCIP_ObjImplics::objvars, 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(), TRUE, and var.

Referenced by resolvePropagation().

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

References addConflictBinvar(), addConflictBounds(), adjustCutoffbound(), assert(), checkGlbfirstnonfixed(), FALSE, infinity, NULL, nvars, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPdebugMsg, SCIPgetGlobalPseudoObjval(), SCIPhashtableExists(), SCIPhashtableRemoveAll(), SCIPisInfinity(), SCIPisPositive(), SCIPisZero(), SCIPvarGetObj(), TRUE, var, and vars.

Referenced by propagateCutoffbound(), propagateCutoffboundBinvar(), and SCIP_DECL_PROPRESPROP().

◆ propagateCutoffboundVar()

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

References assert(), FALSE, NULL, 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(), SCIPvarGetUbLocal(), and var.

Referenced by propagateCutoffbound(), propagateCutoffboundBinvar(), propagateCutoffboundGlobally(), SCIP_DECL_PROPPRESOL(), and SCIPpropagateCutoffboundVar().

◆ propagateCutoffboundBinvar()

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

References assert(), cutoff, FALSE, getMinactObjchg(), NULL, propagateCutoffboundVar(), resolvePropagation(), SCIP_Bool, SCIP_BOUNDTYPE_LOWER, SCIP_BOUNDTYPE_UPPER, SCIP_CALL, SCIP_CONFTYPE_PROPAGATION, SCIP_OKAY, SCIP_Real, SCIPanalyzeConflict(), SCIPgetDepth(), SCIPinitConflictAnalysis(), SCIPisConflictAnalysisApplicable(), SCIPisLT(), SCIPisNegative(), SCIPisZero(), SCIPpropGetData(), SCIPvarIsBinary(), TRUE, and var.

Referenced by propagateCutoffboundBinvars(), and propagateCutoffboundGlobally().

◆ propagateCutoffboundGlobally()

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

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

Referenced by propagateCutoffbound().

◆ propagateCutoffboundBinvars()

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

References assert(), checkGlbfirstnonfixed(), cutoff, FALSE, NULL, propagateCutoffboundBinvar(), SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPdebugMsg, SCIPpropGetData(), SCIPvarGetLbLocal(), SCIPvarGetUbLocal(), TRUE, and var.

Referenced by propagateCutoffbound().

◆ propagateCutoffbound()

◆ calcMaxObjPseudoactivity()

static void calcMaxObjPseudoactivity ( SCIP * scip,
SCIP_PROPDATA * propdata )
static

recalculates the maximum objective pseudoactivity

Parameters
scipSCIP data structure
propdatapropagator data

Definition at line 2962 of file prop_pseudoobj.c.

References assert(), NULL, nvars, objval, SCIP_Real, SCIPgetNVars(), SCIPgetVars(), SCIPisInfinity(), SCIPisNegative(), SCIPisPositive(), SCIPvarGetLbGlobal(), SCIPvarGetObj(), SCIPvarGetUbGlobal(), and vars.

Referenced by getMaxObjPseudoactivityResidualValue(), and updateMaxObjPseudoactivity().

◆ updateMaxObjPseudoactivity()

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

References assert(), calcMaxObjPseudoactivity(), NULL, and SCIP_INVALID.

Referenced by propagateLowerbound().

◆ getMaxObjPseudoactivityResidualValue()

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

References assert(), calcMaxObjPseudoactivity(), NULL, SCIP_INVALID, SCIP_Real, SCIPinfinity(), and SCIPisInfinity().

Referenced by getMaxObjPseudoactivity(), and getMaxObjPseudoactivityResidual().

◆ getMaxObjPseudoactivityResidual()

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

References assert(), getMaxObjPseudoactivityResidualValue(), NULL, objval, SCIP_BOUNDTYPE_LOWER, SCIP_BOUNDTYPE_UPPER, SCIP_Real, SCIPisInfinity(), SCIPvarGetLbGlobal(), SCIPvarGetObj(), SCIPvarGetUbGlobal(), SCIPvarGetWorstBoundType(), and var.

Referenced by propagateLowerboundVar().

◆ getMaxObjPseudoactivity()

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

References getMaxObjPseudoactivityResidualValue(), and SCIP_Real.

Referenced by propagateLowerbound().

◆ propagateLowerboundBinvar()

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

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

Referenced by propagateLowerbound().

◆ propagateLowerboundVar()

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

References assert(), FALSE, getMaxObjPseudoactivityResidual(), objval, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPisFeasGT(), SCIPisFeasLT(), SCIPisInfinity(), SCIPisZero(), SCIPtightenVarLbGlobal(), SCIPtightenVarUbGlobal(), SCIPvarGetLbGlobal(), SCIPvarGetObj(), SCIPvarGetUbGlobal(), SCIPvarIsIntegral(), TRUE, and var.

Referenced by propagateLowerbound().

◆ propagateLowerbound()

◆ SCIP_DECL_PROPCOPY()

static SCIP_DECL_PROPCOPY ( propCopyPseudoobj )
static

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

Definition at line 3433 of file prop_pseudoobj.c.

References assert(), NULL, PROP_NAME, SCIP_CALL, SCIP_OKAY, SCIPincludePropPseudoobj(), and SCIPpropGetName().

◆ SCIP_DECL_PROPFREE()

static SCIP_DECL_PROPFREE ( propFreePseudoobj )
static

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

Definition at line 3447 of file prop_pseudoobj.c.

References NULL, SCIP_OKAY, SCIPfreeBlockMemory, SCIPpropGetData(), and SCIPpropSetData().

◆ SCIP_DECL_PROPINITSOL()

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

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

◆ SCIP_DECL_PROPEXITSOL()

static SCIP_DECL_PROPEXITSOL ( propExitsolPseudoobj )
static

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

Definition at line 3486 of file prop_pseudoobj.c.

References assert(), FALSE, NULL, propdataExit(), SCIP_CALL, SCIP_EVENTTYPE_VARADDED, SCIP_OKAY, SCIPdropEvent(), and SCIPpropGetData().

◆ SCIP_DECL_PROPPRESOL()

◆ SCIP_DECL_PROPEXEC()

◆ SCIP_DECL_PROPRESPROP()

static SCIP_DECL_PROPRESPROP ( propRespropPseudoobj )
static

◆ SCIP_DECL_EVENTEXEC()

static SCIP_DECL_EVENTEXEC ( eventExecPseudoobj )
static