Total dual integrality explained

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

Ax\le b , where A and b are rational, is called totally dual integral (TDI) if for any c \in Z ^{n} such that there is a feasible, bounded solution to the linear program\begin{align} && max c ^{Tx} \\ && Ax\le b, \end{align} there is an integer optimal dual solution.^{[1] [2] [3]}

Edmonds and Giles showed that if a polyhedron

P is the solution set of a TDI system Ax\le b , where b has all integer entries, then every vertex of 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 is a polytope whose vertices are all integer valued, then P is the solution set of some TDI system Ax\le b , where b is integer valued.

Note that TDI is a weaker sufficient condition for integrality than total unimodularity.^[4]

Notes and References

1. Giles. F.R.. W.R. Pulleyblank. William R. Pulleyblank . Total Dual Integrality and Integer Polyhedra. Linear Algebra and its Applications. 1979. 25. 191–196. 10.1016/0024-3795(79)90018-1. free.
2. Edmonds. J.. Jack Edmonds. R. Giles . A min-max relation for submodular functions on graphs. Annals of Discrete Mathematics. 1977. 1. 185–204.
3. Schrijver. A.. On Total Dual Integrality. Linear Algebra and its Applications. 1981. 38. 27–32. 10.1016/0024-3795(81)90005-7. free.
4. Web site: Chekuri. C.. Combinatorial Optimization Lecture Notes.