Minimal inequality

From Glossary

Jump to: navigation, search

In integer programming, a valid inequality is minimal if it not dominated by any valid inequality. Originally, this was limited to not being able to decrease any coefficient and remain valid. For example, suppose LaTeX: 2x_1 + x_2 \ge 1 is a valid inequality. Then, if we decrease the first coefficient to obtain LaTeX: x_1 + x_2 = 1, either this is not valid or it dominates the former, rendering it non-minimal.

More generally, suppose LaTeX: a^Tx \ge b is a valid inequality, and we consider LaTeX: (a',b') such that LaTeX: a' \le t a and LaTeX: b' \ge t b for some positive LaTeX: t such that LaTeX: (a',b') \neq t (a,b). If LaTeX: (a')^T x \ge b' is a valid inequality, it dominates the original one because

\{ x \in \mathbb{R}^n : x \ge 0, \, (a')^T x \ge b \} \subseteq \{ x \in \mathbb{R}^n : x \ge 0, \, a^T x \ge 0 \}.

For example, LaTeX: 4x_1 + 2x_2 \ge 3 dominates LaTeX: 2x_1 + x_2 \ge 1 (use LaTeX: t = 2), so if this is valid, LaTeX: 2x_1 + x_2 \ge 1 cannot be minimal. Every facet-defining inequality is minimal, but not conversely.

Personal tools