Total dual integrality of linear inequality systems. (English) Zbl 0555.90078

Progress in combinatorial optimization, Conf. Waterloo/Ont. 1982, 117-129 (1984).
[For the entire collection see Zbl 0535.00030.]
Let A be a rational \(m\times n\) matrix and b be a rational m-vector. The linear system Ax\(\leq b\) is said to be totally dual integral (TDI) if for all integer n-vectors c, the dual of the linear program max\(\{\) cx: Ax\(\leq b\}\) has an integer-valued optimum solution if it has an optimum solution. We consider two topics: First we discuss the theoretical aspects of total dual integrality. Second, we survey several classes of TDI linear systems and show how the general properties of total dual integrality apply to each class.


90C10 Integer programming
52Bxx Polytopes and polyhedra


Zbl 0535.00030