Detailed Description

do bound tightening by using two rows

Author: Dieter Weninger; Patrick Gemander

Perform bound tightening on two inequalities with some common variables. Two possible methods are being used.

LP-bound 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 row indices \(i \not= k\).

Let \(\ell\) and \(u\) be bound vectors for x and solve the following two LPs

\begin{eqnarray*} L = \min \{ A_{kR} x_R : A_{iR} x_R + A_{iS} x_S \geq b_i, \ell \leq x \leq u \}\\ U = \max \{ A_{kR} x_R : A_{iR} x_R + A_{iS} x_S \geq b_i, \ell \leq x \leq u \} \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.

More details can be found in

Chen W. et. al "Two-row and two-column mixed-integer presolve using hashing-based pairing methods"

Definition in file presol_tworowbnd.c.

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

Go to the source code of this file.

Data Structures
struct	RowPair

Macros
#define	PRESOL_NAME "tworowbnd"

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

#define	PRESOL_PRIORITY -2000

#define	PRESOL_MAXROUNDS 0

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

#define	DEFAULT_ENABLECOPY TRUE

#define	DEFAULT_MAXCONSIDEREDNONZEROS 100

#define	DEFAULT_MAXRETRIEVEFAILS 1000

#define	DEFAULT_MAXCOMBINEFAILS 1000

#define	DEFAULT_MAXHASHFAC 10

#define	DEFAULT_MAXPAIRFAC 1

Typedefs
typedef struct RowPair	ROWPAIR

Functions
static void *	encodeRowPair (ROWPAIR *rowpair)

static int	hashIndexPair (int idx1, int idx2)

static SCIP_RETCODE	addEntry (SCIP scip, int pos, int listsize, int hashlist, int *rowidxlist, int hash, int rowidx)

static void	findNextBlock (int list, int len, int start, int *end)

static SCIP_RETCODE	solveSingleRowLP (SCIP scip, SCIP_Real a, SCIP_Real b, SCIP_Real c, SCIP_Real lbs, SCIP_Real ubs, int len, SCIP_Real obj, SCIP_Bool *solvable)

static SCIP_RETCODE	transformAndSolve (SCIP scip, SCIP_MATRIX matrix, int row1idx, int row2idx, SCIP_Bool swaprow1, SCIP_Bool swaprow2, SCIP_Real aoriginal, SCIP_Real acopy, SCIP_Real coriginal, SCIP_Real ccopy, SCIP_Bool cangetbnd, SCIP_Real lbs, SCIP_Real ubs, SCIP_Real newlbsoriginal, SCIP_Real newlbscopy, SCIP_Real newubsoriginal, SCIP_Real newubscopy, SCIP_Bool success, SCIP_Bool *infeasible)

static SCIP_RETCODE	applyLPboundTightening (SCIP scip, SCIP_MATRIX matrix, int row1, int row2, SCIP_Bool swaprow1, SCIP_Bool swaprow2, SCIP_Real lbs, SCIP_Real ubs, SCIP_Bool *success)

static SCIP_RETCODE	processHashlists (SCIP scip, SCIP_PRESOLDATA presoldata, SCIP_MATRIX matrix, int hashlist1, int hashlist2, int lenhashlist1, int lenhashlist2, int rowidxlist1, int rowidxlist2, SCIP_Real newlbs, SCIP_Real *newubs)

static	SCIP_DECL_PRESOLCOPY (presolCopyTworowbnd)

static	SCIP_DECL_PRESOLFREE (presolFreeTworowbnd)

static	SCIP_DECL_PRESOLINIT (presolInitTworowbnd)

static	SCIP_DECL_PRESOLEXEC (presolExecTworowbnd)

SCIP_RETCODE	SCIPincludePresolTworowbnd (SCIP *scip)

Macro Definition Documentation

◆ PRESOL_NAME

#define PRESOL_NAME "tworowbnd"

Definition at line 73 of file presol_tworowbnd.c.

◆ PRESOL_DESC

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

Definition at line 74 of file presol_tworowbnd.c.

◆ PRESOL_PRIORITY

#define PRESOL_PRIORITY -2000

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

Definition at line 75 of file presol_tworowbnd.c.

◆ PRESOL_MAXROUNDS

#define PRESOL_MAXROUNDS 0

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

Definition at line 76 of file presol_tworowbnd.c.

◆ PRESOL_TIMING

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

Definition at line 77 of file presol_tworowbnd.c.

◆ DEFAULT_ENABLECOPY

#define DEFAULT_ENABLECOPY TRUE

should tworowbnd presolver be copied to sub-SCIPs?

Definition at line 79 of file presol_tworowbnd.c.

◆ DEFAULT_MAXCONSIDEREDNONZEROS

#define DEFAULT_MAXCONSIDEREDNONZEROS 100

maximal number of considered non-zeros within one row (-1: no limit)

Definition at line 80 of file presol_tworowbnd.c.

◆ DEFAULT_MAXRETRIEVEFAILS

#define DEFAULT_MAXRETRIEVEFAILS 1000

maximal number of consecutive useless hashtable retrieves

Definition at line 81 of file presol_tworowbnd.c.

◆ DEFAULT_MAXCOMBINEFAILS

#define DEFAULT_MAXCOMBINEFAILS 1000

maximal number of consecutive useless row combines

Definition at line 82 of file presol_tworowbnd.c.

◆ DEFAULT_MAXHASHFAC

#define DEFAULT_MAXHASHFAC 10

maximal number of hashlist entries as multiple of number of rows in the problem (-1: no limit)

Definition at line 83 of file presol_tworowbnd.c.

◆ DEFAULT_MAXPAIRFAC

#define DEFAULT_MAXPAIRFAC 1

maximal number of processed row pairs as multiple of the number of rows in the problem (-1: no limit)

Definition at line 84 of file presol_tworowbnd.c.

Typedef Documentation

◆ ROWPAIR

typedef struct RowPair ROWPAIR

Definition at line 110 of file presol_tworowbnd.c.

Function Documentation

◆ encodeRowPair()

static void * encodeRowPair ( ROWPAIR * rowpair )

static

encode contents of a rowpair as void* pointer

Parameters

rowpair pointer to rowpair

Definition at line 119 of file presol_tworowbnd.c.

References a, b, RowPair::row1idx, and RowPair::row2idx.

Referenced by processHashlists().

◆ hashIndexPair()

static int hashIndexPair	(	int	idx1,
		int	idx2
	)

static

compute single positive int hashvalue for two ints

Parameters

idx1	first integer index
idx2	second integer index

Definition at line 130 of file presol_tworowbnd.c.

References SCIPhashTwo.

Referenced by SCIP_DECL_PRESOLEXEC().

◆ addEntry()

static SCIP_RETCODE addEntry	(	SCIP *	scip,
		int *	pos,
		int *	listsize,
		int **	hashlist,
		int **	rowidxlist,
		int	hash,
		int	rowidx
	)

static

add hash/rowidx pair to hashlist/rowidxlist

Parameters

scip	SCIP datastructure
pos	position of last entry added
listsize	size of hashlist and rowidxlist
hashlist	block memory array containing hashes
rowidxlist	block memory array containing row indices
hash	hash to be inserted
rowidx	row index to be inserted

Definition at line 141 of file presol_tworowbnd.c.

References SCIP_CALL, SCIP_OKAY, SCIPcalcMemGrowSize(), and SCIPreallocBlockMemoryArray.

Referenced by SCIP_DECL_PRESOLEXEC().

◆ findNextBlock()

static void findNextBlock	(	int *	list,
		int	len,
		int *	start,
		int *	end
	)

static

Parameters

list	list of integers
len	length of list
start	variable to contain start index of found block
end	variable to contain end index of found block

Definition at line 173 of file presol_tworowbnd.c.

Referenced by processHashlists().

◆ solveSingleRowLP()

static SCIP_RETCODE solveSingleRowLP	(	SCIP *	scip,
		SCIP_Real *	a,
		SCIP_Real	b,
		SCIP_Real *	c,
		SCIP_Real *	lbs,
		SCIP_Real *	ubs,
		int	len,
		SCIP_Real *	obj,
		SCIP_Bool *	solvable
	)

static

Parameters

scip	SCIP data structure
a	constraint coefficients
b	right hand side
c	objective coefficients
lbs	lower variable bounds
ubs	upper variable bounds
len	length of arrays
obj	objective value of solution
solvable	status whether LP was solvable

Definition at line 200 of file presol_tworowbnd.c.

References a, b, FALSE, MAX, MIN, SCIP_OKAY, SCIP_Real, SCIPdebugMsg, SCIPinfinity(), SCIPisEQ(), SCIPisInfinity(), SCIPisLE(), SCIPisLT(), SCIPisNegative(), SCIPisPositive(), SCIPisZero(), SCIPselectWeightedReal(), and TRUE.

Referenced by transformAndSolve().

◆ transformAndSolve()

static SCIP_RETCODE transformAndSolve	(	SCIP *	scip,
		SCIP_MATRIX *	matrix,
		int	row1idx,
		int	row2idx,
		SCIP_Bool	swaprow1,
		SCIP_Bool	swaprow2,
		SCIP_Real *	aoriginal,
		SCIP_Real *	acopy,
		SCIP_Real *	coriginal,
		SCIP_Real *	ccopy,
		SCIP_Bool *	cangetbnd,
		SCIP_Real *	lbs,
		SCIP_Real *	ubs,
		SCIP_Real *	newlbsoriginal,
		SCIP_Real *	newlbscopy,
		SCIP_Real *	newubsoriginal,
		SCIP_Real *	newubscopy,
		SCIP_Bool *	success,
		SCIP_Bool *	infeasible
	)

static

Transform rows into single row LPs, solve them and and tighten bounds

During transformation, create coefficient arrays where variables with a zero coefficient in both rows are ignored and bring the LP in the form min c^T x, s.t. a^T x >= b, lbs <= x <= ubs. These LPs are then solved and bounds tightened as described in LP-bound (see above).

Parameters

scip	SCIP data structure
matrix	constraint matrix object, rows specified by row1idx/row2idx must be sorted
row1idx	index of first row
row2idx	index of second row
swaprow1	should row1 <= rhs be used in addition to lhs <= row1
swaprow2	should row2 <= rhs be used in addition to lhs <= row2
aoriginal	buffer array for original constraint coefficients
acopy	buffer array for coefficients adjusted to single-row LP to be solved
coriginal	buffer array for original objective coefficients
ccopy	buffer array for coefficients adjusted to single-row LP to be solved
cangetbnd	buffer array for flags of which variables a bound can be generated
lbs	buffer array for lower bounds for single-row LP
ubs	buffer array for upper bounds for single-row LP
newlbsoriginal	buffer array for new lower bounds not adjusted to individual single-row LPs
newlbscopy	buffer array for adjusted lower bounds
newubsoriginal	buffer array for new upper bounds not adjusted to individual single-row LPs
newubscopy	buffer array for adjusted upper bounds
success	return (success \|\| "found better bounds")
infeasible	we return (infeasible \|\| "detected infeasibility")

Definition at line 546 of file presol_tworowbnd.c.

References FALSE, MAX, RowPair::row1idx, RowPair::row2idx, SCIP_Bool, SCIP_CALL, SCIP_INVALID, SCIP_OKAY, SCIP_Real, SCIPceil(), SCIPdebugMsg, SCIPfloor(), SCIPisGT(), SCIPisInfinity(), SCIPisLT(), SCIPisNegative(), SCIPisPositive(), SCIPmatrixGetColName(), SCIPmatrixGetRowIdxPtr(), SCIPmatrixGetRowLhs(), SCIPmatrixGetRowNNonzs(), SCIPmatrixGetRowRhs(), SCIPmatrixGetRowValPtr(), SCIPmatrixGetVar(), SCIPvarGetName(), SCIPvarIsIntegral(), solveSingleRowLP(), and TRUE.

Referenced by applyLPboundTightening().

◆ applyLPboundTightening()

static SCIP_RETCODE applyLPboundTightening	(	SCIP *	scip,
		SCIP_MATRIX *	matrix,
		int	row1,
		int	row2,
		SCIP_Bool	swaprow1,
		SCIP_Bool	swaprow2,
		SCIP_Real *	lbs,
		SCIP_Real *	ubs,
		SCIP_Bool *	success
	)

static

create required buffer arrays and apply LP-based bound tightening in both directions

Parameters

scip	SCIP data structure
matrix	constraint matrix object
row1	index of first row
row2	index of seond row
swaprow1	should row1 <= rhs be used in addition to lhs <= row1
swaprow2	should row2 <= rhs be used in addition to lhs <= row2
lbs	lower variable bounds
ubs	upper variable bounds
success	return (success \|\| "found better bounds")

Definition at line 1071 of file presol_tworowbnd.c.

References FALSE, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPdebugMsg, SCIPfreeBufferArray, SCIPmatrixGetNColumns(), SCIPmatrixGetRowIdxPtr(), SCIPmatrixGetRowName(), SCIPmatrixGetRowNNonzs(), SCIPmatrixGetRowValPtr(), SCIPsortIntReal(), and transformAndSolve().

Referenced by processHashlists().

◆ processHashlists()

static SCIP_RETCODE processHashlists	(	SCIP *	scip,
		SCIP_PRESOLDATA *	presoldata,
		SCIP_MATRIX *	matrix,
		int *	hashlist1,
		int *	hashlist2,
		int	lenhashlist1,
		int	lenhashlist2,
		int *	rowidxlist1,
		int *	rowidxlist2,
		SCIP_Real *	newlbs,
		SCIP_Real *	newubs
	)

static

Parameters

scip	SCIP data structure
presoldata	presolver data structure
matrix	constraint matrix object
hashlist1	first list of hashes
hashlist2	second list of hashes
lenhashlist1	length of first hashlist
lenhashlist2	length of second hashlist
rowidxlist1	list of row indices corresponding to hashes in hashlist1
rowidxlist2	list of row indices corresponding to hashes in hashlist2
newlbs	lower variable bounds, new bounds will be written here
newubs	upper variable bounds, new bound will be written here

Definition at line 1143 of file presol_tworowbnd.c.

References applyLPboundTightening(), encodeRowPair(), FALSE, findNextBlock(), MAX, MIN, RowPair::row1idx, RowPair::row2idx, SCIP_Bool, SCIP_CALL, SCIP_Longint, SCIP_LONGINT_MAX, SCIP_OKAY, SCIPblkmem(), SCIPhashsetCreate(), SCIPhashsetExists(), SCIPhashsetFree(), SCIPhashsetInsert(), SCIPisInfinity(), SCIPisStopped(), SCIPmatrixGetNRows(), SCIPmatrixGetRowLhs(), SCIPmatrixGetRowRhs(), and TRUE.

Referenced by SCIP_DECL_PRESOLEXEC().

◆ SCIP_DECL_PRESOLCOPY()

static SCIP_DECL_PRESOLCOPY ( presolCopyTworowbnd )

static

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

Definition at line 1273 of file presol_tworowbnd.c.

References NULL, PRESOL_NAME, SCIP_CALL, SCIP_OKAY, SCIPincludePresolTworowbnd(), SCIPpresolGetData(), and SCIPpresolGetName().

◆ SCIP_DECL_PRESOLFREE()

static SCIP_DECL_PRESOLFREE ( presolFreeTworowbnd )

static

destructor of presolver to free user data (called when SCIP is exiting)

Definition at line 1294 of file presol_tworowbnd.c.

References NULL, SCIP_OKAY, SCIPfreeBlockMemory, SCIPpresolGetData(), and SCIPpresolSetData().

◆ SCIP_DECL_PRESOLINIT()

static SCIP_DECL_PRESOLINIT ( presolInitTworowbnd )

static

initialization method of presolver (called after problem was transformed)

Definition at line 1310 of file presol_tworowbnd.c.

References SCIP_OKAY, and SCIPpresolGetData().

◆ SCIP_DECL_PRESOLEXEC()

static SCIP_DECL_PRESOLEXEC ( presolExecTworowbnd )

static

execution method of presolver

Definition at line 1323 of file presol_tworowbnd.c.

References addEntry(), FALSE, hashIndexPair(), MIN, NULL, processHashlists(), SCIP_Bool, SCIP_CALL, SCIP_CUTOFF, SCIP_DIDNOTFIND, SCIP_DIDNOTRUN, SCIP_Longint, SCIP_LONGINT_MAX, SCIP_OKAY, SCIP_Real, SCIP_SUCCESS, SCIPallocBlockMemoryArray, SCIPallocBufferArray, SCIPceil(), SCIPdebugMessage, SCIPdebugMsg, SCIPfixVar(), SCIPfloor(), SCIPfreeBlockMemoryArray, SCIPfreeBufferArray, SCIPisEQ(), SCIPisGT(), SCIPisInfinity(), SCIPisLT(), SCIPisPositive(), SCIPisStopped(), SCIPmatrixCreate(), SCIPmatrixFree(), SCIPmatrixGetNColumns(), SCIPmatrixGetNRows(), SCIPmatrixGetRowIdxPtr(), SCIPmatrixGetRowNNonzs(), SCIPmatrixGetRowRhs(), SCIPmatrixGetRowValPtr(), SCIPmatrixGetVar(), SCIPpresolGetData(), SCIPsortIntInt(), SCIPtightenVarLb(), SCIPtightenVarUb(), SCIPvarGetLbLocal(), SCIPvarGetName(), SCIPvarGetUbLocal(), SCIPvarIsNonimpliedIntegral(), and TRUE.

SCIP

Detailed Description

Data Structures

Macros

Typedefs

Functions

Macro Definition Documentation

◆ PRESOL_NAME

◆ PRESOL_DESC

◆ PRESOL_PRIORITY

◆ PRESOL_MAXROUNDS

◆ PRESOL_TIMING

◆ DEFAULT_ENABLECOPY

◆ DEFAULT_MAXCONSIDEREDNONZEROS

◆ DEFAULT_MAXRETRIEVEFAILS

◆ DEFAULT_MAXCOMBINEFAILS

◆ DEFAULT_MAXHASHFAC

◆ DEFAULT_MAXPAIRFAC

Typedef Documentation

◆ ROWPAIR

Function Documentation

◆ encodeRowPair()

◆ hashIndexPair()

◆ addEntry()

◆ findNextBlock()

◆ solveSingleRowLP()

◆ transformAndSolve()

◆ applyLPboundTightening()

◆ processHashlists()

◆ SCIP_DECL_PRESOLCOPY()

◆ SCIP_DECL_PRESOLFREE()

◆ SCIP_DECL_PRESOLINIT()

◆ SCIP_DECL_PRESOLEXEC()