# 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.

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 "blockmemshell/memory.h"
#include "scip/presol_tworowbnd.h"
#include "scip/pub_matrix.h"
#include "scip/pub_message.h"
#include "scip/pub_misc_sort.h"
#include "scip/pub_presol.h"
#include "scip/pub_var.h"
#include "scip/scip_general.h"
#include "scip/scip_mem.h"
#include "scip/scip_nlp.h"
#include "scip/scip_numerics.h"
#include "scip/scip_presol.h"
#include "scip/scip_pricer.h"
#include "scip/scip_prob.h"
#include "scip/scip_probing.h"
#include "scip/scip_var.h"
#include <string.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)

## ◆ PRESOL_NAME

 #define PRESOL_NAME   "tworowbnd"

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

Referenced by SCIPincludePresolTworowbnd().

## ◆ PRESOL_PRIORITY

 #define PRESOL_PRIORITY   -500000

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

Definition at line 62 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 63 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 64 of file presol_tworowbnd.c.

Referenced by SCIPincludePresolTworowbnd().

## ◆ SUPPORT_THRESHOLD

 #define SUPPORT_THRESHOLD   0.5

threshold for two constraints overlap

Definition at line 66 of file presol_tworowbnd.c.

Referenced by calcTwoRowBnds().

## ◆ FASTMODE_THRESHOLD

 #define FASTMODE_THRESHOLD   1000

max number of baserows for switching to fast mode

Definition at line 67 of file presol_tworowbnd.c.

Referenced by calcTwoRowBnds().

## ◆ BNDCHGTYPE

 typedef enum Bndchgtype BNDCHGTYPE

Definition at line 79 of file presol_tworowbnd.c.

## ◆ Bndchgtype

 enum Bndchgtype

type of bound change

Enumerator
LOWERBOUND
UPPERBOUND
BOTHBOUNDS

Definition at line 73 of file presol_tworowbnd.c.

## ◆ getActivities()

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

Referenced by applyTightening().

## ◆ getMinActivity()

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

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

Referenced by applyTightening().

## ◆ getMaxActivity()

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

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

Referenced by applyTightening().

## ◆ getMaxResActivity()

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

References SCIP_Real, and SCIPisInfinity().

Referenced by applyTightening().

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

Referenced by calcTwoRowBnds().

## ◆ getCoefficients()

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

Referenced by calcTwoRowBnds().

## ◆ getNumOverlap()

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

References SCIPmatrixGetRowIdxPtr(), and SCIPmatrixGetRowNNonzs().

Referenced by calcTwoRowBnds().

## ◆ getOverlapBaseOrdered()

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

References SCIPmatrixGetRowIdxPtr(), and SCIPmatrixGetRowNNonzs().

Referenced by calcTwoRowBnds().

## ◆ 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

Definition at line 1174 of file presol_tworowbnd.c.

Referenced by SCIP_DECL_PRESOLEXEC().

## ◆ getBaseRows()

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

determine base rows

Parameters
 scip SCIP main data structure matrix constraint matrix nbaserows number of present base rows baserows indexes of base rows

Definition at line 1345 of file presol_tworowbnd.c.

References NULL, r, SCIP_OKAY, SCIPmatrixGetNRows(), and SCIPmatrixIsRowRhsInfinity().

Referenced by SCIP_DECL_PRESOLEXEC().

## ◆ getBounds()

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

get bounds of variables

Parameters
 scip SCIP main data structure matrix constraint matrix lowerbds lower bounds upperbds upper bounds

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

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

## ◆ SCIP_DECL_PRESOLEXEC()

 static SCIP_DECL_PRESOLEXEC ( presolExecTworowbnd )
static

execution method of presolver

Definition at line 1426 of file presol_tworowbnd.c.