Better Know A Theorem: Polyhedral Union

Lausanne

This week I have been at EPFL, Lausanne, Switzerland. It has been a good opportunity to practice my French; there is not as much English spoken here as in the more touristic parts of the country. Nonetheless this is a good place to come if you are a tourist: it is nearby the beautiful lake Geneva, home to lots of awesome castles and old buildings, and good food and wine is plentiful. For some reason a main dish I see on a lot of menus is cold roast beef with tartar sauce, usually $25 (Swiss francs ~ Canadian dollars) — as of yet I don’t understand this.

In news that is not directly related, I was recently reading papers on a technique called disjunctive programming going back to the 1970s. The main tool can be interpreted as a very cute result having to do with the fundamentals of LPs that I will depict below. It has to do with taking the convex union of two polyhedra. It’s very simple but seems relatively unknown (or at least, I have seen it buried deep in papers but never in courses where it would fit well).

Polyhedron P1

A linear program in two dimensions can be thought of as a polygon (dots connected by straight lines), pictured as “P1” at the left. There are several “linear constraints” which are all of the format

“2.1 * x + 1.8 * y ≥ 6.7”

and this particular constraint is the line pictured with the vector (arrowhead)

Polyhedron P2

coming out of it. This constraint says that only points to the right of that line are feasible for this constraint; P1 here has 4 other constraints corresponding to its four other sides, and the feasible region is the pentagon. At the right is a second polyhedron which I will call P2, which is similarly defined by four linear constraints.

Intersection of P1 and P2

Now can we get a collection of constraints which expresses the intersection of these two polyhedra? In this case it is easy: simply take all the constraints of P1, and throw in all the constraints of P2, then the feasible region of the resulting system is exactly the intersection of P1 and P2. The intersection polyhedron is pictured in black on the left-hand side. (In this example, there are 9 constraints, but the intersection polyhedron has only 7 sides, since two of the these constraints become redundant.)

Convex Hull of Union of P1 and P2

Whenever you do something with an intersection in mathematics, it is natural to ask if you can do the same thing with a union. That is to say, can we get a linear program to express the set of all points which lie in either P1 or P2 or both? Immediately we can see there is a problem with this, since linear programs can only express convex regions, and the union may not be convex. But it turns out there is an easy way to express the convex hull of the union of P1 and P2, i.e. the smallest convex set containing both P1 and P2 (pictured on the right-hand side).

To fully explain, we will need some symbols. Let z be a vector containing all the variables of the linear program, suppose P1 is represented by the linear system A₁z ≥ b₁ and P2 is represented by the linear system A₂z ≥ b₂. Essentially by definition, the convex hull of the two convex shapes P1 and P2 is equal to

The problem is that this program in variables is not linear, e.g. since we are multiplying with . But the slightly tricky & nice part is that if you rescale the variables, you get the following linear formulation for the same set:

Good times with linear programs! This type of method leads to something called “lift-and-project” in the literature which amounts to automatically strengthening a linear program in such a way that is becomes “closer” to having no fractional vertices.