Detailed Description

do bound tightening by using two rows

Author: Dieter Weninger

Perform bound tightening on two inequalities with some common variables.

Let two constraints be given:

$\begin{eqnarray*} A_{iR} x_R + A_{iS} x_S \geq b_i\\ A_{kR} x_R + A_{kT} x_T \geq b_k \end{eqnarray*}$

with $N$ the set of variable indexes, $R \subseteq N$ , $S \subseteq N$ , $T \subseteq N$ , $R \cap S = \emptyset$ , $R \cap T = \emptyset$ , $S \cap T = \emptyset$ and $i \not= k$ .

Solve the following two LPs

$\begin{eqnarray*} L = \min \{ A_{kR} x_R : A_{iR} x_R + A_{iS} x_S \geq b_i \}\\ U = \max \{ A_{kR} x_R : A_{iR} x_R + A_{iS} x_S \geq b_i \} \end{eqnarray*}$

and use $L$ and $U$ for getting bounds on $x_T$ .

If $L + \mbox{infimum}(A_{kT}x_T) \geq b_k$ , then the second constraint above is redundant.

Definition in file presol_tworowbnd.c.

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

Go to the source code of this file.

Macros
#define	PRESOL_NAME "tworowbnd"

#define	PRESOL_DESC "do bound tigthening by using two rows"

#define	PRESOL_PRIORITY -500000

#define	PRESOL_MAXROUNDS 0

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

#define	SUPPORT_THRESHOLD 0.5

#define	FASTMODE_THRESHOLD 1000

Typedefs
typedef enum Bndchgtype	BNDCHGTYPE

Enumerations
enum	Bndchgtype { LOWERBOUND = 1, UPPERBOUND = 2, BOTHBOUNDS = 3 }

Functions
static void	getActivities (SCIP scip, SCIP_MATRIX matrix, int baserow, int otherrow, int numoverlap, int overlapidx, int othernonoverlapidx, SCIP_Real coefbaseoverlap, SCIP_Real coefotheroverlap, SCIP_Real coefothernonoverlap, SCIP_Real lowerbds, SCIP_Real upperbds, SCIP_Real tmplowerbds, SCIP_Real tmpupperbds, SCIP_Real minratios, SCIP_Real maxratios, int minsortedidx, int maxsortedidx, SCIP_Real minact, SCIP_Real *maxact)

static SCIP_Real	getMinActivity (SCIP scip, int len, int varidxs, SCIP_Real coefs, SCIP_Real lowerbds, SCIP_Real *upperbds)

static SCIP_Real	getMaxActivity (SCIP scip, int len, int varidxs, SCIP_Real coefs, SCIP_Real lowerbds, SCIP_Real upperbds, int infcnt)

static SCIP_Real	getMaxResActivity (SCIP scip, int len, int varidxs, SCIP_Real coefs, SCIP_Real lowerbds, SCIP_Real *upperbds, int idx)

static void	applyTightening (SCIP scip, SCIP_MATRIX matrix, int baserow, int otherrow, int numoverlap, int overlapidx, int othernonoverlapidx, int basenonoverlapidx, SCIP_Real coefbaseoverlap, SCIP_Real coefotheroverlap, SCIP_Real coefbasenonoverlap, SCIP_Real coefothernonoverlap, SCIP_Real lowerbds, SCIP_Real upperbds, SCIP_Real tmplowerbds, SCIP_Real tmpupperbds, SCIP_Real minratios, SCIP_Real maxratios, int minsortedidx, int maxsortedidx, int ntightenbnds, BNDCHGTYPE tighten, int ndeletecons, SCIP_Bool *deletecons)

static void	getCoefficients (SCIP scip, SCIP_MATRIX matrix, int baserow, int otherrow, int numoverlap, int olapidxbaseorder, int olapidxotherorder, int othernonoverlapidx, int basenonoverlapidx, SCIP_Real coefbaseoverlap, SCIP_Real coefotheroverlap, SCIP_Real coefbasenonoverlap, SCIP_Real coefothernonoverlap)

static void	getNumOverlap (SCIP scip, SCIP_MATRIX matrix, int baserow, int otherrow, int countings, int clearinfo, int numoverlap, int olapidxotherorder)

static void	getOverlapBaseOrdered (SCIP scip, SCIP_MATRIX matrix, int baserow, int otherrow, int countings, int clearinfo, int numoverlap, int *olapidxbaseorder)

static SCIP_RETCODE	calcTwoRowBnds (SCIP scip, SCIP_MATRIX matrix, int nbaserows, int baserows, SCIP_Real lowerbds, SCIP_Real upperbds, int ntightenbnds, BNDCHGTYPE tighten, int ndeletecons, SCIP_Bool *deletecons)

static SCIP_RETCODE	getBaseRows (SCIP scip, SCIP_MATRIX matrix, int nbaserows, int baserows)

static void	getBounds (SCIP scip, SCIP_MATRIX matrix, SCIP_Real lowerbds, SCIP_Real upperbds)

static	SCIP_DECL_PRESOLCOPY (presolCopyTworowbnd)

static	SCIP_DECL_PRESOLEXEC (presolExecTworowbnd)

SCIP_RETCODE	SCIPincludePresolTworowbnd (SCIP *scip)

Macro Definition Documentation

#define PRESOL_NAME "tworowbnd"

Definition at line 49 of file presol_tworowbnd.c.

Referenced by SCIP_DECL_PRESOLCOPY(), and SCIPincludePresolTworowbnd().

#define PRESOL_DESC "do bound tigthening by using two rows"

Definition at line 50 of file presol_tworowbnd.c.

Referenced by SCIPincludePresolTworowbnd().

#define PRESOL_PRIORITY -500000

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

Definition at line 51 of file presol_tworowbnd.c.

Referenced by SCIPincludePresolTworowbnd().

#define PRESOL_MAXROUNDS 0

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

Definition at line 52 of file presol_tworowbnd.c.

Referenced by SCIPincludePresolTworowbnd().

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

Definition at line 53 of file presol_tworowbnd.c.

Referenced by SCIPincludePresolTworowbnd().

#define SUPPORT_THRESHOLD 0.5

threshold for two constraints overlap

Definition at line 55 of file presol_tworowbnd.c.

Referenced by calcTwoRowBnds().

#define FASTMODE_THRESHOLD 1000

max number of baserows for switching to fast mode

Definition at line 56 of file presol_tworowbnd.c.

Referenced by calcTwoRowBnds().

Typedef Documentation

typedef enum Bndchgtype BNDCHGTYPE

Definition at line 68 of file presol_tworowbnd.c.

Enumeration Type Documentation

enum Bndchgtype

type of bound change

Enumerator
LOWERBOUND
UPPERBOUND
BOTHBOUNDS

Definition at line 62 of file presol_tworowbnd.c.

Function Documentation

static void getActivities	(	SCIP *	scip,
		SCIP_MATRIX *	matrix,
		int	baserow,
		int	otherrow,
		int	numoverlap,
		int *	overlapidx,
		int *	othernonoverlapidx,
		SCIP_Real *	coefbaseoverlap,
		SCIP_Real *	coefotheroverlap,
		SCIP_Real *	coefothernonoverlap,
		SCIP_Real *	lowerbds,
		SCIP_Real *	upperbds,
		SCIP_Real *	tmplowerbds,
		SCIP_Real *	tmpupperbds,
		SCIP_Real *	minratios,
		SCIP_Real *	maxratios,
		int *	minsortedidx,
		int *	maxsortedidx,
		SCIP_Real *	minact,
		SCIP_Real *	maxact
	)

static

solve two LPs with one row (single constraint) each

a1x + a3y >= b1 (other row) a2x + a4z >= b2 (base row)

minact = min{a2x : a1x + a3y >= b1} maxact = max{a2x : a1x + a3y >= b1}

Parameters

scip	SCIP data structure
matrix	constraint matrix object
baserow	base row index
otherrow	other row index
numoverlap	overlap-size
overlapidx	overlap column indexes
othernonoverlapidx	other row non overlap indexes
coefbaseoverlap	base row overlap coefficients
coefotheroverlap	other row overlap coefficients
coefothernonoverlap	other row non overlap coefficients
lowerbds	lower bounds
upperbds	upper bounds
tmplowerbds	tmp lower bounds
tmpupperbds	tmp upper bounds
minratios	min LP ratios
maxratios	max LP ratios
minsortedidx	min LP sorted indexes
maxsortedidx	max LP sorted indexes
minact	calculated overlap minimal activity w.r.t. to the other row
maxact	calculated overlap maximal activity w.r.t. to the other row

Definition at line 224 of file presol_tworowbnd.c.

References FALSE, NULL, SCIP_Bool, SCIP_LONGINT_MAX, SCIP_Real, SCIP_STATUS_OPTIMAL, SCIPcreate(), SCIPfree(), SCIPgetBestSol(), SCIPgetNVars(), SCIPgetSolOrigObj(), SCIPgetStatus(), SCIPgetVars(), SCIPincludeDefaultPlugins(), SCIPinfinity(), SCIPisEQ(), SCIPisInfinity(), SCIPmatrixGetRowLhs(), SCIPmatrixGetRowNNonzs(), SCIPmatrixPrintRow(), SCIPreadProb(), SCIPsetIntParam(), SCIPsolve(), SCIPsortRealInt(), SCIPvarGetObj(), and TRUE.

Referenced by applyTightening().

static SCIP_Real getMinActivity	(	SCIP *	scip,
		int	len,
		int *	varidxs,
		SCIP_Real *	coefs,
		SCIP_Real *	lowerbds,
		SCIP_Real *	upperbds
	)

static

calculate min activity

Parameters

scip	SCIP data structure
len	length
varidxs	variables indexes
coefs	coefficients
lowerbds	lower bounds
upperbds	upper bounds

Definition at line 660 of file presol_tworowbnd.c.

References SCIP_Real, SCIPinfinity(), and SCIPisInfinity().

Referenced by applyTightening().

static SCIP_Real getMaxActivity	(	SCIP *	scip,
		int	len,
		int *	varidxs,
		SCIP_Real *	coefs,
		SCIP_Real *	lowerbds,
		SCIP_Real *	upperbds,
		int *	infcnt
	)

static

calculate max activity

Parameters

scip	SCIP data structure
len	length
varidxs	variable indexes
coefs	coefficients
lowerbds	lower bounds
upperbds	upper bounds
infcnt	infinity counter

Definition at line 707 of file presol_tworowbnd.c.

References SCIP_Real, SCIPinfinity(), and SCIPisInfinity().

Referenced by applyTightening().

static SCIP_Real getMaxResActivity	(	SCIP *	scip,
		int	len,
		int *	varidxs,
		SCIP_Real *	coefs,
		SCIP_Real *	lowerbds,
		SCIP_Real *	upperbds,
		int	idx
	)

static

get max activity without one column

Parameters

scip	SCIP data structure
len	length
varidxs	variable indexes
coefs	coefficients
lowerbds	upper bounds
upperbds	lower bounds
idx	omitting index

Definition at line 749 of file presol_tworowbnd.c.

References SCIP_Real, and SCIPisInfinity().

Referenced by applyTightening().

static void applyTightening	(	SCIP *	scip,
		SCIP_MATRIX *	matrix,
		int	baserow,
		int	otherrow,
		int	numoverlap,
		int *	overlapidx,
		int *	othernonoverlapidx,
		int *	basenonoverlapidx,
		SCIP_Real *	coefbaseoverlap,
		SCIP_Real *	coefotheroverlap,
		SCIP_Real *	coefbasenonoverlap,
		SCIP_Real *	coefothernonoverlap,
		SCIP_Real *	lowerbds,
		SCIP_Real *	upperbds,
		SCIP_Real *	tmplowerbds,
		SCIP_Real *	tmpupperbds,
		SCIP_Real *	minratios,
		SCIP_Real *	maxratios,
		int *	minsortedidx,
		int *	maxsortedidx,
		int *	ntightenbnds,
		BNDCHGTYPE *	tighten,
		int *	ndeletecons,
		SCIP_Bool *	deletecons
	)

static

apply bound tightening on two overlapping constraints

Parameters

scip	SCIP data structure
matrix	constraint matrix object
baserow	base row index
otherrow	other row index
numoverlap	overlap-size
overlapidx	overlap column indexes
othernonoverlapidx	other row non overlap indexes
basenonoverlapidx	base row non overlap indexes
coefbaseoverlap	base row overlap coefficients
coefotheroverlap	other row overlap coefficients
coefbasenonoverlap	base row non overlap coefficients
coefothernonoverlap	other row non overlap coefficients
lowerbds	lower bounds
upperbds	upper bounds
tmplowerbds	tmp lower bounds
tmpupperbds	tmp upper bounds
minratios	min LP ratios
maxratios	max LP ratios
minsortedidx	min LP sorted indexes
maxsortedidx	max LP sorted indexes
ntightenbnds	number of tightened bounds
tighten	tightened bounds
ndeletecons	number of redundant constraints
deletecons	redundant constraints

Definition at line 786 of file presol_tworowbnd.c.

References BOTHBOUNDS, getActivities(), getMaxActivity(), getMaxResActivity(), getMinActivity(), LOWERBOUND, SCIP_Real, SCIPisGE(), SCIPisInfinity(), SCIPmatrixGetRowLhs(), SCIPmatrixGetRowNNonzs(), TRUE, and UPPERBOUND.

Referenced by calcTwoRowBnds().

static void getCoefficients	(	SCIP *	scip,
		SCIP_MATRIX *	matrix,
		int	baserow,
		int	otherrow,
		int	numoverlap,
		int *	olapidxbaseorder,
		int *	olapidxotherorder,
		int *	othernonoverlapidx,
		int *	basenonoverlapidx,
		SCIP_Real *	coefbaseoverlap,
		SCIP_Real *	coefotheroverlap,
		SCIP_Real *	coefbasenonoverlap,
		SCIP_Real *	coefothernonoverlap
	)

static

extract coefficients from matrix

Parameters

scip	SCIP data structure
matrix	constraint matrix object
baserow	base row index
otherrow	other row index
numoverlap	overlap-size
olapidxbaseorder	overlap column indexes in baserow order
olapidxotherorder	overlap column indexes in otherrow order
othernonoverlapidx	other row non overlap indexes
basenonoverlapidx	base row non overlap indexes
coefbaseoverlap	base row overlap coefficients
coefotheroverlap	other row overlap coefficients
coefbasenonoverlap	base row non overlap coefficients
coefothernonoverlap	other row non overlap coefficients

Definition at line 956 of file presol_tworowbnd.c.

References SCIP_Real, SCIPmatrixGetNColumns(), SCIPmatrixGetRowIdxPtr(), SCIPmatrixGetRowNNonzs(), and SCIPmatrixGetRowValPtr().

Referenced by calcTwoRowBnds().

static void getNumOverlap	(	SCIP *	scip,
		SCIP_MATRIX *	matrix,
		int	baserow,
		int	otherrow,
		int *	countings,
		int *	clearinfo,
		int *	numoverlap,
		int *	olapidxotherorder
	)

static

calculate overlap-size

Parameters

scip	SCIP data structure
matrix	constraint matrix object
baserow	base row index
otherrow	other row index
countings	overlap counting helper array
clearinfo	reset helper array
numoverlap	overlap-size
olapidxotherorder	overlap column indexes in otherrow order

Definition at line 1054 of file presol_tworowbnd.c.

References SCIPmatrixGetRowIdxPtr(), and SCIPmatrixGetRowNNonzs().

Referenced by calcTwoRowBnds().

static void getOverlapBaseOrdered	(	SCIP *	scip,
		SCIP_MATRIX *	matrix,
		int	baserow,
		int	otherrow,
		int *	countings,
		int *	clearinfo,
		int	numoverlap,
		int *	olapidxbaseorder
	)

static

Parameters

scip	SCIP data structure
matrix	constraint matrix object
baserow	base row index
otherrow	other row index
countings	overlap counting helper array
clearinfo	reset helper array
numoverlap	just calculated overlap-size
olapidxbaseorder	overlap column indexes in baserow order

Definition at line 1113 of file presol_tworowbnd.c.

References SCIPmatrixGetRowIdxPtr(), and SCIPmatrixGetRowNNonzs().

Referenced by calcTwoRowBnds().

static SCIP_RETCODE calcTwoRowBnds	(	SCIP *	scip,
		SCIP_MATRIX *	matrix,
		int	nbaserows,
		int *	baserows,
		SCIP_Real *	lowerbds,
		SCIP_Real *	upperbds,
		int *	ntightenbnds,
		BNDCHGTYPE *	tighten,
		int *	ndeletecons,
		SCIP_Bool *	deletecons
	)

static

perform bound tightening on two rows with a specific support intersection

Parameters

scip	SCIP data structure
matrix	constraint matrix object
nbaserows	number of base rows
baserows	base rows indexes
lowerbds	lower bounds
upperbds	upper bounds
ntightenbnds	number of tightened bounds
tighten	bound tighten information
ndeletecons	number of redundant constraints
deletecons	redundant constraints