Total dual integrality

From Wikipedia, the free encyclopedia
Jump to: navigation, search

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\le 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{align}
&&\max c^\mathrm{T}x \\
&& Ax\le b,
\end{align}

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\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[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\le b, where b is integer valued.

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

References[edit]

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