IDEAS home Printed from https://ideas.repec.org/a/spr/aqjoor/v14y2016i1d10.1007_s10288-015-0292-9.html
   My bibliography  Save this article

Light on the infinite group relaxation I: foundations and taxonomy

Author

Listed:
  • Amitabh Basu

    (The Johns Hopkins University)

  • Robert Hildebrand

    (Institute for Operations Research, ETH Zürich)

  • Matthias Köppe

    (University of California, Davis)

Abstract

This is a survey on the infinite group problem, an infinite-dimensional relaxation of integer linear optimization problems introduced by Ralph Gomory and Ellis Johnson in their groundbreaking papers titled Some continuous functions related to corner polyhedra I, II (Math Program 3:23–85, 359–389, 1972a, b). The survey presents the infinite group problem in the modern context of cut generating functions. It focuses on the recent developments, such as algorithms for testing extremality and breakthroughs for the k-row problem for general $$k\ge 1$$ k ≥ 1 that extend previous work on the single-row and two-row problems. The survey also includes some previously unpublished results; among other things, it unveils piecewise linear extreme functions with more than four different slopes. An interactive companion program, implemented in the open-source computer algebra package Sage, provides an updated compendium of known extreme functions.

Suggested Citation

  • Amitabh Basu & Robert Hildebrand & Matthias Köppe, 2016. "Light on the infinite group relaxation I: foundations and taxonomy," 4OR, Springer, vol. 14(1), pages 1-40, March.
    • Handle: RePEc:spr:aqjoor:v:14:y:2016:i:1:d:10.1007_s10288-015-0292-9
    DOI: 10.1007/s10288-015-0292-9
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s10288-015-0292-9
    File Function: Abstract
    Download Restriction: Access to the full text of the articles in this series is restricted.
    File URL: https://libkey.io/10.1007/s10288-015-0292-9?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Balas, Egon & Jeroslow, Robert G., 1980. "Strengthening cuts for mixed integer programs," European Journal of Operational Research, Elsevier, vol. 4(4), pages 224-234, April.
    2. Egon Balas, 1971. "Intersection Cuts—A New Type of Cutting Planes for Integer Programming," Operations Research, INFORMS, vol. 19(1), pages 19-39, February.
    3. M. Grötschel & W. R. Pulleyblank, 1986. "Clique Tree Inequalities and the Symmetric Travelling Salesman Problem," Mathematics of Operations Research, INFORMS, vol. 11(4), pages 537-569, November.
    4. G. Dantzig & R. Fulkerson & S. Johnson, 1954. "Solution of a Large-Scale Traveling-Salesman Problem," Operations Research, INFORMS, vol. 2(4), pages 393-410, November.
    5. Ralph Gomory, 2007. "The atoms of integer programming," Annals of Operations Research, Springer, vol. 149(1), pages 99-102, February.
    6. Santanu S. Dey & Jean-Philippe P. Richard, 2008. "Facets of Two-Dimensional Infinite Group Problems," Mathematics of Operations Research, INFORMS, vol. 33(1), pages 140-166, February.
    7. WOLSEY, Laurence A., 1975. "Faces for a linear inequality in 0-1 variables," LIDAM Reprints CORE 218, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    8. Valentin Borozan & Gérard Cornuéjols, 2009. "Minimal Valid Inequalities for Integer Constraints," Mathematics of Operations Research, INFORMS, vol. 34(3), pages 538-546, August.
    9. Egon Balas & Sebastián Ceria & Gérard Cornuéjols, 1996. "Mixed 0-1 Programming by Lift-and-Project in a Branch-and-Cut Framework," Management Science, INFORMS, vol. 42(9), pages 1229-1246, September.
    10. Charalambos D. Aliprantis & Kim C. Border, 2006. "Infinite Dimensional Analysis," Springer Books, Springer, edition 0, number 978-3-540-29587-7, June.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Amitabh Basu & Michele Conforti & Marco Di Summa & Giacomo Zambelli, 2019. "Optimal Cutting Planes from the Group Relaxations," Management Science, INFORMS, vol. 44(4), pages 1208-1220, November.
    2. Amitabh Basu & Michele Conforti & Marco Di Summa & Joseph Paat, 2019. "The Structure of the Infinite Models in Integer ProgrammingAbstract: The infinite models in integer programming can be described as the convex hull of some points or as the intersection of halfspaces ," Management Science, INFORMS, vol. 44(4), pages 1412-1430, November.

    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. Amitabh Basu & Robert Hildebrand & Matthias Köppe, 2016. "Light on the infinite group relaxation II: sufficient conditions for extremality, sequences, and algorithms," 4OR, Springer, vol. 14(2), pages 107-131, June.
    2. Santanu S. Dey & Andrea Lodi & Andrea Tramontani & Laurence A. Wolsey, 2014. "On the Practical Strength of Two-Row Tableau Cuts," INFORMS Journal on Computing, INFORMS, vol. 26(2), pages 222-237, May.
    3. Egon Balas, 2005. "Projection, Lifting and Extended Formulation in Integer and Combinatorial Optimization," Annals of Operations Research, Springer, vol. 140(1), pages 125-161, November.
    4. Kent Andersen & Gérard Cornuéjols & Yanjun Li, 2005. "Reduce-and-Split Cuts: Improving the Performance of Mixed-Integer Gomory Cuts," Management Science, INFORMS, vol. 51(11), pages 1720-1732, November.
    5. Egon Balas & Thiago Serra, 2020. "When Lift-and-Project Cuts Are Different," INFORMS Journal on Computing, INFORMS, vol. 32(3), pages 822-834, July.
    6. 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.
    7. Amitabh Basu & Robert Hildebrand & Matthias Köppe, 2015. "Equivariant Perturbation in Gomory and Johnson's Infinite Group Problem. I. The One-Dimensional Case," Mathematics of Operations Research, INFORMS, vol. 40(1), pages 105-129, February.
    8. Amitabh Basu & Gérard Cornuéjols & François Margot, 2012. "Intersection Cuts with Infinite Split Rank," Mathematics of Operations Research, INFORMS, vol. 37(1), pages 21-40, February.
    9. Anja Fischer & Frank Fischer, 2015. "An extended approach for lifting clique tree inequalities," Journal of Combinatorial Optimization, Springer, vol. 30(3), pages 489-519, October.
    10. Egon Balas & Gérard Cornuéjols & Tamás Kis & Giacomo Nannicini, 2013. "Combining Lift-and-Project and Reduce-and-Split," INFORMS Journal on Computing, INFORMS, vol. 25(3), pages 475-487, August.
    11. Amitabh Basu & Pierre Bonami & Gérard Cornuéjols & François Margot, 2011. "Experiments with Two-Row Cuts from Degenerate Tableaux," INFORMS Journal on Computing, INFORMS, vol. 23(4), pages 578-590, November.
    12. Michele Conforti & Gérard Cornuéjols & Giacomo Zambelli, 2011. "A Geometric Perspective on Lifting," Operations Research, INFORMS, vol. 59(3), pages 569-577, June.
    13. Gennadiy Averkov & Christian Wagner & Robert Weismantel, 2011. "Maximal Lattice-Free Polyhedra: Finiteness and an Explicit Description in Dimension Three," Mathematics of Operations Research, INFORMS, vol. 36(4), pages 721-742, November.
    14. 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).
    15. Valentin Borozan & Gérard Cornuéjols, 2009. "Minimal Valid Inequalities for Integer Constraints," Mathematics of Operations Research, INFORMS, vol. 34(3), pages 538-546, August.
    16. Santanu S. Dey & Quentin Louveaux, 2011. "Split Rank of Triangle and Quadrilateral Inequalities," Mathematics of Operations Research, INFORMS, vol. 36(3), pages 432-461, August.
    17. Jonathan Eckstein & Mikhail Nediak, 2005. "Depth-Optimized Convexity Cuts," Annals of Operations Research, Springer, vol. 139(1), pages 95-129, October.
    18. Karthekeyan Chandrasekaran & László A. Végh & Santosh S. Vempala, 2016. "The Cutting Plane Method is Polynomial for Perfect Matchings," Mathematics of Operations Research, INFORMS, vol. 41(1), pages 23-48, February.
    19. Jamal Ouenniche & Prasanna K. Ramaswamy & Michel Gendreau, 2017. "A dual local search framework for combinatorial optimization problems with TSP application," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 68(11), pages 1377-1398, November.
    20. Aardal, K.I. & van Hoesel, S., 1995. "Polyhedral Techniques in Combinatorial Optimization," Discussion Paper 1995-57, Tilburg University, Center for Economic Research.

    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:spr:aqjoor:v:14:y:2016:i:1:d:10.1007_s10288-015-0292-9. 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: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.springer.com .

    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.