Detailed Description
aggregate variables by dual arguments
This presolver looks for variables which could not be handled by duality fixing because of one up-/downlock. If the constraint which delivers the up-/downlock has a specific structure, we can aggregate the corresponding variable.
In more detail (for a minimization problem and the case of only one uplock):
Given a variable \(x_i\) with \(c_i \leq 0\) and only one up lock (originating from a constraint c), we are looking for a binary variable \(x_j\) such that:
- if \(x_j = 0\), constraint c can only be fulfilled for \(x_i = lb_i\), and
- if \(x_j = 1\), constraint c becomes redundant and \(x_i\) can be dual-fixed to its upper bound \(ub_i\) (or vice versa). Then we can perform the following aggregation: \(x_i = lb_i + x_j (ub_i - lb_i)\).
Similar arguments apply for the case of only one down lock and \(c_i \geq 0\).
Definition in file presol_dualagg.c.
#include "blockmemshell/memory.h"
#include "scip/presol_dualagg.h"
#include "scip/pub_matrix.h"
#include "scip/pub_message.h"
#include "scip/pub_var.h"
#include "scip/scip_general.h"
#include "scip/scip_mem.h"
#include "scip/scip_message.h"
#include "scip/scip_nlp.h"
#include "scip/scip_numerics.h"
#include "scip/scip_presol.h"
#include "scip/scip_pricer.h"
#include "scip/scip_prob.h"
#include "scip/scip_probing.h"
#include "scip/scip_var.h"
Go to the source code of this file.
Macros | |
#define | PRESOL_NAME "dualagg" |
#define | PRESOL_DESC "aggregate variables by dual arguments" |
#define | PRESOL_PRIORITY -12000 |
#define | PRESOL_MAXROUNDS 0 |
#define | PRESOL_TIMING SCIP_PRESOLTIMING_EXHAUSTIVE /* timing of the presolver (fast, medium, or exhaustive) */ |
Typedefs | |
typedef enum AggrType | AGGRTYPE |
Enumerations | |
enum | AggrType { BIN0UBOUND = -1, NOAGG = 0, BIN0LBOUND = 1 } |
Functions | |
static void | getUplockRowIdx (SCIP_MATRIX *matrix, int aggvaridx, int *rowidx, SCIP_Real *coef) |
static void | getDownlockRowIdx (SCIP_MATRIX *matrix, int aggvaridx, int *rowidx, SCIP_Real *coef) |
static void | getBinVarIdxInUplockRow (SCIP *scip, SCIP_MATRIX *matrix, int aggvaridx, int *binvaridx, AGGRTYPE *aggtype) |
static void | getBinVarIdxInDownlockRow (SCIP *scip, SCIP_MATRIX *matrix, int aggvaridx, int *binvaridx, AGGRTYPE *aggtype) |
static SCIP_RETCODE | findUplockAggregations (SCIP *scip, SCIP_MATRIX *matrix, int *nvaragg, AGGRTYPE *aggtypes, SCIP_VAR **binvars) |
static SCIP_RETCODE | findDownlockAggregations (SCIP *scip, SCIP_MATRIX *matrix, int *nvaragg, AGGRTYPE *aggtypes, SCIP_VAR **binvars) |
static | SCIP_DECL_PRESOLEXEC (presolExecDualagg) |
SCIP_RETCODE | SCIPincludePresolDualagg (SCIP *scip) |
Macro Definition Documentation
◆ PRESOL_NAME
#define PRESOL_NAME "dualagg" |
Definition at line 64 of file presol_dualagg.c.
Referenced by SCIPincludePresolDualagg().
◆ PRESOL_DESC
#define PRESOL_DESC "aggregate variables by dual arguments" |
Definition at line 65 of file presol_dualagg.c.
Referenced by SCIPincludePresolDualagg().
◆ PRESOL_PRIORITY
#define PRESOL_PRIORITY -12000 |
priority of the presolver (>= 0: before, < 0: after constraint handlers)
Definition at line 66 of file presol_dualagg.c.
Referenced by SCIPincludePresolDualagg().
◆ PRESOL_MAXROUNDS
#define PRESOL_MAXROUNDS 0 |
maximal number of presolving rounds the presolver participates in (-1: no limit)
Definition at line 67 of file presol_dualagg.c.
Referenced by SCIPincludePresolDualagg().
◆ PRESOL_TIMING
#define PRESOL_TIMING SCIP_PRESOLTIMING_EXHAUSTIVE /* timing of the presolver (fast, medium, or exhaustive) */ |
Definition at line 68 of file presol_dualagg.c.
Referenced by SCIPincludePresolDualagg().
Typedef Documentation
◆ AGGRTYPE
Definition at line 77 of file presol_dualagg.c.
Enumeration Type Documentation
◆ AggrType
enum AggrType |
type of aggregation
Enumerator | |
---|---|
BIN0UBOUND | x_j = u_j + (l_j-u_j)x_i with x_i binary and x_j aggregation variable |
NOAGG | do not aggregate |
BIN0LBOUND | x_j = l_j + (u_j-l_j)x_i with x_i binary and x_j aggregation variable |
Definition at line 71 of file presol_dualagg.c.
Function Documentation
◆ getUplockRowIdx()
|
static |
find row which leads to the uplock of the given variable
- Parameters
-
matrix constraint matrix aggvaridx index of variable which should be aggregated rowidx pointer to store row index of uplock coef pointer to store coefficient of variable
Definition at line 85 of file presol_dualagg.c.
References NULL, SCIP_Real, SCIPmatrixGetColIdxPtr(), SCIPmatrixGetColNNonzs(), SCIPmatrixGetColNUplocks(), SCIPmatrixGetColValPtr(), and SCIPmatrixIsRowRhsInfinity().
Referenced by getBinVarIdxInUplockRow().
◆ getDownlockRowIdx()
|
static |
find row which leads to the downlock of the given variable
- Parameters
-
matrix constraint matrix aggvaridx index of variable which should be aggregated rowidx pointer to store row index of downlock coef pointer to store coefficient of variable
Definition at line 133 of file presol_dualagg.c.
References NULL, SCIP_Real, SCIPmatrixGetColIdxPtr(), SCIPmatrixGetColNDownlocks(), SCIPmatrixGetColNNonzs(), SCIPmatrixGetColValPtr(), and SCIPmatrixIsRowRhsInfinity().
Referenced by getBinVarIdxInDownlockRow().
◆ getBinVarIdxInUplockRow()
|
static |
find fitting binary variable aggregation for uplock case
- Parameters
-
scip SCIP main data structure matrix constraint matrix aggvaridx index of variable which should be aggregated binvaridx pointer to store index of binary variable aggtype pointer to store type of aggregation
Definition at line 181 of file presol_dualagg.c.
References BIN0LBOUND, BIN0UBOUND, getUplockRowIdx(), NOAGG, NULL, SCIP_Real, SCIP_VARTYPE_BINARY, SCIPisGE(), SCIPisInfinity(), SCIPmatrixGetColLb(), SCIPmatrixGetColUb(), SCIPmatrixGetRowIdxPtr(), SCIPmatrixGetRowLhs(), SCIPmatrixGetRowMaxActivity(), SCIPmatrixGetRowMinActivity(), SCIPmatrixGetRowNNonzs(), SCIPmatrixGetRowValPtr(), SCIPmatrixGetVar(), and SCIPvarGetType().
Referenced by findUplockAggregations().
◆ getBinVarIdxInDownlockRow()
|
static |
find fitting binary variable aggregation for downlock case
- Parameters
-
scip SCIP main data structure matrix constraint matrix aggvaridx index of variable which should be aggregated binvaridx pointer to store index of binary variable aggtype pointer to store type of aggregation
Definition at line 279 of file presol_dualagg.c.
References BIN0LBOUND, BIN0UBOUND, getDownlockRowIdx(), NOAGG, NULL, SCIP_Real, SCIP_VARTYPE_BINARY, SCIPisGE(), SCIPisInfinity(), SCIPmatrixGetColLb(), SCIPmatrixGetColUb(), SCIPmatrixGetRowIdxPtr(), SCIPmatrixGetRowLhs(), SCIPmatrixGetRowMaxActivity(), SCIPmatrixGetRowMinActivity(), SCIPmatrixGetRowNNonzs(), SCIPmatrixGetRowValPtr(), SCIPmatrixGetVar(), and SCIPvarGetType().
Referenced by findDownlockAggregations().
◆ findUplockAggregations()
|
static |
find variable aggregations for uplock case
- Parameters
-
scip SCIP main data structure matrix constraint matrix nvaragg number of redundant variables aggtypes type of aggregations (in same order as variables in matrix) binvars pointers to the binary variables (in same order as variables in matrix)
Definition at line 379 of file presol_dualagg.c.
References getBinVarIdxInUplockRow(), NULL, SCIP_OKAY, SCIP_Real, SCIPisInfinity(), SCIPisLE(), SCIPmatrixGetColLb(), SCIPmatrixGetColNUplocks(), SCIPmatrixGetColUb(), SCIPmatrixGetNColumns(), SCIPmatrixGetVar(), SCIPvarGetLbGlobal(), SCIPvarGetObj(), and SCIPvarGetUbGlobal().
Referenced by SCIP_DECL_PRESOLEXEC().
◆ findDownlockAggregations()
|
static |
find variable aggregations for downlock case
- Parameters
-
scip SCIP main data structure matrix constraint matrix nvaragg number of redundant variables aggtypes type of aggregations (in same order as variables in matrix) binvars pointers to the binary variables (in same order as variables in matrix)
Definition at line 435 of file presol_dualagg.c.
References getBinVarIdxInDownlockRow(), NOAGG, NULL, SCIP_OKAY, SCIP_Real, SCIPisGE(), SCIPisInfinity(), SCIPmatrixGetColLb(), SCIPmatrixGetColNDownlocks(), SCIPmatrixGetColUb(), SCIPmatrixGetNColumns(), SCIPmatrixGetVar(), SCIPvarGetLbGlobal(), SCIPvarGetObj(), and SCIPvarGetUbGlobal().
Referenced by SCIP_DECL_PRESOLEXEC().
◆ SCIP_DECL_PRESOLEXEC()
|
static |
execution method of presolver
Definition at line 498 of file presol_dualagg.c.
References BIN0LBOUND, BIN0UBOUND, BMSclearMemoryArray, findDownlockAggregations(), findUplockAggregations(), NOAGG, NULL, SCIP_Bool, SCIP_CALL, SCIP_CUTOFF, SCIP_DIDNOTFIND, SCIP_DIDNOTRUN, SCIP_OKAY, SCIP_Real, SCIP_STAGE_PRESOLVING, SCIP_SUCCESS, SCIPaggregateVars(), SCIPallocBufferArray, SCIPallowStrongDualReds(), SCIPdebug, SCIPdebugMsg, SCIPfreeBufferArray, SCIPgetNActivePricers(), SCIPgetNBinVars(), SCIPgetStage(), SCIPinProbing(), SCIPisNLPEnabled(), SCIPisStopped(), SCIPmatrixCreate(), SCIPmatrixFree(), SCIPmatrixGetColLb(), SCIPmatrixGetColUb(), SCIPmatrixGetNColumns(), SCIPmatrixGetVar(), and TRUE.