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

:$$

\begin{align}

&&\max c^\mathrm{T}x \\

&& Ax\le b,

\end{align}

there is an integer optimal dual solution.{{cite journal|last=Giles|first=F.R.|author2=W.R. Pulleyblank|author2-link=William R. Pulleyblank |title=Total Dual Integrality and Integer Polyhedra|journal=Linear Algebra and its Applications|year=1979|volume=25|pages=191–196|doi=10.1016/0024-3795(79)90018-1|doi-access=free}}{{cite journal|last=Edmonds|first=J.|author-link=Jack Edmonds|author2=R. Giles |title=A min-max relation for submodular functions on graphs|journal=Annals of Discrete Mathematics|year=1977|volume=1|pages=185–204}}{{cite journal|last=Schrijver|first=A.|title=On Total Dual Integrality|journal=Linear Algebra and its Applications|year=1981|volume=38|pages=27–32|doi=10.1016/0024-3795(81)90005-7|doi-access=free}}

Edmonds and Giles showed that if a polyhedron $P$ is the solution set of a TDI system $Ax\backslash 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\backslash le\; b$, where $b$ is integer valued.

Note that TDI is a weaker sufficient condition for integrality than total unimodularity.{{cite web|last=Chekuri|first=C.|title=Combinatorial Optimization Lecture Notes|url=http://courses.engr.illinois.edu/cs598csc/sp2010/Lectures/Lecture12.pdf}}