# 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

there is an integer optimal dual solution.^{[1]}^{[2]}

Edmonds and Giles^{[2]} 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^{[1]} 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.

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

## References

- ↑
^{1.0}^{1.1}{{#invoke:Citation/CS1|citation |CitationClass=journal }} - ↑
^{2.0}^{2.1}{{#invoke:Citation/CS1|citation |CitationClass=journal }} - ↑ Template:Cite web