TOPICS
Search

Box-Total Dual Integrality


Box-total dual integrality, abbreviated box-TDI, is the property that a rational system of linear inequalities Ax<=b retains total dual integrality after adding arbitrary rational coordinate bounds l<=x<=u. Any lower or upper bound may be omitted (Barbato and Lancini 2026). The word "box" refers to these coordinatewise restrictions.

For every integer objective vector whose maximum over the augmented system is finite, the corresponding dual problem must have an integer optimal solution. The bounds themselves need not be integers. A rational polyhedron is box-totally dual integral if it admits a box-TDI defining system (Barbato and Lancini 2026).

Barbato and Lancini (2026) proved that the stable marriage polytope is box-totally dual integral, and that Rothblum's defining system has this property.


See also

Linear Programming, Polyhedron, Total Dual Integrality

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. "Box-Total Dual Integrality." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/Box-TotalDualIntegrality.html

Subject classifications