TOPICS
Search

Total Dual Integrality

Total dual integrality is a property of a rational system of linear inequalities Ax<=b. The system is totally dual integral if, for every integer objective vector c for which max{c^Tx:Ax<=b} is finite, the dual problem

min{b^Ty:A^Ty=c, y>=0}

has an integer optimal solution (Barbato and Lancini 2026). The property belongs to the defining system, not just its solution polyhedron.

Box-total dual integrality strengthens this property by requiring it to survive the addition of arbitrary rational coordinate bounds l<=x<=u.

See also

Box-Total Dual Integrality, Integer Programming, Linear Programming, Stable Marriage Polytope

Explore with Wolfram|Alpha

References

Barbato, M. and Lancini, E. "The Stable Marriage Polytope Is Box-Totally Dual Integral." 8 Oct 2026. https://arxiv.org/abs/2610.12720.

Cite this as:

Weisstein, Eric W. "Total Dual Integrality." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/TotalDualIntegrality.html

Subject classifications