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.
- 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.
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.
Go to the source code of this file.
Functions | |
| SCIP_RETCODE | SCIPincludePresolTworowbnd (SCIP *scip) |