# SCIP

Solving Constraint Integer Programs

presol_tworowbnd.c File Reference

## Detailed Description

do bound tightening by using two rows

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.

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)

## ◆ PRESOL_NAME

 #define PRESOL_NAME   "tworowbnd"

Definition at line 73 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 74 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 75 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 76 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 77 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 79 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 80 of file presol_tworowbnd.c.

Referenced by SCIPincludePresolTworowbnd().

## ◆ DEFAULT_MAXRETRIEVEFAILS

 #define DEFAULT_MAXRETRIEVEFAILS   1000

maximal number of consecutive useless hashtable retrieves

Definition at line 81 of file presol_tworowbnd.c.

Referenced by SCIPincludePresolTworowbnd().

## ◆ DEFAULT_MAXCOMBINEFAILS

 #define DEFAULT_MAXCOMBINEFAILS   1000

maximal number of consecutive useless row combines

Definition at line 82 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 83 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 84 of file presol_tworowbnd.c.

Referenced by SCIPincludePresolTworowbnd().

## ◆ ROWPAIR

 typedef struct RowPair ROWPAIR

Definition at line 110 of file presol_tworowbnd.c.

## ◆ 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().

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

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.

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.

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

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

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

## ◆ SCIP_DECL_PRESOLFREE()

 static SCIP_DECL_PRESOLFREE ( presolFreeTworowbnd )
static

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

Definition at line 1310 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 1326 of file presol_tworowbnd.c.

References SCIP_OKAY, and SCIPpresolGetData().

## ◆ SCIP_DECL_PRESOLEXEC()

 static SCIP_DECL_PRESOLEXEC ( presolExecTworowbnd )
static