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:

if , constraint c can only be fulfilled for , and
if , constraint c becomes redundant and can be dual-fixed to its upper bound (or vice versa). Then we can perform the following aggregation: .

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

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 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

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 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

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, 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

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, 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

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(), 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

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)