Handbook of Automated Reasoning

3.3 Cutting planes

Consider the integer linear optimization or integer linear programming problem

$\max \{c^{T}x|Ax\le b,x\in {\mathbb{Z}}^n\},A\in {\mathbb{Z}}^{m\times n},b\in {\mathbb{Z}}^m.$

   (3.12)

An important consequence of Theorem (3.3) is that for a rational polyhedron $P=\{x\in {\mathbb{F}}^n|Ax\le b\}$ , the convex hull of the set of integer points S = P ∩ ⁿ in P is again a rational polyhedron. Therefore, in principle, the integer linear optimization ...