Changes
Let <math>A \in {\mathbb Q}^{m\times n}</math> be a rational matrix, and let <math>b \in {\mathbb Q}^m</math>. The linear inequality system <math>Ax \leq b</math> is '''totally dual integral''' (TDI for short) if for every integer vector <math>c \in {\mathbb Z}^n</math> the system <math>\max\{yb: yA=c,\ y \geq 0\}</math> has an integer optimal solution provided that the optimum is finite.
This notion was introduced by Edmonds and Giles <ref>J. Edmonds, R. Giles, ''A min-max relation for submodular functions on graphs'', in: Studies in Integer Programming (Proceedings of the Workshop on Integer Programming, Bonn, 1975; P.L. Hammer, E.L. Johnson, B.H. Korte, G.L. Nemhauser, eds.), 1977, 185–204. [http://books.google.com/books?id=PMyXs5SMa2MC&lpg=PA185&ots=Wc6WdXnS4L&lr=&pg=PA185#v=onepage&q=&fname=false Google Books link].<"EdGi"/ref>, who proved the following fundamental property of TDI systems.
'''Theorem.''' If the system <math>Ax \leq b</math> is TDI and the vector ''b'' is integer, then <math>\{x: Ax \leq b\}</math> is an integer polyhedron.
Another definition can be given using the notion of [[wikipedia:Hilbert basis (linear programming)|Hilbert basis]]. A system <math>Ax \leq b</math> is TDI if and only if for every face ''F'' of the polyhedron <math>P=\{x: Ax \leq b\}</math>, 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 <ref name="GiPu"/>:
'''Theorem.''' If ''P'' is a rational polyhedron, then it has a TDI linear description <math>Ax \leq b</math> 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 [[Wikipedia:Unimodular_matrix#Total_unimodularity|TU matrix]],
* Intersection of two [[generalized polymatroid]]s,
* Submodular flows (see the [[Edmonds-Giles theorem]]),
* Edmonds' description of the matching polytope (see [[Edmonds' matching polytope theorem]]).
==References==
<references> <ref name="EdGi">J. Edmonds, R. Giles, ''A min-max relation for submodular functions on graphs'', in: Studies in Integer Programming (Proceedings of the Workshop on Integer Programming, Bonn, 1975; P.L. Hammer, E.L. Johnson, B.H. Korte, G.L. Nemhauser, eds.), 1977, 185–204. [http://dx.doi.org/10.1016/S0167-5060(08)70734-9 DOI link], [http://books.google.com/books?id=PMyXs5SMa2MC&lpg=PA185&ots=Wc6WdXnS4L&lr=&pg=PA185#v=onepage&q=&f=false Google Books link].</ref> <ref name="GiPu">F.R. Giles, W.R. Pulleyblank, ''Total dual integrality and integer polyhedra'', [http://dx.doi.org/10.1016/0024-3795(79)90018-1 DOI link]</ref> </references>
[[Category:Definitions]]
