generalized variable bounds propagator
Definition in file prop_genvbounds.c.
#include <assert.h>
#include <string.h>
#include "scip/prop_genvbounds.h"
#include "scip/debug.h"
#include "scip/cons_linear.h"
Go to the source code of this file.
Macros | |
#define | PROP_NAME "genvbounds" |
#define | PROP_DESC "generalized variable bounds propagator" |
#define | PROP_TIMING SCIP_PROPTIMING_ALWAYS |
#define | PROP_PRIORITY 3000000 |
#define | PROP_FREQ 1 |
#define | PROP_DELAY FALSE |
#define | PROP_PRESOL_PRIORITY -2000000 |
#define | PROP_PRESOLTIMING SCIP_PRESOLTIMING_FAST /* timing of the presolving method (fast, medium, or exhaustive) */ |
#define | PROP_PRESOL_MAXROUNDS -1 |
#define | DEFAULT_GLOBAL_PROPAGATION TRUE |
#define | DEFAULT_PROPAGATE_IN_ROOT_NODE TRUE |
#define | DEFAULT_SORT TRUE |
#define | DEFAULT_PROPASCONSS FALSE |
#define | EVENTHDLR_NAME "genvbounds" |
#define | EVENTHDLR_DESC "event handler for generalized variable bounds propagator" |
Typedefs | |
typedef struct GenVBound | GENVBOUND |
#define PROP_NAME "genvbounds" |
Definition at line 37 of file prop_genvbounds.c.
Referenced by SCIPgenVBoundAdd().
#define PROP_DESC "generalized variable bounds propagator" |
Definition at line 38 of file prop_genvbounds.c.
#define PROP_TIMING SCIP_PROPTIMING_ALWAYS |
Definition at line 39 of file prop_genvbounds.c.
#define PROP_PRIORITY 3000000 |
propagator priority
Definition at line 40 of file prop_genvbounds.c.
#define PROP_FREQ 1 |
propagator frequency
Definition at line 41 of file prop_genvbounds.c.
#define PROP_DELAY FALSE |
should propagation method be delayed, if other propagators found reductions?
Definition at line 42 of file prop_genvbounds.c.
#define PROP_PRESOL_PRIORITY -2000000 |
priority of the presolving method (>= 0: before, < 0: after constraint handlers); combined with presolvers
Definition at line 45 of file prop_genvbounds.c.
#define PROP_PRESOLTIMING SCIP_PRESOLTIMING_FAST /* timing of the presolving method (fast, medium, or exhaustive) */ |
Definition at line 48 of file prop_genvbounds.c.
#define PROP_PRESOL_MAXROUNDS -1 |
maximal number of presolving rounds the presolver participates in (-1: no limit)
Definition at line 49 of file prop_genvbounds.c.
#define DEFAULT_GLOBAL_PROPAGATION TRUE |
apply global propagation?
Definition at line 52 of file prop_genvbounds.c.
#define DEFAULT_PROPAGATE_IN_ROOT_NODE TRUE |
apply genvbounds in root node if no new incumbent was found?
Definition at line 53 of file prop_genvbounds.c.
#define DEFAULT_SORT TRUE |
sort genvbounds and wait for bound change events? (otherwise all genvbounds are applied in each node)
Definition at line 54 of file prop_genvbounds.c.
#define DEFAULT_PROPASCONSS FALSE |
should genvbounds be transformed to (linear) constraints?
Definition at line 57 of file prop_genvbounds.c.
#define EVENTHDLR_NAME "genvbounds" |
Definition at line 59 of file prop_genvbounds.c.
#define EVENTHDLR_DESC "event handler for generalized variable bounds propagator" |
Definition at line 60 of file prop_genvbounds.c.
Definition at line 82 of file prop_genvbounds.c.
returns correct cutoff bound value
scip | SCIP data structure |
Definition at line 148 of file prop_genvbounds.c.
Referenced by createConstraints(), getGenVBoundsBound(), and resolveGenVBoundPropagation().
|
static |
returns corresponding genvbound in genvboundstore if there is one, NULL otherwise
scip | SCIP data structure |
propdata | data of the genvbounds propagator |
var | bounds variable |
boundtype | bounds type |
Definition at line 169 of file prop_genvbounds.c.
References GenVBound::boundtype, GenVBound::coefs, GenVBound::constant, GenVBound::cutoffcoef, FALSE, getGenVBoundsMinActivity(), GenVBound::ncoefs, NULL, SCIP_Bool, SCIP_BOUNDTYPE_LOWER, SCIP_BOUNDTYPE_UPPER, SCIP_Real, SCIPdebugMsgPrint, SCIPhashmapGetImage(), SCIPisZero(), SCIPvarGetName(), TRUE, GenVBound::var, and GenVBound::vars.
Referenced by addNewGenVBound(), and SCIPgenVBoundAdd().
|
static |
calculates the minactivity of a linear combination of variables stored in an array
scip | SCIP data structure |
vars | array of variables |
coefs | array of coefficients |
nvars | number of variables |
global | use global variable bounds? |
Definition at line 236 of file prop_genvbounds.c.
References bound, GenVBound::coefs, getGenVBoundsMinActivityConflict(), NULL, SCIP_Real, SCIPinfinity(), SCIPisInfinity(), SCIPvarGetLbGlobal(), SCIPvarGetLbLocal(), SCIPvarGetUbGlobal(), SCIPvarGetUbLocal(), and GenVBound::vars.
Referenced by getGenVBound(), and getGenVBoundsBound().
|
static |
calculates the minactivity of a linear combination of variables stored in the current conflict set
scip | SCIP data structure |
vars | array of variables |
coefs | array of coefficients |
nvars | number of variables |
bdchgidx | bound change at which minactivity should be computed; if NULL use local bounds |
Definition at line 277 of file prop_genvbounds.c.
References bound, getGenVBoundsBound(), NULL, SCIP_Bool, SCIP_Real, SCIPgetConflictVarLb(), SCIPgetConflictVarUb(), SCIPgetVarLbAtIndex(), SCIPgetVarUbAtIndex(), SCIPinfinity(), SCIPisEQ(), SCIPisInfinity(), SCIPvarGetLbLocal(), SCIPvarGetUbLocal(), and TRUE.
Referenced by getGenVBoundsMinActivity(), and resolveGenVBoundPropagation().
returns a valid bound given by a generalized variable bound
scip | SCIP data structure |
genvbound | generalized variable bound |
global | use global variable bounds? |
Definition at line 337 of file prop_genvbounds.c.
References GenVBound::boundtype, GenVBound::coefs, GenVBound::constant, createStartingData(), GenVBound::cutoffcoef, getCutoffboundGenVBound(), getGenVBoundsMinActivity(), GenVBound::ncoefs, NULL, SCIP_BOUNDTYPE_LOWER, SCIP_BOUNDTYPE_UPPER, SCIP_CALL, SCIP_INVALID, SCIP_OKAY, SCIP_Real, SCIP_UNKNOWN, SCIPdebugCheckLbGlobal, SCIPdebugCheckUbGlobal, SCIPdebugGetSolVal, SCIPgetSolTransObj(), SCIPgetTransObjoffset(), SCIPgetTransObjscale(), SCIPinfinity(), SCIPisInfinity(), GenVBound::var, and GenVBound::vars.
Referenced by applyGenVBound(), and getGenVBoundsMinActivityConflict().
|
static |
allocate local and global startindices, startcomponents and startmap
scip | SCIP data structure |
propdata | data of the genvbounds propagator |
Definition at line 419 of file prop_genvbounds.c.
References freeStartingData(), NULL, SCIP_CALL, SCIP_OKAY, SCIPallocBlockMemoryArray, SCIPblkmem(), SCIPdebugMsg, and SCIPhashmapCreate().
Referenced by execGenVBounds(), and getGenVBoundsBound().
|
static |
free local and global startindices, startcomponents and startmap
scip | SCIP data structure |
propdata | data of the genvbounds propagator |
Definition at line 460 of file prop_genvbounds.c.
References fillGlobalStartingData(), NULL, SCIP_OKAY, SCIPdebugMsg, SCIPfreeBlockMemoryArray, and SCIPhashmapFree().
Referenced by createConstraints(), createStartingData(), and execGenVBounds().
|
static |
scip | SCIP data structure |
propdata | data of the genvbounds propagator |
Definition at line 505 of file prop_genvbounds.c.
References NULL, resetLocalStartingData(), SCIP_CALL, SCIP_OKAY, SCIPdebugMsg, SCIPisNegative(), SCIPisZero(), and SCIPreallocBlockMemoryArray.
Referenced by execGenVBounds(), and freeStartingData().
|
static |
resets local starting data
scip | SCIP data structure |
propdata | data of the genvbounds propagator |
Definition at line 559 of file prop_genvbounds.c.
References freeComponentsData(), NULL, SCIP_CALL, SCIP_OKAY, and SCIPhashmapRemoveAll().
Referenced by applyGenVBounds(), and fillGlobalStartingData().
|
static |
frees sorted components data
scip | SCIP data structure |
propdata | data of the genvbounds propagator |
Definition at line 579 of file prop_genvbounds.c.
References freeGenVBound(), NULL, SCIP_OKAY, SCIPdebugMsg, and SCIPfreeBlockMemoryArray.
Referenced by createConstraints(), execGenVBounds(), and resetLocalStartingData().
|
static |
frees memory allocated for a generalized variable bound
Definition at line 606 of file prop_genvbounds.c.
References GenVBound::coefs, GenVBound::coefssize, GenVBound::ncoefs, NULL, resolveGenVBoundPropagation(), SCIP_CALL, SCIP_OKAY, SCIPfreeBlockMemory, SCIPfreeBlockMemoryArray, SCIPreleaseVar(), GenVBound::var, and GenVBound::vars.
Referenced by createConstraints(), and freeComponentsData().
|
static |
resolves propagation of lower bound on +/- left-hand side variable of a generalized variable bound
scip | SCIP data structure |
genvbound | genvbound data structure |
bdchgidx | the index of the bound change, representing the point of time where the change took place |
boundval | pointer to lower bound value on +/- left-hand side variable |
success | was the explanation succesful? |
Definition at line 637 of file prop_genvbounds.c.
References analyzeGenVBoundConflict(), GenVBound::boundtype, GenVBound::coefs, GenVBound::constant, GenVBound::cutoffcoef, FALSE, getCutoffboundGenVBound(), getGenVBoundsMinActivityConflict(), MAX, GenVBound::ncoefs, NULL, SCIP_BOUNDTYPE_LOWER, SCIP_BOUNDTYPE_UPPER, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPaddConflictRelaxedLb(), SCIPaddConflictRelaxedUb(), SCIPdebugMsg, SCIPfeasCeil(), SCIPgetConflictVarLb(), SCIPgetConflictVarUb(), SCIPgetVarLbAtIndex(), SCIPgetVarUbAtIndex(), SCIPisEQ(), SCIPisGE(), SCIPisGT(), SCIPisLE(), SCIPisLT(), SCIPisPositive(), SCIPvarGetLbGlobal(), SCIPvarGetLbLocal(), SCIPvarGetName(), SCIPvarGetUbGlobal(), SCIPvarGetUbLocal(), SCIPvarIsIntegral(), TRUE, GenVBound::var, and GenVBound::vars.
Referenced by analyzeGenVBoundConflict(), and freeGenVBound().
|
static |
create initial conflict
scip | SCIP data structure |
genvbound | genvbound data structure |
Definition at line 855 of file prop_genvbounds.c.
References applyGenVBound(), bound, GenVBound::boundtype, MAX, NULL, REALABS, resolveGenVBoundPropagation(), SCIP_Bool, SCIP_BOUNDTYPE_LOWER, SCIP_CALL, SCIP_CONFTYPE_PROPAGATION, SCIP_OKAY, SCIP_Real, SCIPaddConflictRelaxedLb(), SCIPaddConflictRelaxedUb(), SCIPanalyzeConflict(), SCIPdebugMsg, SCIPfeastol(), SCIPgetConflictVarLb(), SCIPgetConflictVarUb(), SCIPgetCutoffbound(), SCIPinitConflictAnalysis(), SCIPisConflictAnalysisApplicable(), SCIPisFeasGT(), SCIPisFeasLT(), SCIPisGE(), SCIPisInfinity(), SCIPisLE(), SCIPvarGetLbLocal(), SCIPvarGetName(), SCIPvarGetUbLocal(), and GenVBound::var.
Referenced by applyGenVBound(), and resolveGenVBoundPropagation().
|
static |
apply propagation for one generalized variable bound; also if the left-hand side variable is locally fixed, we compute the right-hand side minactivity to possibly detect infeasibility
scip | SCIP data structure |
prop | genvbounds propagator |
genvbound | genvbound data structure |
global | apply global bound changes? (global: true, local: false) |
result | result pointer |
nchgbds | counter to increment if bound was tightened |
Definition at line 987 of file prop_genvbounds.c.
References analyzeGenVBoundConflict(), GenVBound::boundtype, FALSE, freeEventData(), getGenVBoundsBound(), GenVBound::index, GenVBound::ncoefs, NULL, REALABS, SCIP_Bool, SCIP_BOUNDTYPE_LOWER, SCIP_BOUNDTYPE_UPPER, SCIP_CALL, SCIP_CUTOFF, SCIP_DIDNOTRUN, SCIP_OKAY, SCIP_Real, SCIP_REDUCEDDOM, SCIP_STAGE_PRESOLVING, SCIP_SUCCESS, SCIP_VARSTATUS_MULTAGGR, SCIPdebugMessage, SCIPdebugMsg, SCIPdebugPrintf, SCIPgetStage(), SCIPinferVarLbProp(), SCIPinferVarUbProp(), SCIPisInfinity(), SCIPtightenVarLbGlobal(), SCIPtightenVarUbGlobal(), SCIPvarGetLbGlobal(), SCIPvarGetLbLocal(), SCIPvarGetName(), SCIPvarGetStatus(), SCIPvarGetUbGlobal(), SCIPvarGetUbLocal(), and GenVBound::var.
Referenced by analyzeGenVBoundConflict(), and applyGenVBounds().
|
static |
frees event data
scip | SCIP data structure |
eventdata | event data to be freed |
Definition at line 1121 of file prop_genvbounds.c.
References freeAllEventData(), NULL, SCIP_OKAY, SCIPfreeBlockMemory, and SCIPfreeBlockMemoryArray.
Referenced by applyGenVBound(), and freeAllEventData().
|
static |
frees all eventdata stored
scip | SCIP data structure |
propdata | data of the genvbounds propagator |
Definition at line 1145 of file prop_genvbounds.c.
References dropAndFreeEvents(), freeEventData(), NULL, SCIP_CALL, SCIP_OKAY, SCIPfreeBlockMemoryArray, and SCIPhashmapFree().
Referenced by dropAndFreeEvents(), and freeEventData().
|
static |
drops all events caught by genvbounds propagator and frees their data
scip | SCIP data structure |
propdata | data of the genvbounds propagator |
Definition at line 1192 of file prop_genvbounds.c.
References freeAllEventData(), getEventData(), NULL, SCIP_CALL, SCIP_EVENTTYPE_LBTIGHTENED, SCIP_EVENTTYPE_UBTIGHTENED, SCIP_OKAY, SCIPdebugMsg, SCIPdropVarEvent(), and GenVBound::var.
Referenced by createConstraints(), execGenVBounds(), and freeAllEventData().
|
static |
returns the corresponding event data entry in the corresponding array, if there is one; if not: allocates a new event data entry, stores it in the array and returns its adress
scip | SCIP data structure |
propdata | data of the genvbounds propagator |
var | variable |
boundtype | type of bound |
eventdata | event data to return |
Definition at line 1241 of file prop_genvbounds.c.
References addEventData(), NULL, SCIP_BOUNDTYPE_LOWER, SCIP_CALL, SCIP_OKAY, SCIPallocBlockMemory, SCIPallocBlockMemoryArray, SCIPhashmapExists(), SCIPhashmapGetImage(), SCIPhashmapInsert(), and GenVBound::var.
Referenced by addEventData(), and dropAndFreeEvents().
|
static |
adds an event to the event array lbevents (if boundtype == SCIP_BOUNDTYPE_LOWER) or ubevents (if boundtype == SCIP_BOUNDTYPE_UPPER)
scip | SCIP data structure |
propdata | data of the genvbounds propagator |
var | variable thats event to be added |
startindex | starting index |
startcomponent | starting components index |
boundtype | type of bound |
Definition at line 1293 of file prop_genvbounds.c.
References getEventData(), NULL, SCIP_CALL, SCIP_OKAY, and setUpEvents().
Referenced by getEventData(), and setUpEvents().
|
static |
scip | SCIP data structure |
propdata | data of the genvbounds propagator |
Definition at line 1336 of file prop_genvbounds.c.
References addEventData(), GenVBound::coefs, GenVBound::ncoefs, NULL, SCIP_BOUNDTYPE_LOWER, SCIP_BOUNDTYPE_UPPER, SCIP_CALL, SCIP_EVENTTYPE_LBTIGHTENED, SCIP_EVENTTYPE_UBTIGHTENED, SCIP_OKAY, SCIPallocBlockMemoryArray, SCIPblkmem(), SCIPcatchVarEvent(), SCIPdebugMsg, SCIPgetNFixedVars(), SCIPgetNVars(), SCIPhashmapCreate(), SCIPisPositive(), SCIPreallocBlockMemoryArray, sortGenVBounds(), and GenVBound::vars.
Referenced by addEventData(), and execGenVBounds().
|
static |
performs a topological sort on genvboundstore array
The genvbounds graph is defined as follows: Given two genvbounds
(genvbound1) c1 * x_i1 >= RHS1
and
(genvbound2) c2 * x_i2 >= RHS2,
there is an arc from genvbound1 to genvbound2 iff c1 = +1 and x_i1 appears with positive coefficient in RHS2 or c1 = -1 and x_i1 appears with negative coefficient in RHS2; in this case, a bound change of x_i1 deduced from genvbound1 improves genvbound2's minactivity in RHS2.
The method computes the strongly connected components and sorts them topologically. The order of the nodes in an strongly connected component is arbitrary.
scip | SCIP data structure |
propdata | data of the genvbounds propagator |
Definition at line 1477 of file prop_genvbounds.c.
References applyGenVBounds(), GenVBound::coefs, GenVBound::index, GenVBound::ncoefs, nnodes, NULL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIPallocBlockMemoryArray, SCIPallocBufferArray, SCIPdebugMsg, SCIPdigraphAddArc(), SCIPdigraphComputeDirectedComponents(), SCIPdigraphComputeUndirectedComponents(), SCIPdigraphCreate(), SCIPdigraphFree(), SCIPdigraphGetComponent(), SCIPdigraphGetNComponents(), SCIPdigraphGetNNodes(), SCIPdigraphTopoSortComponents(), SCIPfreeBufferArray, SCIPhashmapExists(), SCIPhashmapGetImage(), SCIPisNegative(), SCIPisPositive(), TRUE, and GenVBound::vars.
Referenced by execGenVBounds(), and setUpEvents().
|
static |
apply propagation of generalized variable bounds
scip | SCIP data structure |
prop | genvbounds propagator |
global | use global variable bounds for propagation? |
result | result pointer |
nchgbds | counter to increase by the number of changed bounds |
Definition at line 1627 of file prop_genvbounds.c.
References applyGenVBound(), initPropdata(), NULL, resetLocalStartingData(), SCIP_CALL, SCIP_CUTOFF, SCIP_DIDNOTFIND, SCIP_DIDNOTRUN, SCIP_OKAY, SCIP_VARSTATUS_MULTAGGR, SCIPdebugMsg, SCIPgetDepth(), SCIPinProbing(), SCIPpropGetData(), and SCIPvarGetStatus().
Referenced by execGenVBounds(), and sortGenVBounds().
|
static |
initialize propagator data
scip | SCIP data structure |
propdata | data of the genvbounds propagator |
Definition at line 1718 of file prop_genvbounds.c.
References addNewGenVBound(), BMSclearMemoryArray, NULL, SCIP_CALL, SCIP_OKAY, SCIPallocBlockMemoryArray, SCIPblkmem(), SCIPdebugMsg, SCIPgetNVars(), and SCIPhashmapCreate().
Referenced by applyGenVBounds(), and SCIPgenVBoundAdd().
|
static |
adds a new genvbound to genvboundstore array and sets a hashmap entry
scip | SCIP data structure |
propdata | data of the genvbounds propagator |
genvbound | genvbound to be added |
Definition at line 1748 of file prop_genvbounds.c.
References execGenVBounds(), getGenVBound(), NULL, SCIP_BOUNDTYPE_LOWER, SCIP_CALL, SCIP_OKAY, SCIPhashmapInsert(), and SCIPreallocBlockMemoryArray.
Referenced by initPropdata(), and SCIPgenVBoundAdd().
|
static |
runs propagation routine
scip | SCIP data structure |
propdata | data of the genvbounds propagator |
result | result pointer |
local | should local propagation be applied? |
nchgbds | counter to increase by the number of changed bounds |
Definition at line 1788 of file prop_genvbounds.c.
References applyGenVBounds(), createConstraints(), createStartingData(), dropAndFreeEvents(), FALSE, fillGlobalStartingData(), freeComponentsData(), freeStartingData(), NULL, SCIP_CALL, SCIP_CUTOFF, SCIP_DIDNOTFIND, SCIP_DIDNOTRUN, SCIP_OKAY, SCIPdebugMsg, SCIPgetCurrentNode(), SCIPgetCutoffbound(), SCIPgetDepth(), SCIPinProbing(), SCIPisFeasLT(), setUpEvents(), sortGenVBounds(), and TRUE.
Referenced by addNewGenVBound().
|
static |
scip | SCIP data structure |
propdata | data of the genvbounds propagator |
Definition at line 1867 of file prop_genvbounds.c.
References GenVBound::boundtype, GenVBound::coefs, GenVBound::constant, GenVBound::cutoffcoef, dropAndFreeEvents(), FALSE, freeComponentsData(), freeGenVBound(), freeStartingData(), getCutoffboundGenVBound(), GenVBound::index, GenVBound::ncoefs, NULL, SCIP_BOUNDTYPE_LOWER, SCIP_CALL, SCIP_MAXSTRLEN, SCIP_OKAY, SCIP_Real, SCIP_VARTYPE_CONTINUOUS, SCIPaddCons(), SCIPaddVar(), SCIPaddVarLocks(), SCIPallocBufferArray, SCIPcreateConsLinear(), SCIPcreateVarBasic(), SCIPdebugMsg, SCIPdebugMsgPrint, SCIPfreeBlockMemoryArray, SCIPfreeBufferArray, SCIPgenVBoundAdd(), SCIPhashmapFree(), SCIPinfinity(), SCIPmarkDoNotMultaggrVar(), SCIPreleaseCons(), SCIPsnprintf(), SCIPvarGetName(), TRUE, GenVBound::var, and GenVBound::vars.
Referenced by execGenVBounds().
|
static |
initialization method of propagator (called after problem was transformed)
Definition at line 2174 of file prop_genvbounds.c.
Referenced by SCIPgenVBoundAdd().
|
static |
presolving method of propagator
Definition at line 2219 of file prop_genvbounds.c.
|
static |
presolving initialization method of propagator (called when presolving is about to begin)
Definition at line 2254 of file prop_genvbounds.c.
|
static |
presolving deinitialization method of propagator (called after presolving has been finished)
Definition at line 2282 of file prop_genvbounds.c.
|
static |
execution method of propagator
Definition at line 2396 of file prop_genvbounds.c.
|
static |
propagation conflict resolving method of propagator
Definition at line 2476 of file prop_genvbounds.c.
|
static |
solving process deinitialization method of propagator (called before branch and bound process data is freed)
Definition at line 2545 of file prop_genvbounds.c.
|
static |
destructor of propagator to free user data (called when SCIP is exiting)
Definition at line 2602 of file prop_genvbounds.c.
|
static |
Definition at line 2625 of file prop_genvbounds.c.