Total dual integrality
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 , where and are rational, is called totally dual integral (TDI) if for any such that there is a feasible, bounded solution to the linear program
Edmonds and Giles showed that if a polyhedron is the solution set of a TDI system , where has all integer entries, then every vertex of 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 is a polytope whose vertices are all integer valued, then is the solution set of some TDI system , where is integer valued.
- Giles, F.R.; W.R. Pulleyblank (1979). "Total Dual Integrality and Integer Polyhedra". Linear Algebra and its Applications. 25: 191–196.
- Edmonds, J.; R. Giles (1977). "A min-max relation for submodular functions on graphs". Annals of Discrete Mathematics. 1: 185–204.
- Schrijver, A. (1981). "On Total Dual Integrality". Linear Algebra and its Applications. 38: 27–32. doi:10.1016/0024-3795(81)90005-7.
- Chekuri, C. "Combinatorial Optimization Lecture Notes" (PDF).