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 "blockmemshell/memory.h"
#include "scip/prop_pseudoobj.h"
#include "scip/pub_event.h"
#include "scip/pub_implics.h"
#include "scip/pub_message.h"
#include "scip/pub_misc.h"
#include "scip/pub_misc_sort.h"
#include "scip/pub_prop.h"
#include "scip/pub_var.h"
#include "scip/scip_conflict.h"
#include "scip/scip_event.h"
#include "scip/scip_general.h"
#include "scip/scip_lp.h"
#include "scip/scip_mem.h"
#include "scip/scip_message.h"
#include "scip/scip_numerics.h"
#include "scip/scip_param.h"
#include "scip/scip_pricer.h"
#include "scip/scip_prob.h"
#include "scip/scip_probing.h"
#include "scip/scip_prop.h"
#include "scip/scip_solvingstats.h"
#include "scip/scip_tree.h"
#include "scip/scip_var.h"
#include "scip/dbldblarith.h"
#include <string.h>

Go to the source code of this file.

Data Structures
struct	SCIP_ObjImplics

Macros
#define	PROP_NAME   "pseudoobj"
#define	PROP_DESC   "pseudo objective function propagator"
#define	PROP_TIMING   SCIP_PROPTIMING_BEFORELP | SCIP_PROPTIMING_DURINGLPLOOP | SCIP_PROPTIMING_AFTERLPLOOP
#define	PROP_PRIORITY   3000000
#define	PROP_FREQ   1
#define	PROP_DELAY   FALSE
#define	PROP_PRESOL_PRIORITY   +6000000
#define	PROP_PRESOL_MAXROUNDS   -1
#define	PROP_PRESOLTIMING   SCIP_PRESOLTIMING_FAST /* timing of the presolving method (fast, medium, or exhaustive) */
#define	EVENTHDLR_NAME   "pseudoobj"
#define	EVENTHDLR_DESC   "bound change event handler for pseudo objective function propagator"
#define	DEFAULT_MINUSELESS   100
#define	DEFAULT_MAXVARSFRAC   0.1
#define	DEFAULT_PROPFULLINROOT   TRUE
#define	DEFAULT_PROPCUTOFFBOUND   TRUE
#define	DEFAULT_FORCE   FALSE
#define	DEFAULT_MAXNEWVARS   1000
#define	DEFAULT_PROPUSEIMPLICS   TRUE
#define	DEFAULT_RESPROPUSEIMPLICS   TRUE
#define	DEFAULT_MAXIMPLVARS   50000
#define	MAX_CLIQUELENGTH   50

Typedefs
typedef struct SCIP_ObjImplics	SCIP_OBJIMPLICS

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

#define PROP_TIMING   SCIP_PROPTIMING_BEFORELP | SCIP_PROPTIMING_DURINGLPLOOP | SCIP_PROPTIMING_AFTERLPLOOP

Definition at line 70 of file prop_pseudoobj.c.

PROP_PRIORITY

#define PROP_PRIORITY   3000000

propagator priority

Definition at line 71 of file prop_pseudoobj.c.

PROP_FREQ

#define PROP_FREQ   1

propagator frequency

Definition at line 72 of file prop_pseudoobj.c.

PROP_DELAY

#define PROP_DELAY   FALSE

should propagation method be delayed, if other propagators found reductions?

Definition at line 73 of file prop_pseudoobj.c.

PROP_PRESOL_PRIORITY

#define PROP_PRESOL_PRIORITY   +6000000

priority of the presolving method (>= 0: before, < 0: after constraint handlers); combined with presolvers

Definition at line 74 of file prop_pseudoobj.c.

PROP_PRESOL_MAXROUNDS

#define PROP_PRESOL_MAXROUNDS   -1

maximal number of presolving rounds the presolver participates in (-1: no limit)

Definition at line 75 of file prop_pseudoobj.c.

PROP_PRESOLTIMING

#define PROP_PRESOLTIMING   SCIP_PRESOLTIMING_FAST /* timing of the presolving method (fast, medium, or exhaustive) */

Definition at line 78 of file prop_pseudoobj.c.

EVENTHDLR_NAME

#define EVENTHDLR_NAME   "pseudoobj"

Definition at line 80 of file prop_pseudoobj.c.

EVENTHDLR_DESC

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

Definition at line 81 of file prop_pseudoobj.c.

DEFAULT_MINUSELESS

#define DEFAULT_MINUSELESS   100

minimal number of successive non-binary variable propagator whithout a bound reduction before aborted

Definition at line 83 of file prop_pseudoobj.c.

DEFAULT_MAXVARSFRAC

#define DEFAULT_MAXVARSFRAC   0.1

maximal fraction of non-binary variables with non-zero objective without a bound reduction before aborted

Definition at line 86 of file prop_pseudoobj.c.

DEFAULT_PROPFULLINROOT

#define DEFAULT_PROPFULLINROOT   TRUE

do we want to propagate all non-binary variables if we are propagating the root node?

Definition at line 89 of file prop_pseudoobj.c.

DEFAULT_PROPCUTOFFBOUND

#define DEFAULT_PROPCUTOFFBOUND   TRUE

propagate new cutoff bound directly globally

Definition at line 90 of file prop_pseudoobj.c.

DEFAULT_FORCE

#define DEFAULT_FORCE   FALSE

should the propagator be forced even if active pricer are present? Note that can be done if it is known that the pseudo objective activity is given by the zero bound for all variables which are currently not present in the problem

Definition at line 91 of file prop_pseudoobj.c.

DEFAULT_MAXNEWVARS

#define DEFAULT_MAXNEWVARS   1000

number of variable added after the propagator is reinitialized?

Definition at line 98 of file prop_pseudoobj.c.

DEFAULT_PROPUSEIMPLICS

#define DEFAULT_PROPUSEIMPLICS   TRUE

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

Definition at line 99 of file prop_pseudoobj.c.

DEFAULT_RESPROPUSEIMPLICS

#define DEFAULT_RESPROPUSEIMPLICS   TRUE

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

Definition at line 100 of file prop_pseudoobj.c.

DEFAULT_MAXIMPLVARS

#define DEFAULT_MAXIMPLVARS   50000

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

Definition at line 101 of file prop_pseudoobj.c.

MAX_CLIQUELENGTH

#define MAX_CLIQUELENGTH   50

Definition at line 839 of file prop_pseudoobj.c.

Referenced by collectMinactImplicVars(), and getMaxactImplicObjchg().

Typedef Documentation

SCIP_OBJIMPLICS

typedef struct SCIP_ObjImplics SCIP_OBJIMPLICS

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

Definition at line 118 of file prop_pseudoobj.c.

Function Documentation

checkImplicsApplied()

static void checkImplicsApplied ( SCIP *  scip, SCIP_VAR *  var  )

static

check that the implications are applied for a globally fixed variable

Parameters

scip	SCIP data structure
var	variable to check the implications

Definition at line 174 of file prop_pseudoobj.c.

checkGlbfirstnonfixed()

static void checkGlbfirstnonfixed ( SCIP_PROPDATA *  propdata )

static

check if the global fixed indices are correct

Parameters

propdata

propagator data

Definition at line 221 of file prop_pseudoobj.c.

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

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

SCIP_DECL_SORTPTRCOMP() [1/2]

static SCIP_DECL_SORTPTRCOMP ( objimplicsComp  )

static

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

Definition at line 252 of file prop_pseudoobj.c.

Referenced by checkGlbfirstnonfixed().

SCIP_DECL_SORTPTRCOMP() [2/2]

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

SCIP_DECL_HASHGETKEY()

static SCIP_DECL_HASHGETKEY ( cliqueGetHashkey  )

static

hash key retrieval function for cliques

Definition at line 335 of file prop_pseudoobj.c.

References FALSE, and TRUE.

SCIP_DECL_HASHKEYEQ()

static SCIP_DECL_HASHKEYEQ ( cliqueIsHashkeyEq  )

static

returns TRUE iff the cliques are equal

Definition at line 342 of file prop_pseudoobj.c.

References SCIPcliqueGetId().

SCIP_DECL_HASHKEYVAL()

static SCIP_DECL_HASHKEYVAL ( cliqueGetHashkeyVal  )

static

returns the hash value of the key

Definition at line 351 of file prop_pseudoobj.c.

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

scip	SCIP data structure
objimplics	pointer to objective implication data structure
objvars	objective contributor variables, or NULL
binobjvarmap	hash map mapping binary variables with none-zero objective to position in collected variables arrays, or NULL
collectedlbvars	temporary buffer to mark collected variables for lower bound fixing, or NULL
collectedubvars	temporary buffer to mark collected variables for upper bound fixing, or NULL
maxlbobjchg	maximum objective contributor if variables id fixed to zero
maxubobjchg	maximum objective contributor if variables id fixed to one
nlbimpls	number of variables contributing to to lower bound fix
nubimpls	number of variables contributing to to upper bound fix

Definition at line 364 of file prop_pseudoobj.c.

References FALSE, MAX, SCIP_ObjImplics::nlbimpls, SCIP_ObjImplics::nubimpls, NULL, objimplicsFree(), SCIP_Bool, SCIP_BOUNDTYPE_LOWER, SCIP_CALL, SCIP_OKAY, SCIPallocBlockMemory, SCIPallocBlockMemoryArray, SCIPcaptureVar(), SCIPdebugMsg, SCIPhashmapExists(), SCIPhashmapGetImageInt(), SCIPisNegative(), SCIPisZero(), SCIPtightenVarLbGlobal(), SCIPtightenVarUbGlobal(), SCIPvarGetBestBoundType(), SCIPvarGetLbGlobal(), SCIPvarGetName(), SCIPvarGetObj(), SCIPvarGetUbGlobal(), and SCIPvarIsBinary().

Referenced by collectMinactVar().

objimplicsFree()

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

static

frees an objective implication data structure

Parameters

scip	SCIP data structure
objimplics	pointer to objective implication data structure

Definition at line 498 of file prop_pseudoobj.c.

Referenced by objimplicsCreate().

objimplicsDelPos()

static 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

scip	SCIP data structure
objimplics	objective implication data structure
pos	position

Definition at line 526 of file prop_pseudoobj.c.

Referenced by getMinactImplicObjchg().

catchObjEvent()

static 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

scip	SCIP data structure
propdata	propagator data
eventhdlr	event handler for global bound change events
var	variable for which the event should be dropped

Definition at line 577 of file prop_pseudoobj.c.

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

dropObjEvent()

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

static

drop variable event w.r.t. objective coefficient

Parameters

scip	SCIP data structure
propdata	propagator data
eventhdlr	event handler for global bound change events
var	variable for which the event should be dropped

Definition at line 608 of file prop_pseudoobj.c.

References dropVarEvents(), NULL, SCIP_CALL, SCIP_EVENTTYPE_GLBCHANGED, SCIP_EVENTTYPE_GUBCHANGED, SCIP_OKAY, SCIP_Real, SCIPdropVarEvent(), SCIPisZero(), and SCIPvarGetObj().

Referenced by catchObjEvent().

dropVarEvents()

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

static

drop all variable events

Parameters

scip	SCIP data structure
propdata	propagator data

Definition at line 639 of file prop_pseudoobj.c.

Referenced by dropObjEvent().

propdataReset()

static void propdataReset ( SCIP_PROPDATA *  propdata )

static

reset propagatore data structure

Parameters

propdata

propagator data

Definition at line 702 of file prop_pseudoobj.c.

propdataExit()

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

static

free propagator data

Parameters

scip	SCIP data structure
propdata	propagator data

Definition at line 734 of file prop_pseudoobj.c.

Referenced by SCIP_DECL_PROPEXEC(), and SCIP_DECL_PROPEXITSOL().

getVarObjchg()

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

static

returns the objective change for the given binary variable

Parameters

var	variable to get objective change for
boundtype	bound type to consider
bound	fixing bound

Definition at line 770 of file prop_pseudoobj.c.

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

collectMinactImplicVar()

static 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

scip	SCIP data structure
var	variable to computes the objective contribution
binobjvarmap	hash map mapping binary variables with none-zero objective to position in collected variables arrays
collectedvars	temporary buffer to mark collected variables
nbinobjvars	number of binary variables with non-zero objective coefficient
contributors	array to store the contributors
ncontributors	pointer to store number of contributor to the objective contribution

Definition at line 789 of file prop_pseudoobj.c.

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

Referenced by collectMinactImplicVars().

collectMinactImplicVars()

static 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

scip	SCIP data structure
var	variable to computes the objective contribution
bound	bound to check for
binobjvarmap	hash map mapping binary variables with none-zero objective to position in collected variables arrays
collectedvars	temporary buffer to mark collected variables
nbinobjvars	number of binary variables with non-zero objective coefficient
contributors	array to store the contributors
uselesscliques	hash table to store useless cliques, or NULL
ncontributors	pointer to store number of contributor to the objective contribution
objchg	pointer to store the objective change

Definition at line 856 of file prop_pseudoobj.c.

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

Referenced by collectMinactObjchg().

getMinactImplicObjchg()

static 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

scip	SCIP data structure
var	variable to computes the objective contribution
objimplics	objective implication data for the given variable
bdchgidx	bound change index representing time on path to current node, or NULL
bound	bound to check for
local	propagate local bounds, otherwise global bounds
objchg	pointer to store the objective change

Definition at line 983 of file prop_pseudoobj.c.

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

Referenced by collectMinactImplicVars(), and getMinactObjchg().

collectMinactObjchg()

static 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

scip	SCIP data structure
var	variable to computes the objective contribution
bound	bound to check for
binobjvarmap	hash map mapping binary variables with none-zero objective to position in collected variables arrays
collectedvars	temporary buffer to mark collected variables
nbinobjvars	number of binary variables with non-zero objective coefficient
contributors	array to store the contriboters
uselesscliques	hash table to store useless cliques, or NULL
ncontributors	pointer to store number of contributor to the objective contribution
objchg	pointer to store the objective change

Definition at line 1068 of file prop_pseudoobj.c.

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

Referenced by collectMinactVar(), and getMinactImplicObjchg().

getMinactObjchg()

static 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

scip	SCIP data structure
var	variable to computes the objective contribution
objimplics	objective implication data for the given variable
bdchgidx	bound change index representing time on path to current node, or NULL
bound	bound to check for
local	propagate local bounds, otherwise global bounds
objchg	pointer to store the objective change

Definition at line 1101 of file prop_pseudoobj.c.

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

Referenced by collectMinactObjchg(), and propagateCutoffboundBinvar().

getMaxactImplicObjchg()

static 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

scip	SCIP data structure
var	variable to computes the objective contribution
bound	bound to check for
objchg	pointer to store the objective change

Definition at line 1137 of file prop_pseudoobj.c.

References ABS, BMSclearMemoryArray, FALSE, getMaxactObjchg(), MAX_CLIQUELENGTH, NULL, SCIP_Bool, SCIP_BOUNDTYPE_LOWER, SCIP_BOUNDTYPE_UPPER, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPcliqueGetNVars(), SCIPcliqueGetValues(), SCIPcliqueGetVars(), SCIPdebugMsg, SCIPfreeBufferArray, SCIPgetNContVars(), SCIPgetNVars(), SCIPgetVars(), SCIPisFeasGT(), SCIPisFeasLT(), SCIPisTransformed(), SCIPisZero(), SCIPvarGetCliques(), SCIPvarGetImplBounds(), SCIPvarGetImplTypes(), SCIPvarGetImplVars(), SCIPvarGetLbGlobal(), SCIPvarGetLbLocal(), SCIPvarGetName(), SCIPvarGetNCliques(), SCIPvarGetNImpls(), SCIPvarGetObj(), SCIPvarGetProbindex(), SCIPvarGetUbGlobal(), SCIPvarGetUbLocal(), SCIPvarGetWorstBoundType(), SCIPvarIsActive(), SCIPvarIsBinary(), and TRUE.

Referenced by getMaxactObjchg(), and getMinactObjchg().

getMaxactObjchg()

static 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

scip	SCIP data structure
var	variable to computes the objective contribution
bound	bound to check for
useimplics	should implications be used
objchg	pointer to store the objective change

Definition at line 1327 of file prop_pseudoobj.c.

References getMaxactImplicObjchg(), getVarObjchg(), NULL, resetContributors(), SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIPvarGetWorstBoundType(), and SCIPvarIsBinary().

Referenced by collectMaxactVar(), getMaxactImplicObjchg(), and propagateLowerboundBinvar().

resetContributors()

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

static

reset variables array which marks variables which are collected

Parameters

binobjvarmap	hash map mapping binary variables with none-zero objective to position in collected variables arrays
collectedvars	temporary buffer to mark collected variables which should be reset
contributors	temporary buffer to use for collecting contributors
ncontributors	number of contributors

Definition at line 1356 of file prop_pseudoobj.c.

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

Referenced by collectMinactVar(), and getMaxactObjchg().

collectMinactVar()

static 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

scip	SCIP data structure
var	variable to check
objimplics	pointer to store the objective implication data structure w.r.t. minimum activity
useimplics	should implications be used
binobjvarmap	hash map mapping binary variables with none-zero objective to position in collected variables arrays
collectedlbvars	temporary buffer to mark collected variables for lower bound fixing
collectedubvars	temporary buffer to mark collected variables for upper bound fixing
nbinobjvars	number of binary variables with non-zero objective coefficient
contributors	temporary buffer to use for collecting contributors
uselesscliques	hash table to store useless cliques, or NULL
collect	pointer to store if the variable should be stored

Definition at line 1381 of file prop_pseudoobj.c.

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

Referenced by resetContributors().

collectMaxactVar()

static 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

scip	SCIP data structure
var	variable to check
useimplics	should implications be used
objchg	pointer to store the objective change w.r.t. maximum activity
isnotzero	pointer to store if the objective change is unequal to zero or not

Definition at line 1497 of file prop_pseudoobj.c.

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

Referenced by collectMinactVar().

propdataInit()

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

static

initializate the propagator

Parameters

scip	SCIP data structure
propdata	propagator data

Definition at line 1534 of file prop_pseudoobj.c.

Referenced by collectMaxactVar(), and SCIP_DECL_PROPEXEC().

addConflictBounds()

static 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

scip	SCIP data structure
var	variable to check for objective contribution
bdchgidx	bound change index (time stamp of bound change), or NULL for current time
reqpseudoobjval	pointer to store the remaining minimum activity which has to be proven

Definition at line 1845 of file prop_pseudoobj.c.

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

Referenced by resolvePropagation().

getConflictImplics()

static 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

scip	SCIP data structure
vars	variable to check for objective contribution
start	start index
end	end index
bdchgidx	bound change index (time stamp of bound change), or NULL for current time
addedvars	hash table containing variables which are already added directly or implicitly due to implications
reqpseudoobjval	pointer to store the remaining minimum activity which has to be proven
foundimplics	pointer to store if an implication is found

Definition at line 1905 of file prop_pseudoobj.c.

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

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

addConflictBinvar()

static 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

scip	SCIP data structure
var	variable to check for objective contribution
bdchgidx	bound change index (time stamp of bound change), or NULL for current time
objimplics	objective implication data for the given variable
addedvars	hash table containing variables which are already add directly or implicitly due to implications
respropuseimplics	should implications be used
reqpseudoobjval	pointer to store the remaining minimum activity which has to be proven

Definition at line 1952 of file prop_pseudoobj.c.

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

Referenced by getConflictImplics(), and resolvePropagation().

adjustCutoffbound()

static 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

scip	SCIP data structure
propdata	propagator data
var	variable that was deduced
inferinfo	inference information
boundtype	the type of the changed bound (lower or upper bound)
bdchgidx	bound change index (time stamp of bound change), or NULL for current time
addedvars	hash table which contains variables which are already added or implicitly given as reason for the resolve, or NULL
cutoffbound	pointer to store the adjusted cutoff bound

Definition at line 2040 of file prop_pseudoobj.c.

References FALSE, getConflictImplics(), getVarObjchg(), SCIP_ObjImplics::nlbimpls, SCIP_ObjImplics::nubimpls, NULL, SCIP_ObjImplics::objvars, resolvePropagation(), SCIP_Bool, SCIP_BOUNDTYPE_LOWER, SCIP_BOUNDTYPE_UPPER, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPfeastol(), SCIPgetVarLbAtIndex(), SCIPgetVarUbAtIndex(), SCIPisEQ(), SCIPisNegative(), SCIPisZero(), SCIPvarGetBestBoundType(), SCIPvarGetLbGlobal(), SCIPvarGetObj(), SCIPvarGetUbGlobal(), SCIPvarIsBinary(), SCIPvarIsIntegral(), and TRUE.

Referenced by addConflictBinvar(), and resolvePropagation().

resolvePropagation()

static 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

scip	SCIP data structure
propdata	propagator data
cutoffbound	the global cutoff
infervar	variable that was deduced, or NULL for conflict analysis initialization
inferinfo	inference information
boundtype	the type of the changed bound (lower or upper bound)
bdchgidx	bound change index (time stamp of bound change), or NULL for current time

Definition at line 2136 of file prop_pseudoobj.c.

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

Referenced by adjustCutoffbound(), and propagateCutoffboundBinvar().

propagateCutoffboundVar()

static 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

scip	SCIP data structure
prop	propagator, or NULL
var	variable to propagate
inferinfo	inference information to store with the bound change
objchg	objective change
cutoffbound	cutoff bound to use
pseudoobjval	pseudo objective value to use
local	local or global propagation
tightened	pointer to store if the variable domain was tightened

Definition at line 2282 of file prop_pseudoobj.c.

References FALSE, NULL, propagateCutoffboundBinvar(), QUAD, QUAD_TO_DBL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPdebugMsg, SCIPinferVarLbProp(), SCIPinferVarUbProp(), SCIPisFeasEQ(), SCIPisInfinity(), SCIPisLT(), SCIPisZero(), SCIPquadprecDivQD, SCIPquadprecSumDD, SCIPquadprecSumQD, SCIPtightenVarLbGlobal(), SCIPtightenVarUbGlobal(), SCIPvarGetLbGlobal(), SCIPvarGetLbLocal(), SCIPvarGetName(), SCIPvarGetUbGlobal(), and SCIPvarGetUbLocal().

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

propagateCutoffboundBinvar()

static 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

scip	SCIP data structure
prop	propagator, or NULL
var	variable to propagate
pos	position of the variable in the corresponding propdata variable array
cutoffbound	cutoff bound to use
pseudoobjval	pseudo objective value to use
tightened	pointer to store if the variable domain was tightened
cutoff	pointer to store if a cutoff was detected
local	propagate local bounds, otherwise global bounds

Definition at line 2396 of file prop_pseudoobj.c.

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

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

propagateCutoffboundGlobally()

static 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

scip	SCIP data structure
prop	propagator
nchgbds	pointer to store the number of bound changes
cutoff	pointer to store if a cutoff was detected

Definition at line 2480 of file prop_pseudoobj.c.

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

Referenced by propagateCutoffboundBinvar().

propagateCutoffboundBinvars()

static 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

scip	SCIP data structure
prop	propagator
cutoffbound	cutoff bound to use
pseudoobjval	pseudo objective value to use
nfixedvars	pointer to store the number of fixed variables
cutoff	pointer to store if a cutoff was detected

Definition at line 2637 of file prop_pseudoobj.c.

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

Referenced by propagateCutoffboundGlobally().

propagateCutoffbound()

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

static

propagates the cutoff bound c*x <= cutoff

Parameters

scip	SCIP data structure
prop	propagator
result	pointer to store the result of the callback method

Definition at line 2770 of file prop_pseudoobj.c.

Referenced by propagateCutoffboundBinvars(), and SCIP_DECL_PROPEXEC().

calcMaxObjPseudoactivity()

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

static

recalculates the maximum objective pseudoactivity

Parameters

scip	SCIP data structure
propdata	propagator data

Definition at line 2966 of file prop_pseudoobj.c.

updateMaxObjPseudoactivity()

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

static

updates the pseudo objective activity if necessary

Parameters

scip	SCIP data structure
propdata	propagator data

Definition at line 3016 of file prop_pseudoobj.c.

getMaxObjPseudoactivityResidualValue()

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

static

returns the residual pseudo objective activity without the given value

Parameters

scip	SCIP data structure
propdata	propagator data
contrib	value to eliminate from pseudo objective activity

Definition at line 3031 of file prop_pseudoobj.c.

getMaxObjPseudoactivityResidual()

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

static

returns the residual pseudo objective activity

Parameters

scip	SCIP data structure
propdata	propagator data
var	variable to get residual activity for

Definition at line 3069 of file prop_pseudoobj.c.

Referenced by propagateLowerboundVar().

getMaxObjPseudoactivity()

static SCIP_Real getMaxObjPseudoactivity ( SCIP *  scip, SCIP_PROPDATA *  propdata  )

static

returns the maximum pseudo objective activity of the objective function

Parameters

scip	SCIP data structure
propdata	propagator data

Definition at line 3102 of file prop_pseudoobj.c.

propagateLowerboundBinvar()

static 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

scip	SCIP data structure
var	variable to propagate
lowerbound	lower bound to use
maxpseudoobjact	maximum pseudo objective activity
useimplics	should implications be used
infeasible	pointer to store if the variable domain got empty, infeasible
tightened	pointer to store if the variable domain was tightened

Definition at line 3112 of file prop_pseudoobj.c.

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

propagateLowerboundVar()

static 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

scip	SCIP data structure
propdata	propagator data
var	variable to propagate
lowerbound	lower bound to use
infeasible	pointer to store if the variable domain got empty, infeasible
tightened	pointer to store if the variable domain was tightened

Definition at line 3170 of file prop_pseudoobj.c.

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

Referenced by propagateLowerboundBinvar().

propagateLowerbound()

static SCIP_RETCODE propagateLowerbound ( SCIP *  scip, SCIP_PROP *  prop, SCIP_RESULT *  result  )

static

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

Parameters

scip	SCIP data structure
prop	propagator
result	pointer to store the result of the callback method

Definition at line 3235 of file prop_pseudoobj.c.

Referenced by propagateLowerboundVar(), and SCIP_DECL_PROPEXEC().

SCIP_DECL_PROPCOPY()

static SCIP_DECL_PROPCOPY ( propCopyPseudoobj  )

static

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

Definition at line 3436 of file prop_pseudoobj.c.

SCIP_DECL_PROPFREE()

static SCIP_DECL_PROPFREE ( propFreePseudoobj  )

static

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

Definition at line 3450 of file prop_pseudoobj.c.

SCIP_DECL_PROPINITSOL()

static SCIP_DECL_PROPINITSOL ( propInitsolPseudoobj  )

static

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

Definition at line 3465 of file prop_pseudoobj.c.

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

SCIP_DECL_PROPEXITSOL()

static SCIP_DECL_PROPEXITSOL ( propExitsolPseudoobj  )

static

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

Definition at line 3489 of file prop_pseudoobj.c.

References FALSE, propdataExit(), SCIP_CALL, SCIP_DECL_PROPPRESOL(), SCIP_EVENTTYPE_VARADDED, SCIP_OKAY, SCIP_Real, and SCIPdropEvent().

Referenced by SCIP_DECL_PROPINITSOL().

SCIP_DECL_PROPPRESOL()

static SCIP_DECL_PROPPRESOL ( propPresolPseudoobj  )

static

presolving method of propagator

Definition at line 3512 of file prop_pseudoobj.c.

Referenced by SCIP_DECL_PROPEXITSOL().

SCIP_DECL_PROPEXEC()

static SCIP_DECL_PROPEXEC ( propExecPseudoobj  )

static

execution method of propagator

Definition at line 3595 of file prop_pseudoobj.c.

References propagateCutoffbound(), propagateLowerbound(), propdataExit(), propdataInit(), SCIP_CALL, SCIP_CUTOFF, SCIP_DECL_PROPRESPROP(), SCIP_OKAY, SCIP_Real, SCIP_REDUCEDDOM, SCIP_STAGE_SOLVING, SCIPgetStage(), SCIPisEQ(), SCIPvarGetLbGlobal(), and SCIPvarGetUbGlobal().

SCIP_DECL_PROPRESPROP()

static SCIP_DECL_PROPRESPROP ( propRespropPseudoobj  )

static

propagation conflict resolving method of propagator

Definition at line 3651 of file prop_pseudoobj.c.

Referenced by SCIP_DECL_PROPEXEC().

SCIP_DECL_EVENTEXEC()

static SCIP_DECL_EVENTEXEC ( eventExecPseudoobj  )

static

execution method of bound change event handler

Definition at line 3684 of file prop_pseudoobj.c.