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 "blockmemshell/memory.h"
#include "scip/presol_redvub.h"
#include "scip/pub_matrix.h"
#include "scip/pub_message.h"
#include "scip/pub_presol.h"
#include "scip/pub_var.h"
#include "scip/scip_cons.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 "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_PRESOLCOPY (presolCopyRedvub)

static	SCIP_DECL_PRESOLEXEC (presolExecRedvub)

SCIP_RETCODE	SCIPincludePresolRedvub (SCIP *scip)

Macro Definition Documentation

◆ PRESOL_NAME

#define PRESOL_NAME "redvub"

Definition at line 60 of file presol_redvub.c.

◆ PRESOL_DESC

#define PRESOL_DESC "detect redundant variable bound constraints"

Definition at line 61 of file presol_redvub.c.

◆ PRESOL_PRIORITY

#define PRESOL_PRIORITY -9000000

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

Definition at line 62 of file presol_redvub.c.

◆ PRESOL_MAXROUNDS

#define PRESOL_MAXROUNDS 0

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

Definition at line 63 of file presol_redvub.c.

◆ PRESOL_TIMING

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

Definition at line 64 of file presol_redvub.c.

◆ MAXPAIRCOMP

#define MAXPAIRCOMP 1000

maximal number of pairwise comparisons

Definition at line 66 of file presol_redvub.c.

Function Documentation

◆ isVub()

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 74 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(), SCIPvarIsImpliedIntegral(), and TRUE.

Referenced by findVarAggrRedVbcons().

◆ isVlb()

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 158 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(), SCIPvarIsImpliedIntegral(), and TRUE.

Referenced by findVarAggrRedVbcons().

◆ detectDominatingVubs()

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 243 of file presol_redvub.c.

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

Referenced by findVarAggrRedVbcons().

◆ detectDominatingVlbs()

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 349 of file presol_redvub.c.

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

Referenced by findVarAggrRedVbcons().

◆ 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

Definition at line 456 of file presol_redvub.c.

References detectDominatingVlbs(), detectDominatingVubs(), isVlb(), isVub(), SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPfreeBufferArray, SCIPmatrixGetColIdxPtr(), SCIPmatrixGetColNNonzs(), SCIPmatrixGetNColumns(), SCIPmatrixGetNRows(), SCIPmatrixGetVar(), and SCIPvarIsIntegral().

Referenced by SCIP_DECL_PRESOLEXEC().

◆ SCIP_DECL_PRESOLCOPY()

static SCIP_DECL_PRESOLCOPY ( presolCopyRedvub )

static

copy method for presolver plugins (called when SCIP copies plugins)

Definition at line 568 of file presol_redvub.c.

References NULL, PRESOL_NAME, SCIP_CALL, SCIP_OKAY, SCIPincludePresolRedvub(), and SCIPpresolGetName().

◆ SCIP_DECL_PRESOLEXEC()

static SCIP_DECL_PRESOLEXEC ( presolExecRedvub )

static

execution method of presolver

Definition at line 582 of file presol_redvub.c.

References BMSclearMemoryArray, findVarAggrRedVbcons(), NULL, r, SCIP_Bool, SCIP_CALL, SCIP_CUTOFF, SCIP_DIDNOTFIND, SCIP_DIDNOTRUN, SCIP_OKAY, SCIP_STAGE_PRESOLVING, SCIP_SUCCESS, SCIPaggregateVars(), SCIPallocBufferArray, SCIPdebugMsg, SCIPdelCons(), SCIPfreeBufferArray, SCIPgetNActivePricers(), SCIPgetNContVars(), SCIPgetStage(), SCIPinProbing(), SCIPisNLPEnabled(), SCIPisStopped(), SCIPmatrixCreate(), SCIPmatrixFree(), SCIPmatrixGetCons(), SCIPmatrixGetNColumns(), SCIPmatrixGetNRows(), SCIPmatrixGetVar(), and TRUE.

SCIP

Detailed Description

Macros

Functions

Macro Definition Documentation

◆ PRESOL_NAME

◆ PRESOL_DESC

◆ PRESOL_PRIORITY

◆ PRESOL_MAXROUNDS

◆ PRESOL_TIMING

◆ MAXPAIRCOMP

Function Documentation

◆ isVub()

◆ isVlb()

◆ detectDominatingVubs()

◆ detectDominatingVlbs()

◆ findVarAggrRedVbcons()

◆ SCIP_DECL_PRESOLCOPY()

◆ SCIP_DECL_PRESOLEXEC()