Scippy

SCIP

Solving Constraint Integer Programs

presol_dualagg.c File Reference

Detailed Description

aggregate variables by dual arguments

Author
Dieter Weninger

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:

  1. if $x_j = 0$, constraint c can only be fulfilled for $x_i = lb_i$, and
  2. 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 <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)
 

Macro Definition Documentation

#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().

Typedef Documentation

typedef enum AggrType AGGRTYPE

Definition at line 58 of file presol_dualagg.c.

Enumeration Type Documentation

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.

Function Documentation

static void getUplockRowIdx ( SCIP_MATRIX matrix,
int  aggvaridx,
int *  rowidx,
SCIP_Real coef 
)
static

find row which leads to the uplock of the given variable

Parameters
matrixconstraint matrix
aggvaridxindex of variable which should be aggregated
rowidxpointer to store row index of uplock
coefpointer to store coefficient of variable

Definition at line 66 of file presol_dualagg.c.

References NULL, SCIP_Real, SCIPmatrixGetColIdxPtr(), SCIPmatrixGetColNNonzs(), SCIPmatrixGetColNUplocks(), SCIPmatrixGetColValPtr(), and SCIPmatrixIsRowRhsInfinity().

Referenced by getBinVarIdxInUplockRow().

static void getDownlockRowIdx ( SCIP_MATRIX matrix,
int  aggvaridx,
int *  rowidx,
SCIP_Real coef 
)
static

find row which leads to the downlock of the given variable

Parameters
matrixconstraint matrix
aggvaridxindex of variable which should be aggregated
rowidxpointer to store row index of downlock
coefpointer to store coefficient of variable

Definition at line 115 of file presol_dualagg.c.

References NULL, SCIP_Real, SCIPmatrixGetColIdxPtr(), SCIPmatrixGetColNDownlocks(), SCIPmatrixGetColNNonzs(), SCIPmatrixGetColValPtr(), and SCIPmatrixIsRowRhsInfinity().

Referenced by getBinVarIdxInDownlockRow().

static void getBinVarIdxInUplockRow ( SCIP scip,
SCIP_MATRIX matrix,
int  aggvaridx,
int *  binvaridx,
AGGRTYPE aggtype 
)
static

find fitting binary variable aggregation for uplock case

Parameters
scipSCIP main data structure
matrixconstraint matrix
aggvaridxindex of variable which should be aggregated
binvaridxpointer to store index of binary variable
aggtypepointer to store type of aggregation

Definition at line 163 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().

static void getBinVarIdxInDownlockRow ( SCIP scip,
SCIP_MATRIX matrix,
int  aggvaridx,
int *  binvaridx,
AGGRTYPE aggtype 
)
static

find fitting binary variable aggregation for downlock case

Parameters
scipSCIP main data structure
matrixconstraint matrix
aggvaridxindex of variable which should be aggregated
binvaridxpointer to store index of binary variable
aggtypepointer to store type of aggregation

Definition at line 261 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().

static SCIP_RETCODE findUplockAggregations ( SCIP scip,
SCIP_MATRIX matrix,
int *  nvaragg,
AGGRTYPE aggtypes,
SCIP_VAR **  binvars 
)
static

find variable aggregations for uplock case

Parameters
scipSCIP main data structure
matrixconstraint matrix
nvaraggnumber of redundant variables
aggtypestype of aggregations (in same order as variables in matrix)
binvarspointers to the binary variables (in same order as variables in matrix)

Definition at line 361 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().

static SCIP_RETCODE findDownlockAggregations ( SCIP scip,
SCIP_MATRIX matrix,
int *  nvaragg,
AGGRTYPE aggtypes,
SCIP_VAR **  binvars 
)
static

find variable aggregations for downlock case

Parameters
scipSCIP main data structure
matrixconstraint matrix
nvaraggnumber of redundant variables
aggtypestype of aggregations (in same order as variables in matrix)
binvarspointers to the binary variables (in same order as variables in matrix)

Definition at line 417 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_RETCODE SCIPincludePresolDualagg ( SCIP scip)

creates the dualagg presolver and includes it in SCIP

Parameters
scipSCIP data structure

Definition at line 591 of file presol_dualagg.c.

References NULL, PRESOL_DESC, PRESOL_MAXROUNDS, PRESOL_NAME, PRESOL_PRIORITY, PRESOL_TIMING, SCIP_CALL, SCIP_OKAY, and SCIPincludePresolBasic().

Referenced by SCIPincludeDefaultPlugins().