# Total dual integrality

Let [math]A \in {\mathbb Q}^{m\times n}[/math] be a rational matrix, and let [math]b \in {\mathbb Q}^m[/math]. The linear inequality system [math]Ax \leq b[/math] is **totally dual integral** (TDI for short) if for every integer vector [math]c \in {\mathbb Z}^n[/math] the system [math]\max\{yb: yA=c,\ y \geq 0\}[/math] has an integer optimal solution provided that the optimum is finite.

This notion was introduced by Edmonds and Giles ^{[1]}, who proved the following fundamental property of TDI systems.

**Theorem.** If the system [math]Ax \leq b[/math] is TDI and the vector *b* is integer, then [math]\{x: Ax \leq b\}[/math] is an integer polyhedron.

Another definition can be given using the notion of Hilbert basis. A system [math]Ax \leq b[/math] is TDI if and only if for every face *F* of the polyhedron [math]P=\{x: Ax \leq b\}[/math], the rows of *A* that correspond to tight inequalities for *F* form a Hilbert basis. This characterization can be used to prove the following theorem of Giles and Pulleyblank ^{[2]}:

**Theorem.** If *P* is a rational polyhedron, then it has a TDI linear description [math]Ax \leq b[/math] such that the matrix *A* is integral. If *P* is an integer polyhedron, then *b* can also be integral.

## Examples

The following are some examples of TDI systems:

- Any linear system given by a TU matrix,
- Intersection of two generalized polymatroids,
- Submodular flows (see the Edmonds-Giles theorem),
- Edmonds' description of the matching polytope (see Edmonds' matching polytope theorem).

## References

- ↑ J. Edmonds, R. Giles,
*A min-max relation for submodular functions on graphs*, in: Studies in Integer Programming (Proceedings of the Workshop on Integer Programming, Bonn, 1975; P.L. Hammer, E.L. Johnson, B.H. Korte, G.L. Nemhauser, eds.), 1977, 185–204. DOI link, Google Books link. - ↑ F.R. Giles, W.R. Pulleyblank,
*Total dual integrality and integer polyhedra*, DOI link