Cutting planes and integer hulls

For a polyhedron $P$, its integer hull is $P_I=\operatorname{conv}(P\cap\mathbb Z^n)$. Linear optimization over the integer points and over this hull has the same supremum whenever the integer set is nonempty, because a linear objective on a convex combination is a convex combination of the constituent values. For rational polyhedra the integer hull is itself a rational polyhedron. This structural fact does not promise a small description: a useful formulation can require many inequalities, so explicitly listing the entire hull may be computationally unrealistic.

An inequality is valid if it holds at every integer-feasible point under consideration. It separates a candidate only if that candidate violates it. Both properties are required for an effective cut at the current LP solution. An inequality already implied by the relaxation is valid but cannot remove a feasible LP point. An arbitrary inequality that removes the candidate may be invalid because it excludes desirable integer points too. Separation algorithms search a specified family of valid inequalities; failure to find a violated member of that family does not prove the candidate belongs to the full integer hull.

Suppose $P=\{x:Ax\le b\}$ and all coordinates of the intended solution are integers. Choose nonnegative multipliers $\lambda$ such that $\lambda^TA$ is an integer row. Combining the constraints gives $\lambda^TAx\le\lambda^Tb$. Its left side is integer for every intended point, so it also satisfies $\lambda^TAx\le\lfloor\lambda^Tb\rfloor$. This is a Chvátal–Gomory cut. The floor step is justified by the integrality of the combined left side, not by an instruction to round every coefficient or every inequality independently.

If some variables are continuous, an integer-looking coefficient row generally does not make the left side integer. Mixed-integer cut formulas therefore require different arguments that account for continuous terms. Likewise, a nonnegative combination is essential when adding inequalities in this direction; a negative multiplier could reverse an inequality. Rational scaling can help obtain integral combined coefficients, but multiplying an inequality by an arbitrary number and flooring its bound without checking the new left side is unsafe. A derivation should display the multipliers and explicitly name the integer quantity that permits rounding.

For a binary knapsack $\sum_i a_ix_i\le B$ with nonnegative weights, a cover is an index set $C$ whose weights sum to more than $B$. All its items cannot be selected simultaneously, giving $\sum_{i\in C}x_i\le|C|-1$. This proof uses both the overweight condition and binary variables. Minimal covers can be strengthened by lifting additional variables, but any lifted coefficient needs its own validity argument. Cover cuts expose combinatorial exclusions absent from the original average resource inequality and often improve a node relaxation before further branching.

A globally valid cut preserves every integer-feasible point of the original model; a locally valid cut may rely on branch-specific restrictions and can only be used where those restrictions hold. Keeping that scope is essential when sharing cuts between nodes. For rational pure-integer polyhedra, repeated Chvátal–Gomory closure reaches the integer hull after finitely many rounds, but that theorem neither says one cut suffices nor grants a small worst-case algorithm. Arbitrary choices of valid cuts need not reproduce the full closure or inherit a finite-step guarantee. Branch-and-cut combines validated cuts with exhaustive branching, retaining the bound and coverage logic of the previous lesson.