Detailed Description

perform multi-aggregation on implied free variables

Author: Dieter Weninger

This presolver tries to find implied free variables within equalities which are convenient for multi-aggregation.

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

Go to the source code of this file.

Macros
#define	PRESOL_NAME "implfree"

#define	PRESOL_DESC "exploit implied free variables for multi-aggregation"

#define	PRESOL_PRIORITY -1000

#define	PRESOL_MAXROUNDS 0

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

#define	MAXABSRATIO ((SCIP_Real)1000.0)

#define	SIDECHANGERATIO ((SCIP_Real)10.0)

Functions
static SCIP_Real	getMaxActSingleRowWithoutCol (SCIP scip, SCIP_MATRIX matrix, int row, int col)

static SCIP_Real	getMinActSingleRowWithoutCol (SCIP scip, SCIP_MATRIX matrix, int row, int col)

static void	getActivityResiduals (SCIP scip, SCIP_MATRIX matrix, int col, int row, SCIP_Real val, SCIP_Real minresactivity, SCIP_Real maxresactivity, SCIP_Bool isminsettoinfinity, SCIP_Bool ismaxsettoinfinity)

static void	getVarBoundsOfRow (SCIP scip, SCIP_MATRIX matrix, int col, int row, SCIP_Real val, SCIP_Real rowlb, SCIP_Bool lbfound, SCIP_Real rowub, SCIP_Bool ubfound)

static SCIP_Bool	isVarImpliedFree (SCIP scip, SCIP_MATRIX matrix, int col, int row, SCIP_Bool lockedcons, int impllbrowidx, int *implubrowidx)

static SCIP_Real	getFillIn (SCIP_MATRIX *matrix, int col, int row)

static SCIP_Real	sideChangeNumericalStable (SCIP *scip, SCIP_Real oldside, SCIP_Real aggrconst, SCIP_Real val)

static void	getNumHugeActivities (SCIP scip, SCIP_MATRIX matrix, int maxactposhuge, int maxactneghuge, int minactposhuge, int minactneghuge)

static void	getActivityRelax (SCIP scip, SCIP_MATRIX matrix, int row, int col, SCIP_Real val, int maxactposhuge, int maxactneghuge, int minactposhuge, int minactneghuge, SCIP_Bool minisrelax, SCIP_Bool maxisrelax)

static SCIP_Bool	numericalStable (SCIP scip, SCIP_MATRIX matrix, int col, int row, SCIP_Real aggrconst, int maxactposhuge, int maxactneghuge, int minactposhuge, int minactneghuge)

static void	calcNewSidesAfterAggregation (SCIP scip, SCIP_MATRIX matrix, int col, int row, SCIP_Real coef, SCIP_Real newlhs, SCIP_Real newrhs)

static SCIP_Bool	isConsRedundant (SCIP scip, SCIP_MATRIX matrix, int col, int row, SCIP_Real coef)

static void	getMultiaggVars (SCIP scip, SCIP_MATRIX matrix, SCIP_Bool multiaggvars, int nummultiaggvars, int multiaggequalities, SCIP_Bool consredundant, SCIP_Bool lockedcons, SCIP_Bool skipvars, int maxactposhuge, int maxactneghuge, int minactposhuge, int minactneghuge)

static	SCIP_DECL_PRESOLCOPY (presolCopyImplfree)

static	SCIP_DECL_PRESOLEXEC (presolExecImplfree)

SCIP_RETCODE	SCIPincludePresolImplfree (SCIP *scip)

Macro Definition Documentation

◆ PRESOL_NAME

#define PRESOL_NAME "implfree"

Definition at line 35 of file presol_implfree.c.

Referenced by SCIP_DECL_PRESOLCOPY(), and SCIPincludePresolImplfree().

◆ PRESOL_DESC

#define PRESOL_DESC "exploit implied free variables for multi-aggregation"

Definition at line 36 of file presol_implfree.c.

Referenced by SCIPincludePresolImplfree().

◆ PRESOL_PRIORITY

#define PRESOL_PRIORITY -1000

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

Definition at line 37 of file presol_implfree.c.

Referenced by SCIPincludePresolImplfree().

◆ PRESOL_MAXROUNDS

#define PRESOL_MAXROUNDS 0

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

Definition at line 38 of file presol_implfree.c.

Referenced by SCIPincludePresolImplfree().

◆ PRESOL_TIMING

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

Definition at line 39 of file presol_implfree.c.

Referenced by SCIPincludePresolImplfree().

◆ MAXABSRATIO

#define MAXABSRATIO ((SCIP_Real)1000.0)

max abs coefficients ratio

Definition at line 41 of file presol_implfree.c.

Referenced by numericalStable().

◆ SIDECHANGERATIO

#define SIDECHANGERATIO ((SCIP_Real)10.0)

max side change ratio

Definition at line 42 of file presol_implfree.c.

Referenced by sideChangeNumericalStable().

Function Documentation

◆ getMaxActSingleRowWithoutCol()

static SCIP_Real getMaxActSingleRowWithoutCol	(	SCIP *	scip,
		SCIP_MATRIX *	matrix,
		int	row,
		int	col
	)

static

calculate max activity of one row without one column

Parameters

scip	SCIP main data structure
matrix	matrix containing the constraints
row	row index
col	column index

Definition at line 51 of file presol_implfree.c.

References NULL, SCIP_Real, SCIPisInfinity(), SCIPmatrixGetColLb(), SCIPmatrixGetColUb(), SCIPmatrixGetRowIdxPtr(), SCIPmatrixGetRowNNonzs(), and SCIPmatrixGetRowValPtr().

Referenced by getActivityResiduals().

◆ getMinActSingleRowWithoutCol()

static SCIP_Real getMinActSingleRowWithoutCol	(	SCIP *	scip,
		SCIP_MATRIX *	matrix,
		int	row,
		int	col
	)

static

calculate min activity of one row without one column

Parameters

scip	SCIP main data structure
matrix	matrix containing the constraints
row	row index
col	column index

Definition at line 103 of file presol_implfree.c.

References NULL, SCIP_Real, SCIPisInfinity(), SCIPmatrixGetColLb(), SCIPmatrixGetColUb(), SCIPmatrixGetRowIdxPtr(), SCIPmatrixGetRowNNonzs(), and SCIPmatrixGetRowValPtr().

Referenced by getActivityResiduals().

◆ getActivityResiduals()

static void getActivityResiduals	(	SCIP *	scip,
		SCIP_MATRIX *	matrix,
		int	col,
		int	row,
		SCIP_Real	val,
		SCIP_Real *	minresactivity,
		SCIP_Real *	maxresactivity,
		SCIP_Bool *	isminsettoinfinity,
		SCIP_Bool *	ismaxsettoinfinity
	)

static

get min/max residual activity without the specified column

Parameters

scip	SCIP main data structure
matrix	matrix containing the constraints
col	column index
row	row index
val	coefficient of this variable in this row
minresactivity	minimum residual activity of this row
maxresactivity	maximum residual activity of this row
isminsettoinfinity	flag indicating if minresactiviy is set to infinity
ismaxsettoinfinity	flag indicating if maxresactiviy is set to infinity

Definition at line 155 of file presol_implfree.c.

References FALSE, getMaxActSingleRowWithoutCol(), getMinActSingleRowWithoutCol(), NULL, SCIP_Real, SCIPinfinity(), SCIPisInfinity(), SCIPmatrixGetColLb(), SCIPmatrixGetColUb(), SCIPmatrixGetRowMaxActivity(), SCIPmatrixGetRowMinActivity(), SCIPmatrixGetRowNMaxActNegInf(), SCIPmatrixGetRowNMaxActPosInf(), SCIPmatrixGetRowNMinActNegInf(), SCIPmatrixGetRowNMinActPosInf(), and TRUE.

Referenced by getVarBoundsOfRow(), and isConsRedundant().

◆ getVarBoundsOfRow()

static void getVarBoundsOfRow	(	SCIP *	scip,
		SCIP_MATRIX *	matrix,
		int	col,
		int	row,
		SCIP_Real	val,
		SCIP_Real *	rowlb,
		SCIP_Bool *	lbfound,
		SCIP_Real *	rowub,
		SCIP_Bool *	ubfound
	)

static

calculate the bounds of one variable from one row

Parameters

scip	SCIP main data structure
matrix	matrix containing the constraints
col	column index of variable
row	row index
val	coefficient of this column in this row
rowlb	lower bound of row
lbfound	flag indicating that a lower bound was calculated
rowub	upper bound of row
ubfound	flag indicating that an upper bound was calculated

Definition at line 296 of file presol_implfree.c.

References FALSE, getActivityResiduals(), NULL, SCIP_Bool, SCIP_Real, SCIPinfinity(), SCIPisInfinity(), SCIPmatrixGetRowLhs(), SCIPmatrixGetRowRhs(), and TRUE.

Referenced by isVarImpliedFree().

◆ isVarImpliedFree()

static SCIP_Bool isVarImpliedFree	(	SCIP *	scip,
		SCIP_MATRIX *	matrix,
		int	col,
		int	row,
		SCIP_Bool *	lockedcons,
		int *	impllbrowidx,
		int *	implubrowidx
	)

static

verify if the variable is implied free

Parameters

scip	SCIP main data structure
matrix	matrix containing the constraints
col	column index for implied free test
row	constraint planned for multi-aggregation
lockedcons	constraint not suitable for bound implication
impllbrowidx	row which implies the lower bound
implubrowidx	row which implied the upper bound

Definition at line 363 of file presol_implfree.c.

References FALSE, getVarBoundsOfRow(), NULL, SCIP_Bool, SCIP_Real, SCIPinfinity(), SCIPisFeasLE(), SCIPisInfinity(), SCIPmatrixGetColIdxPtr(), SCIPmatrixGetColLb(), SCIPmatrixGetColNNonzs(), SCIPmatrixGetColUb(), SCIPmatrixGetColValPtr(), and TRUE.

Referenced by getMultiaggVars().

◆ getFillIn()

static SCIP_Real getFillIn	(	SCIP_MATRIX *	matrix,
		int	col,
		int	row
	)

static

calculate the amount of fill-in getting from multi-aggregation

Parameters

matrix	constraint matrix object
col	column index
row	row index

Definition at line 446 of file presol_implfree.c.

References NULL, SCIP_Real, SCIPmatrixGetColNNonzs(), and SCIPmatrixGetRowNNonzs().

Referenced by getMultiaggVars().

◆ sideChangeNumericalStable()

static SCIP_Real sideChangeNumericalStable	(	SCIP *	scip,
		SCIP_Real	oldside,
		SCIP_Real	aggrconst,
		SCIP_Real	val
	)

static

verify if the multi-aggregation is numerical stable concerning the side change

Parameters

scip	current scip instance
oldside	old rhs or lhs of constraint
aggrconst	multiaggrconstant
val	coefficient of multiaggvariable not within the aggregated constraint

Definition at line 474 of file presol_implfree.c.

References MAX, REALABS, SCIP_Real, and SIDECHANGERATIO.

Referenced by numericalStable().

◆ getNumHugeActivities()

static void getNumHugeActivities	(	SCIP *	scip,
		SCIP_MATRIX *	matrix,
		int *	maxactposhuge,
		int *	maxactneghuge,
		int *	minactposhuge,
		int *	minactneghuge
	)

static

calculate the huge contribution counters

Parameters

scip	current scip instance
matrix	constraint matrix
maxactposhuge	max activity positive contribution counter
maxactneghuge	max activity negative contribution counter
minactposhuge	min activity positive contribution counter
minactneghuge	min activity negative contribution counter

Definition at line 492 of file presol_implfree.c.

References NULL, SCIP_Real, SCIPisHugeValue(), SCIPisInfinity(), SCIPmatrixGetColLb(), SCIPmatrixGetColUb(), SCIPmatrixGetNRows(), SCIPmatrixGetRowIdxPtr(), SCIPmatrixGetRowNNonzs(), and SCIPmatrixGetRowValPtr().

Referenced by SCIP_DECL_PRESOLEXEC().

◆ getActivityRelax()

static void getActivityRelax	(	SCIP *	scip,
		SCIP_MATRIX *	matrix,
		int	row,
		int	col,
		SCIP_Real	val,
		int *	maxactposhuge,
		int *	maxactneghuge,
		int *	minactposhuge,
		int *	minactneghuge,
		SCIP_Bool *	minisrelax,
		SCIP_Bool *	maxisrelax
	)

static

verify if activities could be inexact

Parameters

scip	SCIP data structure
matrix	constraint matrix object
row	row index
col	column index
val	coefficient value of variable in linear constraint
maxactposhuge	max activity positive contribution counter
maxactneghuge	max activity negative contribution counter
minactposhuge	min activity positive contribution counter
minactneghuge	min activity negative contribution counter
minisrelax	flag indicating min activity could be inexact
maxisrelax	flag indicating max activity could be inexact

Definition at line 577 of file presol_implfree.c.

References FALSE, SCIP_Real, SCIPisHugeValue(), SCIPisInfinity(), SCIPmatrixGetColLb(), SCIPmatrixGetColUb(), SCIPmatrixGetRowNMaxActNegInf(), SCIPmatrixGetRowNMaxActPosInf(), SCIPmatrixGetRowNMinActNegInf(), SCIPmatrixGetRowNMinActPosInf(), and TRUE.

Referenced by numericalStable().

◆ numericalStable()

static SCIP_Bool numericalStable	(	SCIP *	scip,
		SCIP_MATRIX *	matrix,
		int	col,
		int	row,
		SCIP_Real	aggrconst,
		int *	maxactposhuge,
		int *	maxactneghuge,
		int *	minactposhuge,
		int *	minactneghuge
	)

static

verify if the multi-aggregation is numerical stable

Parameters

scip	SCIP data structure
matrix	constraint matrix object
col	column index
row	row index
aggrconst	aggregation constant
maxactposhuge	max activity positive contribution counter
maxactneghuge	max activity negative contribution counter
minactposhuge	min activity positive contribution counter
minactneghuge	min activity negative contribution counter

Definition at line 728 of file presol_implfree.c.

References FALSE, getActivityRelax(), MAXABSRATIO, REALABS, SCIP_Bool, SCIP_Real, SCIPinfinity(), SCIPisInfinity(), SCIPmatrixGetColIdxPtr(), SCIPmatrixGetColNNonzs(), SCIPmatrixGetColValPtr(), SCIPmatrixGetRowIdxPtr(), SCIPmatrixGetRowLhs(), SCIPmatrixGetRowNNonzs(), SCIPmatrixGetRowRhs(), SCIPmatrixGetRowValPtr(), sideChangeNumericalStable(), and TRUE.

Referenced by getMultiaggVars().

◆ calcNewSidesAfterAggregation()

static void calcNewSidesAfterAggregation	(	SCIP *	scip,
		SCIP_MATRIX *	matrix,
		int	col,
		int	row,
		SCIP_Real	coef,
		SCIP_Real *	newlhs,
		SCIP_Real *	newrhs
	)

static

calculate sides after aggregation

Parameters

scip	SCIP data structure
matrix	constraint matrix object
col	column index
row	row index
coef	coefficient of aggregated variable
newlhs	new calculated left hand side
newrhs	new calculated right hand side

Definition at line 838 of file presol_implfree.c.

References NULL, SCIP_Real, SCIPinfinity(), SCIPisInfinity(), SCIPisLE(), SCIPmatrixGetColLb(), SCIPmatrixGetColUb(), SCIPmatrixGetRowLhs(), and SCIPmatrixGetRowRhs().

Referenced by isConsRedundant().

◆ isConsRedundant()

static SCIP_Bool isConsRedundant	(	SCIP *	scip,
		SCIP_MATRIX *	matrix,
		int	col,
		int	row,
		SCIP_Real	coef
	)

static

verify if the constraint becomes redundant after aggregation

Parameters

scip	SCIP data structure
matrix	constraint matrix object
col	column index
row	row index
coef	coefficient of aggregated variable

Definition at line 894 of file presol_implfree.c.

References calcNewSidesAfterAggregation(), FALSE, getActivityResiduals(), SCIP_Bool, SCIP_Real, and SCIPisFeasLE().

Referenced by getMultiaggVars().

◆ getMultiaggVars()

static void getMultiaggVars	(	SCIP *	scip,
		SCIP_MATRIX *	matrix,
		SCIP_Bool *	multiaggvars,
		int *	nummultiaggvars,
		int *	multiaggequalities,
		SCIP_Bool *	consredundant,
		SCIP_Bool *	lockedcons,
		SCIP_Bool *	skipvars,
		int *	maxactposhuge,
		int *	maxactneghuge,
		int *	minactposhuge,
		int *	minactneghuge
	)

static

identify candidates for multi-aggregation

Parameters

scip	SCIP data structure
matrix	constraint matrix object
multiaggvars	array indicating multi-aggregatable variables
nummultiaggvars	number of multi-aggregatable variables
multiaggequalities	array holding aggregation equality row indices
consredundant	array indicating which constraint became redundant
lockedcons	constraints which could not be used for bound implication
skipvars	array holding which variables should be investigated
maxactposhuge	max activity positive contribution counter
maxactneghuge	max activity negative contribution counter
minactposhuge	min activity positive contribution counter
minactneghuge	min activity negative contribution counter

Definition at line 923 of file presol_implfree.c.

References FALSE, getFillIn(), isConsRedundant(), isVarImpliedFree(), NULL, numericalStable(), SCIP_Bool, SCIP_Real, SCIP_VARTYPE_CONTINUOUS, SCIPisEQ(), SCIPmatrixGetNColumns(), SCIPmatrixGetNRows(), SCIPmatrixGetRowIdxPtr(), SCIPmatrixGetRowLhs(), SCIPmatrixGetRowNNonzs(), SCIPmatrixGetRowRhs(), SCIPmatrixGetRowValPtr(), SCIPmatrixGetVar(), SCIPvarGetType(), and TRUE.

Referenced by SCIP_DECL_PRESOLEXEC().

◆ SCIP_DECL_PRESOLCOPY()

static SCIP_DECL_PRESOLCOPY ( presolCopyImplfree )

static

copy method for constraint handler plugins (called when SCIP copies plugins)

Definition at line 1059 of file presol_implfree.c.

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

◆ SCIP_DECL_PRESOLEXEC()

static SCIP_DECL_PRESOLEXEC ( presolExecImplfree )

static

execution method of presolver

Definition at line 1074 of file presol_implfree.c.

References BMSclearMemoryArray, getMultiaggVars(), getNumHugeActivities(), NULL, scalars, SCIP_Bool, SCIP_CALL, SCIP_DIDNOTFIND, SCIP_DIDNOTRUN, SCIP_OKAY, SCIP_Real, SCIP_STAGE_PRESOLVING, SCIP_VARTYPE_CONTINUOUS, SCIPallocBufferArray, SCIPconsGetName(), SCIPdebugMsg, SCIPdebugMsgPrint, SCIPdelCons(), SCIPfreeBufferArray, SCIPgetNActivePricers(), SCIPgetNContVars(), SCIPgetNVars(), SCIPgetStage(), SCIPinProbing(), SCIPisEQ(), SCIPisInfinity(), SCIPisNLPEnabled(), SCIPisStopped(), SCIPmatrixCreate(), SCIPmatrixFree(), SCIPmatrixGetCons(), SCIPmatrixGetNColumns(), SCIPmatrixGetNRows(), SCIPmatrixGetRowIdxPtr(), SCIPmatrixGetRowLhs(), SCIPmatrixGetRowNNonzs(), SCIPmatrixGetRowRhs(), SCIPmatrixGetRowValPtr(), SCIPmatrixGetVar(), SCIPmultiaggregateVar(), SCIPvarGetLbGlobal(), SCIPvarGetName(), SCIPvarGetType(), and SCIPvarGetUbGlobal().

SCIP

Detailed Description

Macros

Functions

Macro Definition Documentation

◆ PRESOL_NAME

◆ PRESOL_DESC

◆ PRESOL_PRIORITY

◆ PRESOL_MAXROUNDS

◆ PRESOL_TIMING

◆ MAXABSRATIO

◆ SIDECHANGERATIO

Function Documentation

◆ getMaxActSingleRowWithoutCol()

◆ getMinActSingleRowWithoutCol()

◆ getActivityResiduals()

◆ getVarBoundsOfRow()

◆ isVarImpliedFree()

◆ getFillIn()

◆ sideChangeNumericalStable()

◆ getNumHugeActivities()

◆ getActivityRelax()

◆ numericalStable()

◆ calcNewSidesAfterAggregation()

◆ isConsRedundant()

◆ getMultiaggVars()

◆ SCIP_DECL_PRESOLCOPY()

◆ SCIP_DECL_PRESOLEXEC()