A Horizon Tour of Box-Total Dual Integrality

A linear system is totally dual integral (TDI) if, for every linear program with integer cost vector defined on it, the dual problem admits an integer optimum whenever it is feasible. A linear system is box-totally dual integral (box-TDI) if it remains TDI under the addition of arbitrary rational bounds on its variables. First introduced by Edmonds and Giles in the late 1970s, box-TDIness is a central property in combinatorial optimization, with deep connections to polyhedral integrality, min–max duality, and integer programming. This article provides a self-contained survey of both classical and recent results concerning box-TDI systems and polyhedra. We also discuss complexity aspects and examples from combinatorial optimization where box-TDIness arises naturally. Particular attention is paid to unifying different lines of development in the literature and clarifying the structural properties that underlie the theory. Throughout the paper, we highlight open questions and conjectures, offering a perspective on ongoing and future directions of research.