Detailed Description

remove redundant variable upper bound constraints

Author: Dieter Weninger

This presolver looks for dominating variable bound constraints on the same continuous variable and discards them. For example let x be a continuous variable and y, y' are binary variables. In addition, let two variable upper bound constraints ax - by <= e and cx - dy' <= f are given. If ax - by <= e implies cx - dy' <= f, then we can remove the second constraint and substitute/aggregate y' := y. The same can be done with variable lower bound constraints.

Definition in file presol_redvub.c.

#include <stdio.h>
#include <assert.h>
#include <string.h>
#include "scip/pub_matrix.h"
#include "presol_redvub.h"

Go to the source code of this file.

Macros
#define	PRESOL_NAME "redvub"

#define	PRESOL_DESC "detect redundant variable bound constraints"

#define	PRESOL_PRIORITY -9000000

#define	PRESOL_MAXROUNDS 0

#define	PRESOL_TIMING SCIP_PRESOLTIMING_EXHAUSTIVE /* timing of the presolver (fast, medium, or exhaustive) */

#define	MAXPAIRCOMP 1000

Functions
static SCIP_Bool	isVub (SCIP scip, SCIP_MATRIX matrix, int row, SCIP_Real lowthreshold, SCIP_Real highthreshold, int conidx, int binidx)

static SCIP_Bool	isVlb (SCIP scip, SCIP_MATRIX matrix, int row, SCIP_Real lowthreshold, SCIP_Real highthreshold, int conidx, int binidx)

static SCIP_RETCODE	detectDominatingVubs (SCIP scip, SCIP_MATRIX matrix, int nvubs, int vubs, SCIP_Real lowthresholds, SCIP_Real highthresholds, int conidxs, int binidxs, int nvaragg, SCIP_Bool isvartoagg, SCIP_VAR aggvars, int ndeletecons, SCIP_Bool *deletecons)

static SCIP_RETCODE	detectDominatingVlbs (SCIP scip, SCIP_MATRIX matrix, int nvlbs, int vlbs, SCIP_Real lowthresholds, SCIP_Real highthresholds, int conidxs, int binidxs, int nvaragg, SCIP_Bool isvartoagg, SCIP_VAR aggvars, int ndeletecons, SCIP_Bool *deletecons)

static SCIP_RETCODE	findVarAggrRedVbcons (SCIP scip, SCIP_MATRIX matrix, int nvaragg, SCIP_Bool isvartoagg, SCIP_VAR *aggvars, int ndeletecons, SCIP_Bool *deletecons)

static	SCIP_DECL_PRESOLEXEC (presolExecRedvub)

SCIP_RETCODE	SCIPincludePresolRedvub (SCIP *scip)

Macro Definition Documentation

#define PRESOL_NAME "redvub"

Definition at line 40 of file presol_redvub.c.

Referenced by SCIPincludePresolRedvub().

#define PRESOL_DESC "detect redundant variable bound constraints"

Definition at line 41 of file presol_redvub.c.

Referenced by SCIPincludePresolRedvub().

#define PRESOL_PRIORITY -9000000

priority of the presolver (>= 0: before, < 0: after constraint handlers)

Definition at line 42 of file presol_redvub.c.

Referenced by SCIPincludePresolRedvub().

#define PRESOL_MAXROUNDS 0

maximal number of presolving rounds the presolver participates in (-1: no limit)

Definition at line 43 of file presol_redvub.c.

Referenced by SCIPincludePresolRedvub().

#define PRESOL_TIMING SCIP_PRESOLTIMING_EXHAUSTIVE /* timing of the presolver (fast, medium, or exhaustive) */

Definition at line 44 of file presol_redvub.c.

Referenced by SCIPincludePresolRedvub().

#define MAXPAIRCOMP 1000

maximal number of pairwise comparisons

Definition at line 46 of file presol_redvub.c.

Referenced by detectDominatingVlbs(), and detectDominatingVubs().

Function Documentation

static SCIP_Bool isVub	(	SCIP *	scip,
		SCIP_MATRIX *	matrix,
		int	row,
		SCIP_Real *	lowthreshold,
		SCIP_Real *	highthreshold,
		int *	conidx,
		int *	binidx
	)

static

verify if the constraint is a variable upper bound constraint

Parameters

scip	SCIP main data structure
matrix	matrix instance
row	row index
lowthreshold	low switching threshold
highthreshold	high switching threshold
conidx	variable index of continuous variable
binidx	variable index of binary variable

Definition at line 54 of file presol_redvub.c.

References FALSE, NULL, SCIP_Bool, SCIP_Real, SCIP_VARTYPE_BINARY, SCIP_VARTYPE_CONTINUOUS, SCIPisGE(), SCIPmatrixGetNRows(), SCIPmatrixGetRowIdxPtr(), SCIPmatrixGetRowLhs(), SCIPmatrixGetRowNNonzs(), SCIPmatrixGetRowValPtr(), SCIPmatrixGetVar(), SCIPmatrixIsRowRhsInfinity(), SCIPvarGetLbGlobal(), SCIPvarGetObj(), SCIPvarGetType(), and TRUE.

Referenced by findVarAggrRedVbcons().

static SCIP_Bool isVlb	(	SCIP *	scip,
		SCIP_MATRIX *	matrix,
		int	row,
		SCIP_Real *	lowthreshold,
		SCIP_Real *	highthreshold,
		int *	conidx,
		int *	binidx
	)

static

verify if the constraint is a variable lower bound constraint

Parameters

scip	SCIP main data structure
matrix	matrix instance
row	row index
lowthreshold	low switching threshold
highthreshold	high switching threshold
conidx	variable index of continuous variable
binidx	variable index of binary variable

Definition at line 135 of file presol_redvub.c.

References FALSE, NULL, SCIP_Bool, SCIP_Real, SCIP_VARTYPE_BINARY, SCIP_VARTYPE_CONTINUOUS, SCIPisGE(), SCIPmatrixGetNRows(), SCIPmatrixGetRowIdxPtr(), SCIPmatrixGetRowLhs(), SCIPmatrixGetRowNNonzs(), SCIPmatrixGetRowValPtr(), SCIPmatrixGetVar(), SCIPmatrixIsRowRhsInfinity(), SCIPvarGetLbGlobal(), SCIPvarGetObj(), SCIPvarGetType(), and TRUE.

Referenced by findVarAggrRedVbcons().

static SCIP_RETCODE detectDominatingVubs	(	SCIP *	scip,
		SCIP_MATRIX *	matrix,
		int	nvubs,
		int *	vubs,
		SCIP_Real *	lowthresholds,
		SCIP_Real *	highthresholds,
		int *	conidxs,
		int *	binidxs,
		int *	nvaragg,
		SCIP_Bool *	isvartoagg,
		SCIP_VAR **	aggvars,
		int *	ndeletecons,
		SCIP_Bool *	deletecons
	)

static

searches for variable upper bound constraints on the same continuous variable with a dominance relation

Parameters

scip	SCIP main data structure
matrix	matrix containing the constraints
nvubs	number of vubs
vubs	row indices of the vubs
lowthresholds	low switching thresholds
highthresholds	high switching thresholds
conidxs	variable indexes of continuous variable
binidxs	variable indexes of binary variable
nvaragg	number of variables for aggregation
isvartoagg	flags indicating if variable could be aggregated
aggvars	pointers to the variables by which the aggregation should be done
ndeletecons	number of deleteable constraints
deletecons	flags which constraints could be deleted

Definition at line 217 of file presol_redvub.c.

References FALSE, MAXPAIRCOMP, NULL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIPdebugMessage, SCIPinfoMessage(), SCIPisEQ(), SCIPisGT(), SCIPisLE(), SCIPmatrixGetColNDownlocks(), SCIPmatrixGetCons(), SCIPmatrixGetVar(), SCIPprintCons(), SCIPvarGetName(), and TRUE.

Referenced by findVarAggrRedVbcons().

static SCIP_RETCODE detectDominatingVlbs	(	SCIP *	scip,
		SCIP_MATRIX *	matrix,
		int	nvlbs,
		int *	vlbs,
		SCIP_Real *	lowthresholds,
		SCIP_Real *	highthresholds,
		int *	conidxs,
		int *	binidxs,
		int *	nvaragg,
		SCIP_Bool *	isvartoagg,
		SCIP_VAR **	aggvars,
		int *	ndeletecons,
		SCIP_Bool *	deletecons
	)

static

searches for variable lower bound constraints on the same continuous variable with a dominance relation

Parameters

scip	SCIP main data structure
matrix	matrix containing the constraints
nvlbs	number of vlbs
vlbs	row indices of the vlbs
lowthresholds	low switching thresholds
highthresholds	high switching thresholds
conidxs	variable indexes of continuous variable
binidxs	variable indexes of binary variable
nvaragg	number of variables for aggregation
isvartoagg	flags indicating if variable could be aggregated
aggvars	pointers to the variables by which the aggregation should be done
ndeletecons	number of deleteable constraints
deletecons	flags which constraints could be deleted

Definition at line 316 of file presol_redvub.c.

References FALSE, MAXPAIRCOMP, NULL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIPdebugMessage, SCIPinfoMessage(), SCIPisEQ(), SCIPisGE(), SCIPisLT(), SCIPmatrixGetColNUplocks(), SCIPmatrixGetCons(), SCIPmatrixGetVar(), SCIPprintCons(), SCIPvarGetName(), and TRUE.

Referenced by findVarAggrRedVbcons().

static SCIP_RETCODE findVarAggrRedVbcons	(	SCIP *	scip,
		SCIP_MATRIX *	matrix,
		int *	nvaragg,
		SCIP_Bool *	isvartoagg,
		SCIP_VAR **	aggvars,
		int *	ndeletecons,
		SCIP_Bool *	deletecons
	)

static

find variable aggregations and redundant variable bound constraints

Parameters

scip	SCIP main data structure
matrix	constraint matrix
nvaragg	number of redundant variables
isvartoagg	flags indicating which variables could be substituted/aggregated
aggvars	pointers to the variables by which the aggregation should be done
ndeletecons	number of redundant constraints
deletecons	flags indicating which constraints could be deleted