View source for Patent cliff

In [[mathematical optimization]], '''total dual integrality''' is a sufficient condition for the integrality of a polyhedron. Thus, the [[Integer programming|optimization of a linear objective over the integral points]] of such a polyhedron can be done using techniques from [[linear programming]].

A linear system <math>Ax\le b</math>, where <math>A</math> and <math>b</math> are rational, is called totally dual integral (TDI) if for any <math>c \in \mathbb{Z}^n</math> such that there is a feasible, bounded solution to the linear program
:<math>
\begin{align}
&&\max c^\mathrm{T}x \\
&& Ax\le b,
\end{align}
</math>
there is an integer optimal dual solution.<ref name="gilesPullyblank">{{cite journal|last=Giles|first=F.R.|coauthors=W.R. Pulleyblank|title=Total Dual Integrality and Integer Polyhedra|journal=Linear algebra and its applications|year=1979|volume=25|pages=191–196}}</ref><ref name="EdmondsGiles">{{cite journal|last=Edmonds|first=J.|coauthors=R. Giles|title=A min-max relation for submodular functions on graphs|journal=Annals of Discrete Mathematics|year=1977|volume=1|pages=185–204}}</ref> 

Edmonds and Giles<ref name=EdmondsGiles /> showed that if a polyhedron <math>P</math> is the solution set of a TDI system <math>Ax\le b</math>, where <math>b</math> has all integer entries, then every vertex of <math>P</math> 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<ref name=gilesPullyblank /> showed that if <math>P</math> is a polytope whose vertices are all integer valued, then <math>P</math> is the solution set of some TDI system <math>Ax\le b</math>, where <math>b</math> is integer valued.

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

==References==
{{Reflist}}



[[Category:Mathematical optimization]]