Integral Linear Programs
A linear program in real variables is said to be integral if it has at least one optimal solution which is integral. Likewise, a polyhedron is said to be integral if for all bounded feasible objective functions c, the linear program has an optimum with integer coordinates. As observed by Edmonds and Giles in 1977, one can equivalently say that a polyhedron is integral if for every bounded feasible integral objective function c, the optimal value of the linear program is an integer.
Integral linear programs are of central importance in the polyhedral aspect of combinatorial optimization since they provide an alternate characterization of a problem. Specifically, for any problem, the convex hull of the solutions is an integral polyhedron; if this polyhedron has a nice/compact description, then we can efficiently find the optimal feasible solution under any linear objective. Conversely, if we can prove that a linear programming relaxation is integral, then it is the desired description of the convex hull of feasible (integral) solutions.
Note that terminology is not consistent throughout the literature, so one should be careful to distinguish the following two concepts,
- in an integer linear program, described in the previous section, variables are forcibly constrained to be integers, and this problem is NP-hard in general,
- in an integral linear program, described in this section, variables are not constrained to be integers but rather one has proven somehow that the continuous problem always has an integral optimal value (assuming c is integral), and this optimal value may be found efficiently since all polynomial-size linear programs can be solved in polynomial time.
One common way of proving that a polyhedron is integral is to show that it is totally unimodular. There are other general methods including the integer decomposition property and total dual integrality. Other specific well-known integral LPs include the matching polytope, lattice polyhedra, submodular flow polyhedra, and the intersection of 2 generalized polymatroids/g-polymatroids --- e.g. see Schrijver 2003.
A bounded integral polyhedron is sometimes called a convex lattice polytope, particularly in two dimensions.
Read more about this topic: Linear Programming
Famous quotes containing the words integral and/or programs:
“Painting myself for others, I have painted my inward self with colors clearer than my original ones. I have no more made my book than my book has made me—a book consubstantial with its author, concerned with my own self, an integral part of my life; not concerned with some third-hand, extraneous purpose, like all other books.”
—Michel de Montaigne (1533–1592)
“[The Republicans] offer ... a detailed agenda for national renewal.... [On] reducing illegitimacy ... the state will use ... funds for programs to reduce out-of-wedlock pregnancies, to promote adoption, to establish and operate children’s group homes, to establish and operate residential group homes for unwed mothers, or for any purpose the state deems appropriate. None of the taxpayer funds may be used for abortion services or abortion counseling.”
—Newt Gingrich (b. 1943)