IDEAS home Printed from https://ideas.repec.org/p/cor/louvco/2024031.html

A Horizon Tour of Box-Total Dual Integrality

Author

Listed:
  • Lancini, Emiliano

    (Université Paris Dauphine)

  • Pisanu, Francesco

    (Université catholique de Louvain, LIDAM/CORE, Belgium)

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.

Suggested Citation

  • Lancini, Emiliano & Pisanu, Francesco, 2024. "A Horizon Tour of Box-Total Dual Integrality," LIDAM Discussion Papers CORE 2024031, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    • Handle: RePEc:cor:louvco:2024031
    as

    Download full text from publisher

    File URL: https://dial.uclouvain.be/pr/boreal/en/object/boreal%3A295204/datastream/PDF_01/view
    Download Restriction: no
    ---><---

    References listed on IDEAS

    as
    1. Guoli Ding & Lei Tan & Wenan Zang, 2018. "When Is the Matching Polytope Box-Totally Dual Integral?," Mathematics of Operations Research, INFORMS, vol. 43(1), pages 64-99, February.
    2. EDMONDS, Jack & GILES, Rick, 1977. "A min-max relation for submodular functions on graphs," LIDAM Reprints CORE 301, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    3. Robert Weismantel, 1996. "Hilbert Bases and the Facets of Special Knapsack Polytopes," Mathematics of Operations Research, INFORMS, vol. 21(4), pages 886-904, November.
    4. Xujin Chen & Guoli Ding & Wenan Zang, 2008. "A Characterization of Box-Mengerian Matroid Ports," Mathematics of Operations Research, INFORMS, vol. 33(2), pages 497-512, May.
    5. Robert E. Bixby & William H. Cunningham, 1980. "Converting Linear Programs to Network Problems," Mathematics of Operations Research, INFORMS, vol. 5(3), pages 321-357, August.
    Full references (including those not matched with items on IDEAS)

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Xujin Chen & Zhibin Chen & Wenan Zang, 2010. "A Unified Approach to Box-Mengerian Hypergraphs," Mathematics of Operations Research, INFORMS, vol. 35(3), pages 655-668, August.
    2. András Frank, 2005. "On Kuhn's Hungarian Method—A tribute from Hungary," Naval Research Logistics (NRL), John Wiley & Sons, vol. 52(1), pages 2-5, February.
    3. Xujin Chen & Guoli Ding & Xiaodong Hu & Wenan Zang, 2006. "A Min-Max Relation on Packing Feedback Vertex Sets," Mathematics of Operations Research, INFORMS, vol. 31(4), pages 777-788, November.
    4. Clemens Heuberger, 2004. "Inverse Combinatorial Optimization: A Survey on Problems, Methods, and Results," Journal of Combinatorial Optimization, Springer, vol. 8(3), pages 329-361, September.
    5. Kazuo Murota, 2016. "Discrete convex analysis: A tool for economics and game theory," The Journal of Mechanism and Institution Design, Society for the Promotion of Mechanism and Institution Design, University of York, vol. 1(1), pages 151-273, December.
    6. Alexandre Skoda, 2019. "Convexity of graph-restricted games induced by minimum partitions," Post-Print halshs-01617023, HAL.
    7. Meijia Han & Wenxing Zhu, 2023. "Nonnegative partial s-goodness for the equivalence of a 0-1 linear program to weighted linear programming," Journal of Combinatorial Optimization, Springer, vol. 45(5), pages 1-37, July.
    8. Mao-Cheng Cai & Xiaoguang Yang & Yanjun Li, 1999. "Inverse Polymatroidal Flow Problem," Journal of Combinatorial Optimization, Springer, vol. 3(1), pages 115-126, July.
    9. M. Cai & X. Yang & Y. Li, 2000. "Inverse Problems of Submodular Functions on Digraphs," Journal of Optimization Theory and Applications, Springer, vol. 104(3), pages 559-575, March.
    10. Alexandre Skoda, 2016. "Inheritance of Convexity for Partition Restricted," Documents de travail du Centre d'Economie de la Sorbonne 16040, Université Panthéon-Sorbonne (Paris 1), Centre d'Economie de la Sorbonne.
    11. Ali Aouad & Vivek Farias & Retsef Levi, 2021. "Assortment Optimization Under Consider-Then-Choose Choice Models," Management Science, INFORMS, vol. 67(6), pages 3368-3386, June.
    12. Aardal, K. & van Hoesel, C.P.M., 1995. "Polyhedral techniques in combinatorial optimization," Research Memorandum 014, Maastricht University, Maastricht Research School of Economics of Technology and Organization (METEOR).
    13. Alexandre Skoda, 2017. "Inheritance of Convexity for the P min-Restricted Game," Post-Print halshs-01660670, HAL.
    14. Joseph C. Hartman, 2000. "The parallel replacement problem with demand and capital budgeting constraints," Naval Research Logistics (NRL), John Wiley & Sons, vol. 47(1), pages 40-56, February.
    15. Alexandre Skoda, 2016. "Inheritance of Convexity for Partition Restricted Games," Post-Print halshs-01318105, HAL.
    16. Christopher Hojny & Tristan Gally & Oliver Habeck & Hendrik Lüthen & Frederic Matter & Marc E. Pfetsch & Andreas Schmitt, 2020. "Knapsack polytopes: a survey," Annals of Operations Research, Springer, vol. 292(1), pages 469-517, September.
    17. Alexandre Skoda, 2017. "Inheritance of Convexity for the P min-Restricted Game," Université Paris1 Panthéon-Sorbonne (Post-Print and Working Papers) halshs-01660670, HAL.
    18. Aardal, K.I. & van Hoesel, S., 1995. "Polyhedral Techniques in Combinatorial Optimization," Other publications TiSEM ed028a07-eb6a-4c8d-8f21-d, Tilburg University, School of Economics and Management.
    19. Alexandre Skoda, 2017. "Convexity of Graph-Restricted Games Induced by Minimum Partitions," Post-Print halshs-01659804, HAL.
    20. Alexander Bockmayr & Friedrich Eisenbrand, 2001. "Cutting Planes and the Elementary Closure in Fixed Dimension," Mathematics of Operations Research, INFORMS, vol. 26(2), pages 304-312, May.

    More about this item

    Statistics

    Access and download statistics

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:cor:louvco:2024031. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Alain GILLIS (email available below). General contact details of provider: https://edirc.repec.org/data/coreebe.html .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.