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

{\begin{aligned}&&\max c^{{\mathrm {T}}}x\\&&Ax\leq b,\end{aligned}}

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

Edmonds and Giles^[2] showed that if a polyhedron $P$ is the solution set of a TDI system $Ax\leq 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^[1] showed that if $P$ is a polytope whose vertices are all integer valued, then $P$ is the solution set of some TDI system $Ax\leq b$ , where $b$ is integer valued.

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

References

1 2 Giles, F.R.; W.R. Pulleyblank (1979). "Total Dual Integrality and Integer Polyhedra". Linear algebra and its applications. 25: 191–196.
1 2 Edmonds, J.; R. Giles (1977). "A min-max relation for submodular functions on graphs". Annals of Discrete Mathematics. 1: 185–204.
↑ Chekuri, C. "Combinatorial Optimization Lecture Notes" (PDF).

This article is issued from Wikipedia - version of the 8/18/2015. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.