1 Answers
In mathematical optimization, total dual integrality is a sufficient condition for the integrality of a polyhedron. Thus, the optimization of a linear objective over the integral points of such a polyhedron can be done using techniques from linear programming.
A linear system A x ≤ b {\displaystyle Ax\leq b} , where A {\displaystyle A} and b {\displaystyle b} are rational, is called totally dual integral if for any c ∈ Z n {\displaystyle c\in \mathbb {Z} ^{n}} such that there is a feasible, bounded solution to the linear program
there is an integer optimal dual solution.
Edmonds and Giles showed that if a polyhedron P {\displaystyle P} is the solution set of a TDI system A x ≤ b {\displaystyle Ax\leq b} , where b {\displaystyle b} has all integer entries, then every vertex of P {\displaystyle P} is integer-valued. Thus, if a linear program as above is solved by the simplex algorithm, the optimal solution returned will be integer. Further, Giles and Pulleyblank showed that if P {\displaystyle P} is a polytope whose vertices are all integer valued, then P {\displaystyle P} is the solution set of some TDI system A x ≤ b {\displaystyle Ax\leq b} , where b {\displaystyle b} is integer valued.