presol_tworowbnd.h File Reference

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.

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_RETCODE	SCIPincludePresolTworowbnd (SCIP *scip)