Scippy

SCIP

Solving Constraint Integer Programs

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.

  1. 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 64 of file presol_tworowbnd.c.

Referenced by SCIP_DECL_PRESOLCOPY(), and SCIPincludePresolTworowbnd().

◆ PRESOL_DESC

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

Definition at line 65 of file presol_tworowbnd.c.

Referenced by SCIPincludePresolTworowbnd().

◆ PRESOL_PRIORITY

#define PRESOL_PRIORITY   -2000

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

Definition at line 66 of file presol_tworowbnd.c.

Referenced by SCIPincludePresolTworowbnd().

◆ PRESOL_MAXROUNDS

#define PRESOL_MAXROUNDS   0

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

Definition at line 67 of file presol_tworowbnd.c.

Referenced by SCIPincludePresolTworowbnd().

◆ PRESOL_TIMING

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

Definition at line 68 of file presol_tworowbnd.c.

Referenced by SCIPincludePresolTworowbnd().

◆ DEFAULT_ENABLECOPY

#define DEFAULT_ENABLECOPY   TRUE

should tworowbnd presolver be copied to sub-SCIPs?

Definition at line 70 of file presol_tworowbnd.c.

Referenced by SCIPincludePresolTworowbnd().

◆ DEFAULT_MAXCONSIDEREDNONZEROS

#define DEFAULT_MAXCONSIDEREDNONZEROS   100

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

Definition at line 71 of file presol_tworowbnd.c.

Referenced by SCIPincludePresolTworowbnd().

◆ DEFAULT_MAXRETRIEVEFAILS

#define DEFAULT_MAXRETRIEVEFAILS   1000

maximal number of consecutive useless hashtable retrieves

Definition at line 72 of file presol_tworowbnd.c.

Referenced by SCIPincludePresolTworowbnd().

◆ DEFAULT_MAXCOMBINEFAILS

#define DEFAULT_MAXCOMBINEFAILS   1000

maximal number of consecutive useless row combines

Definition at line 73 of file presol_tworowbnd.c.

Referenced by SCIPincludePresolTworowbnd().

◆ 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 74 of file presol_tworowbnd.c.

Referenced by SCIPincludePresolTworowbnd().

◆ 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 75 of file presol_tworowbnd.c.

Referenced by SCIPincludePresolTworowbnd().

Typedef Documentation

◆ ROWPAIR

typedef struct RowPair ROWPAIR

Definition at line 101 of file presol_tworowbnd.c.

Function Documentation

◆ encodeRowPair()

static void* encodeRowPair ( ROWPAIR rowpair)
static

encode contents of a rowpair as void* pointer

Parameters
rowpairpointer to rowpair

Definition at line 110 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
idx1first integer index
idx2second integer index

Definition at line 121 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
scipSCIP datastructure
posposition of last entry added
listsizesize of hashlist and rowidxlist
hashlistblock memory array containing hashes
rowidxlistblock memory array containing row indices
hashhash to be inserted
rowidxrow index to be inserted

Definition at line 132 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
listlist of integers
lenlength of list
startvariable to contain start index of found block
endvariable to contain end index of found block

Definition at line 164 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
scipSCIP data structure
aconstraint coefficients
bright hand side
cobjective coefficients
lbslower variable bounds
ubsupper variable bounds
lenlength of arrays
objobjective value of solution
solvablestatus whether LP was solvable

Definition at line 191 of file presol_tworowbnd.c.

References b, FALSE, MAX, 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
scipSCIP data structure
matrixconstraint matrix object, rows specified by row1idx/row2idx must be sorted
row1idxindex of first row
row2idxindex of second row
swaprow1should row1 <= rhs be used in addition to lhs <= row1
swaprow2should row2 <= rhs be used in addition to lhs <= row2
aoriginalbuffer array for original constraint coefficients
acopybuffer array for coefficients adjusted to single-row LP to be solved
coriginalbuffer array for original objective coefficients
ccopybuffer array for coefficients adjusted to single-row LP to be solved
cangetbndbuffer array for flags of which variables a bound can be generated
lbsbuffer array for lower bounds for single-row LP
ubsbuffer array for upper bounds for single-row LP
newlbsoriginalbuffer array for new lower bounds not adjusted to individual single-row LPs
newlbscopybuffer array for adjusted lower bounds
newubsoriginalbuffer array for new upper bounds not adjusted to individual single-row LPs
newubscopybuffer array for adjusted upper bounds
successreturn (success || "found better bounds")
infeasiblewe return (infeasible || "detected infeasibility")

Definition at line 537 of file presol_tworowbnd.c.

References FALSE, MAX, SCIP_Bool, SCIP_CALL, SCIP_INVALID, SCIP_OKAY, SCIP_Real, SCIP_VARTYPE_BINARY, SCIP_VARTYPE_IMPLINT, SCIP_VARTYPE_INTEGER, SCIPceil(), SCIPdebugMsg, SCIPfloor(), SCIPisGT(), SCIPisInfinity(), SCIPisLT(), SCIPisNegative(), SCIPisPositive(), SCIPmatrixGetColName(), SCIPmatrixGetRowIdxPtr(), SCIPmatrixGetRowLhs(), SCIPmatrixGetRowNNonzs(), SCIPmatrixGetRowRhs(), SCIPmatrixGetRowValPtr(), SCIPmatrixGetVar(), SCIPvarGetName(), SCIPvarGetType(), 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
scipSCIP data structure
matrixconstraint matrix object
row1index of first row
row2index of seond row
swaprow1should row1 <= rhs be used in addition to lhs <= row1
swaprow2should row2 <= rhs be used in addition to lhs <= row2
lbslower variable bounds
ubsupper variable bounds
successreturn (success || "found better bounds")

Definition at line 1078 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
scipSCIP data structure
presoldatapresolver data structure
matrixconstraint matrix object
hashlist1first list of hashes
hashlist2second list of hashes
lenhashlist1length of first hashlist
lenhashlist2length of second hashlist
rowidxlist1list of row indices corresponding to hashes in hashlist1
rowidxlist2list of row indices corresponding to hashes in hashlist2
newlbslower variable bounds, new bounds will be written here
newubsupper variable bounds, new bound will be written here

Definition at line 1150 of file presol_tworowbnd.c.

References applyLPboundTightening(), encodeRowPair(), FALSE, findNextBlock(), MAX, 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 1280 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 1301 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 1317 of file presol_tworowbnd.c.

References SCIP_OKAY, and SCIPpresolGetData().

◆ SCIP_DECL_PRESOLEXEC()