Long-delayed Posts II: Cutting Planes

This is a vast topic dealing with the following question: you are given a convex polytope P in R^n (say, as the intersection of some halfspaces), and you only care about the integer points inside P (i.e., S = P intersect Z^n). How do you come up with some halfspace h such that S lies in h, but some portion of P lies outside the halfspace (and hence is "cut off")?

Ideally you want to find a set H of halfspaces so that P'(P,H) = P intersect (intersection of halfspaces in H) equals convex-hull(S) --- note that this P' is the smallest convex body that can contain all of S.

As a simple illustration, if you have the following inequalities

3x + 4y <= 17 2x + 6y <= 22 x, y >= 0

Graphing this, we get:

Adding the first two inequalities gives us

5x + 10y <= 39

or

x + 2y <= 7.80

But since we only care about integer values of x,y, we can round down the RHS, and get the following "valid" inequality:

x+2y <= 7.

Similarly, the fact that x>=0 along with the second inequality implies that 6y <= 22, and using the same rounding-down idea, we get another "valid" inequality:

y <= 3.

And similarly (using the first inequality, and y >= 0), one gets

x <= 5.

Note that each of these cuts off some portion of the original polytope; though we are still left with a fractional vertex (5, 0.5). (How should we cut this fractional vertex off?)

Note that we used some simple rules-of-thumb to generate these inequalities that were valid for all integer points S inside P, but cut off some portions of the polytope. One can ask: are there automated procedures to generate such valid inequalities in a systematic fashion? Are these procedures to generate these cutting planes "complete" --- do they eventually give leave us with the convex hull of S? How much time do these procedures take?

You can refer to entire books on the subject (e.g., Schrijver's book on Linear and Integer Programming). There has been much interest in some of these advanced techniques: the Lovasz-Schrijver method, the Sherali-Adams method, and the Lassere method. We may blog about this sometime later, but before we end, let us see how the simple idea about rounding down the right hand side is applicable to the matching polytope.

The Matching Polytope

One can use same ideas as above to get the Edmonds' matching polyope formulation from the naive matching constraints: start with

x(delta v) <= 1 for all v
x_e >= 0

now take a set A of vertices, and add up the constraint x(delta v) <= 1 for v in A. You get

2 \sum_{e subsetof A} x_e + \sum_{e in delta A} x_e <= |A|.

Now since the x_e's are non-negative, drop the second summation to get

\sum_{e subsetof A} x_e <= |A|/2.

But since all integer solutions give an integer value on the left, you can replace the right by

\sum_{e subsetof A} x_e <= floor(|A|/2).