A Horizon Tour of Box-Total Dual Integrality

Emiliano Lancini () and Francesco Pisanu ()
Additional contact information
Emiliano Lancini: Université Paris Dauphine
Francesco Pisanu: Université catholique de Louvain, LIDAM/CORE, Belgium

No 2024031, LIDAM Discussion Papers CORE from Université catholique de Louvain, Center for Operations Research and Econometrics (CORE)

Abstract: 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.

Pages: 44
Date: 2024-12-17
References: Add references at CitEc
Citations:

Downloads: (external link)
https://dial.uclouvain.be/pr/boreal/en/object/bore ... tastream/PDF_01/view (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:cor:louvco:2024031

Access Statistics for this paper

More papers in LIDAM Discussion Papers CORE from Université catholique de Louvain, Center for Operations Research and Econometrics (CORE) Voie du Roman Pays 34, 1348 Louvain-la-Neuve (Belgium). Contact information at EDIRC.
Bibliographic data for series maintained by Alain GILLIS ().