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:
Similar arguments apply for the case of only one down lock and \(c_i \geq 0\).
Definition in file presol_dualagg.c.
#include <stdio.h>
#include <assert.h>
#include <string.h>
#include "scip/pub_matrix.h"
#include "presol_dualagg.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) |
#define PRESOL_NAME "dualagg" |
Definition at line 45 of file presol_dualagg.c.
Referenced by SCIPincludePresolDualagg().
#define PRESOL_DESC "aggregate variables by dual arguments" |
Definition at line 46 of file presol_dualagg.c.
Referenced by SCIPincludePresolDualagg().
#define PRESOL_PRIORITY -12000 |
priority of the presolver (>= 0: before, < 0: after constraint handlers)
Definition at line 47 of file presol_dualagg.c.
Referenced by SCIPincludePresolDualagg().
#define PRESOL_MAXROUNDS 0 |
maximal number of presolving rounds the presolver participates in (-1: no limit)
Definition at line 48 of file presol_dualagg.c.
Referenced by SCIPincludePresolDualagg().
#define PRESOL_TIMING SCIP_PRESOLTIMING_EXHAUSTIVE /* timing of the presolver (fast, medium, or exhaustive) */ |
Definition at line 49 of file presol_dualagg.c.
Referenced by SCIPincludePresolDualagg().
Definition at line 58 of file presol_dualagg.c.
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 52 of file presol_dualagg.c.
|
static |
find row which leads to the uplock of the given variable
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 66 of file presol_dualagg.c.
References SCIP_Real, SCIPmatrixGetColIdxPtr(), SCIPmatrixGetColNNonzs(), SCIPmatrixGetColNUplocks(), SCIPmatrixGetColValPtr(), and SCIPmatrixIsRowRhsInfinity().
Referenced by getBinVarIdxInUplockRow().
|
static |
find row which leads to the downlock of the given variable
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 115 of file presol_dualagg.c.
References SCIP_Real, SCIPmatrixGetColIdxPtr(), SCIPmatrixGetColNDownlocks(), SCIPmatrixGetColNNonzs(), SCIPmatrixGetColValPtr(), and SCIPmatrixIsRowRhsInfinity().
Referenced by getBinVarIdxInDownlockRow().
|
static |
find fitting binary variable aggregation for uplock case
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 163 of file presol_dualagg.c.
References BIN0LBOUND, BIN0UBOUND, getUplockRowIdx(), NOAGG, SCIP_Real, SCIP_VARTYPE_BINARY, SCIPisGE(), SCIPisInfinity(), SCIPmatrixGetColLb(), SCIPmatrixGetColUb(), SCIPmatrixGetRowIdxPtr(), SCIPmatrixGetRowLhs(), SCIPmatrixGetRowMaxActivity(), SCIPmatrixGetRowMinActivity(), SCIPmatrixGetRowNNonzs(), SCIPmatrixGetRowValPtr(), SCIPmatrixGetVar(), and SCIPvarGetType().
Referenced by findUplockAggregations().
|
static |
find fitting binary variable aggregation for downlock case
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 261 of file presol_dualagg.c.
References BIN0LBOUND, BIN0UBOUND, getDownlockRowIdx(), NOAGG, SCIP_Real, SCIP_VARTYPE_BINARY, SCIPisGE(), SCIPisInfinity(), SCIPmatrixGetColLb(), SCIPmatrixGetColUb(), SCIPmatrixGetRowIdxPtr(), SCIPmatrixGetRowLhs(), SCIPmatrixGetRowMaxActivity(), SCIPmatrixGetRowMinActivity(), SCIPmatrixGetRowNNonzs(), SCIPmatrixGetRowValPtr(), SCIPmatrixGetVar(), and SCIPvarGetType().
Referenced by findDownlockAggregations().
|
static |
find variable aggregations for uplock case
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 361 of file presol_dualagg.c.
References getBinVarIdxInUplockRow(), SCIP_OKAY, SCIP_Real, SCIPisInfinity(), SCIPisLE(), SCIPmatrixGetColLb(), SCIPmatrixGetColNUplocks(), SCIPmatrixGetColUb(), SCIPmatrixGetNColumns(), SCIPmatrixGetVar(), SCIPvarGetLbGlobal(), SCIPvarGetObj(), and SCIPvarGetUbGlobal().
Referenced by SCIP_DECL_PRESOLEXEC().
|
static |
find variable aggregations for downlock case
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 417 of file presol_dualagg.c.
References getBinVarIdxInDownlockRow(), NOAGG, SCIP_OKAY, SCIP_Real, SCIPisGE(), SCIPisInfinity(), SCIPmatrixGetColLb(), SCIPmatrixGetColNDownlocks(), SCIPmatrixGetColUb(), SCIPmatrixGetNColumns(), SCIPmatrixGetVar(), SCIPvarGetLbGlobal(), SCIPvarGetObj(), and SCIPvarGetUbGlobal().
Referenced by SCIP_DECL_PRESOLEXEC().
|
static |
execution method of presolver
Definition at line 480 of file presol_dualagg.c.
References BIN0LBOUND, BIN0UBOUND, BMSclearMemoryArray, findDownlockAggregations(), findUplockAggregations(), NOAGG, SCIP_Bool, SCIP_CALL, SCIP_CUTOFF, SCIP_DIDNOTFIND, SCIP_DIDNOTRUN, SCIP_OKAY, SCIP_Real, SCIP_STAGE_PRESOLVING, SCIP_SUCCESS, SCIPaggregateVars(), SCIPallocBufferArray, SCIPallowDualReds(), SCIPdebug, SCIPdebugMsg, SCIPfreeBufferArray, SCIPgetNActivePricers(), SCIPgetNBinVars(), SCIPgetStage(), SCIPinProbing(), SCIPisNLPEnabled(), SCIPisStopped(), SCIPmatrixCreate(), SCIPmatrixFree(), SCIPmatrixGetColLb(), SCIPmatrixGetColUb(), SCIPmatrixGetNColumns(), and SCIPmatrixGetVar().