Integral Convex Polyhedra and an Approach to Integralization

Abstract

Many combinatorial optimization problems may be formulated as integer linear programming problems - that is, problems of the form: given a convex polyhedron P contained in the non-negative orthant of n-dimensional space, find a integer point in P which maximizes (or minimizes) a given linear objective function. Well known linear programming methods would suffice to solve such a problem if: (i) P is an integral convex polyhedron, or (ii) P is transformed into the integral convex polyhedron that is the convex hull of the set of integer points in P, a process which is called integralization.