Total dual integrality

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

This notion was introduced by Edmonds and Giles , who proved the following fundamental property of TDI systems.

Theorem. If the system $$Ax \leq b$$ is TDI and the vector b is integer, then $$\{x: Ax \leq b\}$$ is an integer polyhedron.

Another definition can be given using the notion of Hilbert basis. A system $$Ax \leq b$$ is TDI if and only if for every face F of the polyhedron $$P=\{x: Ax \leq b\}$$ , 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 :

Theorem. If P is a rational polyhedron, then it has a TDI linear description $$Ax \leq b$$ 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).