  # SCIP

Solving Constraint Integer Programs

presol_tworowbnd.h 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.

1. ConvComb with clique-extension Given two constraints

\begin{eqnarray*} A_{i\cdot} x \geq b_i \\ A_{k\cdot} x \geq b_k \\ \ell \leq x \leq u \\ \end{eqnarray*}

this method determines promising values for $$\lambda \in (0,1)$$ and applies feasibility-based bound tightening to the convex combinations

$$(\lambda A_{i\cdot} + (1 - \lambda) A_{k\cdot}) x \geq \lambda b_i + (1 - \lambda) b_k$$.

Additionally, cliques drawn from the SCIPcliqueTable are used to further strengthen the above bound tightening. Full details can be found in

• Belotti P. "Bound reduction using pairs of linear inequalities"
• Chen W. et. al "Two-row and two-column mixed-integer presolve using hashing-based pairing methods"

Definition in file presol_tworowbnd.h.

#include "scip/def.h"
#include "scip/type_retcode.h"
#include "scip/type_scip.h"

Go to the source code of this file.

## Functions

SCIP_EXPORT SCIP_RETCODE SCIPincludePresolTworowbnd (SCIP *scip)