Table of Contents
Presolve techniques analyze the problem before starting the branch-and-bound search to simplify it and reduce the search space. For instance, it may tighten variable bounds, remove redundancies, or strengthen constraints. Presolve can significantly speed up the solution process.
Typically, a presolve operation is added using the .with_presolver method. For instance, here is how to add the OneRowBoundStrengthening presolver detailed bellow.
For more details, please refer to Achterberg et al. (2019).
Bound Rounding
This presolve simply rounds down or up the variable bounds associated to integer or binary variables. This is typically used in combination with other presolvers that may affect variable bounds.
Here is how to add it.
One Row Bound Strengthening
One-row bound strengthening tightens variable bounds by analyzing each constraint individually. Consider a linear inequality
\[ A_{iS} x_S + a_{ik} x_k \le b_i, \]
where \( S = \text{supp}(A_i\cdot) \setminus \{k\} \) and \( a_{ik} \neq 0 \). First, a lower bound on the sum of the other variables is computed
\[ \ell_{iS} = \inf \{ A_{iS} x_S \}. \]
Then, depending on the sign of \(a_{ik}\), the bound of \(x_k\) is updated as follows:
If \(a_{ik} > 0\), update the upper bound:
\[ u_k := \min \Big\{ u_k, \frac{b_i - \ell_{iS}}{a_{ik}} \Big\}. \]
If \(a_{ik} < 0\), update the lower bound:
\[ \ell_k := \max \Big\{ \ell_k, \frac{b_i - \ell_{iS}}{a_{ik}} \Big\}. \]
This procedure is applied iteratively across all constraints, with safeguards to prevent infinite sequences of tiny reductions. More specifically,
- a change is ignored if the improvement is smaller than \(10^3 \cdot \varepsilon\), where \(\varepsilon\) is the feasibility tolerance,
- bounds with absolute values exceeding \(10^8\) are also ignored.
Only one round per constraint is applied per presolve pass.
Note that this presolver does not round the bounds for integer variables. Please, use this in combination with the BoundRounding presolver for better performance.
Generated by
1.16.1