It has been recognized recently that to represent a polyhedron as the projection of a higher-dimensional, but simpler, polyhedron is a powerful tool in polyhedral combinatorics. We develop a general method to construct higher-dimensional polyhedra (or, in some cases, convex sets) whose projection approximates the convex hull of 0-1 valued solutions of a system of linear inequalities. An important feature of these approximations is that one can optimize any linear objective function over them in polynomial time.
展开▼
