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 [math]\displaystyle{ Ax\le b }[/math], where [math]\displaystyle{ A }[/math] and [math]\displaystyle{ b }[/math] are rational, is called totally dual integral (TDI) if for any [math]\displaystyle{ c \in \mathbb{Z}^n }[/math] such that there is a feasible, bounded solution to the linear program

[math]\displaystyle{ \begin{align} &&\max c^\mathrm{T}x \\ && Ax\le b, \end{align} }[/math]

there is an integer optimal dual solution.

Edmonds and Giles showed that if a polyhedron [math]\displaystyle{ P }[/math] is the solution set of a TDI system [math]\displaystyle{ Ax\le b }[/math], where [math]\displaystyle{ b }[/math] has all integer entries, then every vertex of [math]\displaystyle{ P }[/math] 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 [math]\displaystyle{ P }[/math] is a polytope whose vertices are all integer valued, then [math]\displaystyle{ P }[/math] is the solution set of some TDI system [math]\displaystyle{ Ax\le b }[/math], where [math]\displaystyle{ b }[/math] is integer valued.

Note that TDI is a weaker sufficient condition for integrality than total unimodularity.