One of the central elements of (Mixed-) Integer Linear Programming is the polyhedral approach. The feasible set of a Linear Program is a polyhedron, where a vertex (if there is one) is optimal for any linear objective function where an optimal solution exists. In the case of MILPs, however, the integrality constraint on some variables breaks down the feasible set S into disjoint polyhedra. Nevertheless, the first reasonable attempt at solving any MILP consists of replacing S with the linear relaxation P defined by the linear constraints of the formulation alone. Then we can run the “wish-me-luck” algorithm:
The wish-me-luck algorithm:
1. Ignore the integrality constraints and solve the MILP as an LP.
2. If the integrality constraints are satisfied, we are done!
3. Otherwise, we are (temporarily) doomed!
Sometimes the gamble is guaranteed. If we can find a polyhedron Q corresponding to the convex hull of the feasible set S, i.e. Q = conv(S), then we can solve the MILP as if it were an LP by optimizing over Q because all vertices belong to S. We say that an MILP formulation is perfect if P and Q coincide, like in network flow problems with integer coefficients. In the vast amount of cases where that does not happen, the quest illustrated in Schrijver’s book cover begins: we want to start from a good P (in white) and hopefully find an optimal solution by getting closer to Q (in red).
For a good P, we may compare different formulations for their strength. For example, by showing that the linear relaxation of one formulation is a proper subset of another, even if the variables are different. We can show that by proving that a function maps each solution of the linear relaxation of one formulation to that of another whereas the converse is not true. To strengthen this formulation towards something like Q, at least around the optimal solution, we may add cutting planes. A cutting plane is an inequality that removes a region of the linear relaxation not in S, which is often around an optimal solution of the linear relaxation, in the hope that “wish-me-luck” works next time!
We take for granted that the convex hull is polyhedral, but is it? The following result is adapted from the recent book by Conforti, Cornuéjols, and Zambelli:
The Fundamental Theorem of Integer Programming (Meyer, 1974):
Given rational matrices A, G and a rational vector b, let P := { (x, y) : Ax + Gy ≤ b } and let S := { (x, y) ∈ P : x integral }. Then there exist rational matrices A’, G’ and a rational vector b’ such that conv(S) = { (x, y) : A’ x + G’ y ≤ b’ }.
The fact that the coefficients of the formulation should be rational is often overlooked. In practice, since these problems are solved with finite precision, this becomes irrelevant. However, the convex hull of some MILPs is not polyhedral. The following example is adapted from an exercise in the book above and includes “pi” as a special guest.
If P := { (x, y) : 0 ≤ y ≤ π x } and S := { (x, y) ∈ P : x, y integral },
then conv(S) = { (0, 0) } ∪ { (x, y) : 0 ≤ y < π x }, which is not polyhedral.
The proof for this example is quite simple (in comparison to the example in CCZ’s book). First, no point besides (0, 0) in the line y = π x belongs to S, and by consequence to conv(S). Suppose for contradiction that such a point (x’, y’) exits. Then y’ / x’ is a rational representation of π, a contradiction. Second, any other point (x, y) for which 0 ≤ y < π x belongs to conv(S). Since x > 0, there is a rational number p / q such that y / x < p / q < π and thus (x, y) is inside a cone rooted at (0, 0) with rays (1, 0) and (p, q).
Hence, when it comes to integer programming, you should better be rational…
Thiago Serra 