linguistic:voice_change, linguistic:paraphrasing, information:filtering, stylistic:tone
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, i.e., made of only integer values. Likewise, a polyhedron P = { x ∣ A x ≥ 0 } {\displaystyle P=\{x\mid Ax\geq 0\}} is said to be integral if for all bounded feasible objective functions c, the linear program { max c x ∣ x ∈ P } {\displaystyle \{\max cx\mid x\in P\}} has an optimum x ∗ {\displaystyle x^{*}} with integer coordinates. As observed by Edmonds and Giles in 1977, one can equivalently say that the polyhedron P {\displaystyle P} is integral if for every bounded feasible integral objective function c, the optimal value of the linear program { max c x ∣ x ∈ P } {\displaystyle \{\max cx\mid x\in P\}} 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.

Terminology is not consistent throughout the literature, so one should be careful to distinguish the following two concepts,

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 two generalized polymatroids/ g -polymatroids – e.g. see Schrijver 2003.