Skip to main content
SpringerLink
Log in

Light on the infinite group relaxation I: foundations and taxonomy

  • Invited Survey
  • Published:
4OR Aims and scope Submit manuscript

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\) 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.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6
Fig. 7
Fig. 8

Similar content being viewed by others

Notes

  1. This notation for functions of finite support is used, for example, in Aliprantis and Border (2006).

  2. This model is called the mixed-integer infinite relaxation, for example in the survey (Conforti et al. 2011a), or sometimes the mixed-integer group problem, but we shall not use either of these terms in the remainder of our survey.

  3. This model is called the continuous infinite relaxation, for example in the survey (Conforti et al. 2011a), or sometimes the continuous group problem.

  4. Indeed, \(y \in R_{\mathbf{f}}(G,S)\) gives an element \(\bar{y} \in R_{\bar{\mathbf{f}}}(G/S,0)\) by setting \(\bar{y}(C) = \sum _{{\mathbf{r}}\in C} y({\mathbf{r}})\) for every coset \(C \in G/S\). In the other direction, given \(\bar{y} \in R_{\bar{\mathbf{f}}}(G/S,0)\) we get a solution \(y \in R_{\mathbf{f}}(G,S)\) by simply picking a canonical representative \({\mathbf{r}}_C\) for each coset \(C \in G/S\) and setting \(y({\mathbf{r}}_C) = \bar{y}(C)\). From aggregation of variables it follows that the strongest valid inequalities for the convex hull of \(R_{\mathbf{f}}(G,S)\) will have identical coefficients on any coset; see Theorem 2.6.

  5. In a proof by contradiction, they say that if \(\pi \) is not a facet, then there exists a valid function \(\pi ^*\) and a \(y^* \in R_{\mathbf{f}}(G,S)\) such that \(y^* \in P(\pi ^*){\setminus } P(\pi )\). This works when \(\pi \) is not a weak facet, but does not work if we assume that \(\pi \) is not a facet.

  6. See Sect. 3.1 for the definition that we use.

  7. When \(\pi \) is a discontinuous piecewise linear function, subadditivity gives certain relations on the limit values of the function. We omit this more subtle discussion in this survey; see Basu et al. (2014a) for more details.

  8. See Sect. 3.1 for the definition that we use.

  9. See Sect. 3.1 for the definition that we use, which includes certain discontinuous functions.

  10. This condition is also not always true for piecewise linear functions. See Table 4 for examples of extreme functions that are discontinuous on both sides of the origin. The condition of one-sided continuity at the origin cannot be removed from the hypothesis of Lemma 2.11 (v) (New result \(\clubsuit \)). This is illustrated by example zhou_two_sided_discontinuous_cannot_assume_any_continuity, constructed by Zhou (2014, unpublished).

  11. Gomory and Johnson’s (2003) original proof actually holds only for weak facets, and not for facets as claimed in.

  12. In contrast to Gomory–Johnson’s Facet Theorem, the condition that \(E(\pi ) \subseteq E(\pi ')\) implies \(\pi ' = \pi \) only needs to be tested on minimal valid functions, not all valid functions.

  13. Sometimes certain continuity arguments need to be made, where results like Lemma 2.11(iii), (iv) and (v) are helpful. In such situations, the proof of extremality is usually slightly simpler than a proof for facetness, owing to Lemma 2.11(iii); see Remark 5.5 and Remark 6.4.

  14. The program (Hong et al. 2014) can be run on a local installation of Sage, or online via SageMathCloud. The help system provides a discussion of parameters of the extreme functions, bibliographic information, etc. It is accessed by typing the function name as shown in the table, followed by a question mark. Example: gmic?

  15. See Sect. 3.1 for the definition that we use, which includes certain discontinuous functions.

  16. See Theorem 5.1 for a general k-row result.

  17. The functions are available in the electronic compendium (Zhou 2014) as hildebrand_5_slope...

  18. Note that in Gomory and Johnson (2003), the word “minimal” needs to be replaced by “satisfies the symmetry condition” throughout the statement of their theorem and its proof.

  19. They present it in a setting of pseudo-periodic superadditive functions, rather than periodic subadditive functions.

  20. A discontinuous version of Theorem 3.11 appears in Basu et al. (2014a, Theorem 2.5), where it is stated for the case \(k=1\); it extends verbatim to general k. All relevant limits of the function at discontinuities are taken care of by testing

    figure b

    for all faces \(F\in {\varDelta }\mathcal {P}\) that contain the vertex (u, v). For \(k=1\), by analyzing the possible faces F, one recovers the explicit limit relations stated in Richard et al. (2009, Theorem 22).

  21. A different approach is taken in Dey and Richard (2008, Proposition 10) where the subadditivity test uses so-called supplemental vertices which are introduced to get around the problem of unbounded cells.

  22. This is not restrictive due to Theorem 3.10(ii) and Proposition 3.8(1).

  23. Instead of \({\varDelta }D = [0,1]^k \times [0,1]^k\), one can choose \({\varDelta }D = D \times D\) for any D such that \( D + \mathbb Z^k = \mathbb R^k\); see the discussion in Basu et al. (2014b).

  24. For \(k=1\), necessarily \({\mathbf{f}}\in {{\mathrm{vert}}}(\mathcal {P})\) (Basu et al. 2014a, Lemma 2.4). The same is true for genuinely k-dimensional functions (Theorem 3.10). If, however, \({\mathbf{f}}\notin {{\mathrm{vert}}}(\mathcal {P})\), then the condition (3.5) in the symmetry test must be replaced by a slightly more complicated condition (as stated in Basu et al. 2014b, Theorem 3.10, Remark 3.11). Let \(S = \{\,({\mathbf{u}},{\mathbf{v}})\mid {\mathbf{u}}+ {\mathbf{v}}\equiv {\mathbf{f}}\textstyle \pmod {\mathbf{1}}\,\}\). Then \({\varDelta }\mathcal {P}\cap S := \{\, F\cap S: F \in {\varDelta }\mathcal {P}\, \}\) is again a polyhedral complex. The condition (3.5) is then replaced by:

    $$\begin{aligned} {\varDelta }\pi ({\mathbf{u}},{\mathbf{v}}) = 0 \quad \text {for all}\quad ({\mathbf{u}},{\mathbf{v}})\in {\varDelta }D \cap {{\mathrm{vert}}}({\varDelta }\mathcal {P}\cap S). \end{aligned}$$

References

  • Aczél J, Dhombres JG (1989) Functional equations in several variables, vol 31. Cambridge University Press, Cambridge

    Book  Google Scholar 

  • Aliprantis C, Border K (2006) Infinite dimensional analysis: a Hitchhiker’s guide, 2nd edn. Springer, Berlin

    Google Scholar 

  • Andersen K, Louveaux Q, Weismantel R, Wolsey L (2007) Inequalities from two rows of a simplex tableau. In: Fischetti M, Williamson D (eds) Integer programming and combinatorial optimization. Proceedings of the 12th international IPCO conference, Ithaca, NY, USA, June 25–27. Lecture notes in computer science, vol 4513, Springer, Berlin, Heidelberg, pp 1–15. doi:10.1007/978-3-540-72792-7_1

  • Aráoz J, Evans L, Gomory RE, Johnson EL (2003) Cyclic group and knapsack facets. Math Program Ser B 96:377–408

    Article  Google Scholar 

  • Averkov G, Basu A (2014) On the unique-lifting property. In: Lee J, Vygen J (eds) Integer programming and combinatorial optimization. Lecture notes in computer science, vol 8494, pp 76–87. Springer. doi:10.1007/978-3-319-07557-0_7

  • Balas E (1971) Intersection cuts—a new type of cutting planes for integer programming. Oper Res 19:19–39

    Article  Google Scholar 

  • Balas E (1975) Facets of the knapsack polytope. Math Program 8(1):146–164

    Article  Google Scholar 

  • Balas E, Ceria S, Cornuéjols G (1993) A lift-and-project cutting plane algorithm for mixed 0–1 programs. Math Program 58(1–3):295–324

    Article  Google Scholar 

  • Balas E, Ceria S, Cornuéjols G (1996a) Mixed 0–1 programming by lift-and-project in a branch-and-cut framework. Manage Sci 42(9):1229–1246

    Article  Google Scholar 

  • Balas E, Ceria S, Cornuéjols G, Natraj NR (1996b) Gomory cuts revisited. Oper Res Lett 19(1):1–9

  • Balas E, Jeroslow RG (1980) Strengthening cuts for mixed integer programs. Eur J Oper Res 4(4):224–234. doi:10.1016/0377-2217(80)90106-X

    Article  Google Scholar 

  • Basu A, Conforti M, Cornuéjols G, Zambelli G (2010a) Maximal lattice-free convex sets in linear subspaces. Math Oper Res 35:704–720

    Article  Google Scholar 

  • Basu A, Conforti M, Cornuéjols G, Zambelli G (2010b) Minimal inequalities for an infinite relaxation of integer programs. SIAM J Discrete Math 24:158–168. doi:10.1137/090756375

    Article  Google Scholar 

  • Basu A, Cornuéjols G, Köppe M (2012a) Unique minimal liftings for simplicial polytopes. Math Oper Res 37(2):346–355. doi:10.1287/moor.1110.0536

    Article  Google Scholar 

  • Basu A, Conforti M, Cornuéjols G, Zambelli G (2012b) A counterexample to a conjecture of Gomory and Johnson. Math Program Ser A 133(1–2):25–38. doi:10.1007/s10107-010-0407-1

    Article  Google Scholar 

  • Basu A, Hildebrand R, Köppe M (2013a) Equivariant perturbation in Gomory and Johnson’s infinite group problem. II. The unimodular two-dimensional case. In: Goemans M, Correa J (eds) Integer programming and combinatorial optimization. Lecture notes in computer science, vol 7801. Springer, pp 62–73. doi:10.1007/978-3-642-36694-9_6

  • Basu A, Hildebrand R, Köppe M, Molinaro M (2013b) A \((k+1)\)-slope theorem for the \(k\)-dimensional infinite group relaxation. SIAM J Optim 23(2):1021–1040. doi:10.1137/110848608

    Article  Google Scholar 

  • Basu A, Campêlo M, Conforti M, Cornuéjols G, Zambelli G (2013c) Unique lifting of integer variables in minimal inequalities. Math Program 141(1–2):561–576

    Article  Google Scholar 

  • Basu A, Hildebrand R, Köppe M (2014a) Equivariant perturbation in Gomory and Johnson’s infinite group problem. I. The one-dimensional case. Math Oper Res 40(1):105–129. doi:10.1287/moor.2014.0660

  • Basu A, Hildebrand R, Köppe M (2014b) Equivariant perturbation in Gomory and Johnson’s infinite group problem. III. Foundations for the \(k\) = 2. arXiv:1403.4628 [math.OC]

  • Basu A, Hildebrand R, Köppe M (2014c) Equivariant perturbation in Gomory and Johnson’s infinite group problem. IV. The general unimodular two-dimensional case

  • Basu A, Hildebrand R, Köppe M (2015) Light on the infinite group relaxation II: sufficient conditions for extremality, sequences, and algorithms. 4OR-Q J Oper Res. doi:10.1007/s10288-015-0293-8

  • Bixby RE, Fenelon M, Gu Z, Rothberg E, Wunderling R (2004) Mixed integer programming: a progress report. In: Grötschel M (ed) The sharpest cut, MPS-SIAM series on optimization, Philadelphia, PA, pp 309–325, ISBN 0-89871-552-0

  • Borozan V, Cornuéjols G (2009) Minimal valid inequalities for integer constraints. Math Oper Res 34:538–546. doi:10.1287/moor.1080.0370

    Article  Google Scholar 

  • Chen K (2011) Topics in group methods for integer programming. Ph.D. thesis, Georgia Institute of Technology

  • Chvátal V (1975) On certain polytopes associated with graphs. J Comb Theory Ser B 18(2):138–154

    Article  Google Scholar 

  • Conforti M, Cornuéjols G, Zambelli G (2011a) Corner polyhedra and intersection cuts. Surv Oper Res Manage Sci 16:105–120

    Google Scholar 

  • Conforti M, Cornuéjols G, Zambelli G (2011b) A geometric perspective on lifting. Oper Res 59(3):569–577. doi:10.1287/opre.1110.0916

    Article  Google Scholar 

  • Conforti M, Cornuéjols G, Daniilidis A, Lemaréchal C, Malick J (2013) Cut-generating functions and S-free sets. Math Oper Res 40(2):253–275. doi:10.1287/moor.2014.0670

    Google Scholar 

  • Cornuéjols G, Naddef D, Pulleyblank WR (1983) Halin graphs and the travelling salesman problem. Math Program 26(3):287–294

    Article  Google Scholar 

  • Cornuéjols G, Fonlupt J, Naddef D (1985) The traveling salesman problem on a graph and some related integer polyhedra. Math Program 33(1):1–27

    Article  Google Scholar 

  • Cornuéjols G (2007) Revival of the Gomory cuts in the 1990s. Ann Oper Res 149(1):63–66

    Article  Google Scholar 

  • Cornuéjols G, Pulleyblank WR (1982) The travelling salesman polytope and \(\{0, 2\}\)-matchings. North-Holland Mathematics Studies 66:27–55

    Article  Google Scholar 

  • Cornuéjols G, Molinaro M (2013) A 3-slope theorem for the infinite relaxation in the plane. Math Program 142(1–2):83–105. doi:10.1007/s10107-012-0562-7

    Article  Google Scholar 

  • Dantzig G, Fulkerson R, Johnson S (1954) Solution of a large-scale traveling-salesman problem. J Oper Res Soc Am 2(4):393–410

    Google Scholar 

  • Dash S, Günlük O (2006) Valid inequalities based on simple mixed-integer sets. Mathe Program 105:29–53. doi:10.1007/s10107-005-0599-y

    Article  Google Scholar 

  • Dey SS, Richard J-PP, Li Y, Miller LA (2010) On the extreme inequalities of infinite group problems. Math Program 121(1):145–170. doi:10.1007/s10107-008-0229-6

    Article  Google Scholar 

  • Dey SS, Richard J-PP (2008) Facets of two-dimensional infinite group problems. Math Oper Res 33(1):140–166. doi:10.1287/moor.1070.0283

    Article  Google Scholar 

  • Dey SS, Richard J-PP (2010) Relations between facets of low- and high-dimensional group problems. Math Program 123(2):285–313. doi:10.1007/s10107-009-0303-8

    Article  Google Scholar 

  • Dey SS, Wolsey LA (2010a) Constrained infinite group relaxations of MIPs. SIAM J Optim 20(6):2890–2912

    Article  Google Scholar 

  • Dey SS, Wolsey LA (2010b) Two row mixed-integer cuts via lifting. Math Program 124:143–174

    Article  Google Scholar 

  • Gomory RE (1958) Outline of an algorithm for integer solutions to linear programs. Bull Am Math Soc 64:275–278

    Article  Google Scholar 

  • Gomory RE (1960) An algorithm for the mixed integer problem. Technical report RM-2597-PR, The RAND Corporation, Santa Monica, CA

  • Gomory RE (1963) An algorithm for integer solutions to linear programs. Recent Adv Math Program 64:260–302

    Google Scholar 

  • Gomory RE (1965) On the relation between integer and noninteger solutions to linear programs. Proc Nat Acad Sci USA 53(2):260

    Article  Google Scholar 

  • Gomory RE (1969) Some polyhedra related to combinatorial problems. Linear Algebra Appl 2(4):451–558

    Article  Google Scholar 

  • Gomory RE, Johnson EL, Evans L (2003) Corner polyhedra and their connection with cutting planes. Math Program 96(2):321–339

    Article  Google Scholar 

  • Gomory RE (2007) The atoms of integer programming. Ann Oper Res 149(1):99–102

    Article  Google Scholar 

  • Gomory RE, Johnson EL (1972a) Some continuous functions related to corner polyhedra, I. Math Program 3:23–85. doi:10.1007/BF01584976

    Article  Google Scholar 

  • Gomory RE, Johnson EL (1972b) Some continuous functions related to corner polyhedra, II. Math Program 3:359–389. doi:10.1007/BF01585008

    Article  Google Scholar 

  • Gomory RE, Johnson EL (2003) T-space and cutting planes. Math Program 96:341–375. doi:10.1007/s10107-003-0389-3

    Article  Google Scholar 

  • Grötschel M, Padberg MW (1979a) On the symmetric travelling salesman problem I: inequalities. Math Program 16(1):265–280

    Article  Google Scholar 

  • Grötschel M, Padberg MW (1979b) On the symmetric travelling salesman problem II: lifting theorems and facets. Math Program 16(1):281–302

    Article  Google Scholar 

  • Grötschel M, Padberg MW (1985) Polyhedral theory. In: Lawler EL, Lenstra JK, H A, Kan GR, Shmoys DB (eds) The traveling salesman problem. Wiley, Chichester, NY, pp 251–305

    Google Scholar 

  • Grötschel M, Pulleyblank WR (1986) Clique tree inequalities and the symmetric traveling salesman problem. Math Oper Res 11:537–569

    Article  Google Scholar 

  • Grötschel M, Nemhauser GL (2008) George Dantzig’s contributions to integer programming. Discrete Optim 5(2):168–173, In Memory of George B. Dantzig. doi:10.1016/j.disopt.2007.08.003

  • Hong CY, Köppe M, Zhou Y (2014) Sage program for computation and experimentation with the 1-dimensional Gomory–Johnson infinite group problem. https://github.com/mkoeppe/infinite-group-relaxation-code

  • Hunter JK, Nachtergaele B (2001) Applied analysis. World Scientific, ISBN 978-9-812-70543-3

  • Johnson EL (1974) On the group problem for mixed integer programming. Math Program Study 2:137–179

    Article  Google Scholar 

  • Kianfar K, Fathi Y (2009) Generalized mixed integer rounding inequalities: facets for infinite group polyhedra. Math Program 120:313–346

    Article  Google Scholar 

  • Köppe M, Zhou Y (2015a) An electronic compendium of extreme functions for the Gomory–Johnson infinite group problem. Oper Res Lett 43(4):438–444. doi:10.1016/j.orl.2015.06.004

  • Köppe M, Zhou Y (2015b) New computer-based search strategies for extreme functions of the Gomory–Johnson infinite group problem. arXiv:1506.00017 [math.OC]

  • Letchford AN, Lodi A (2002) Strengthening Chvátal-Gomory cuts and Gomory fractional cuts. Oper Res Lett 30(2):74–82. doi:10.1016/S0167-6377(02)00112-8

    Article  Google Scholar 

  • Nemhauser GL, Trotter LE Jr (1974) Properties of vertex packing and independence system polyhedra. Math Program 6(1):48–61

    Article  Google Scholar 

  • Padberg MW (1973) On the facial structure of set packing polyhedra. Math Program 5(1):199–215

    Article  Google Scholar 

  • Richard J-PP, Dey SS (2010) The group-theoretic approach in mixed integer programming. In: Jünger, M, Liebling TM, Naddef D, Nemhauser GL, Pulleyblank WR, Reinelt G, Rinaldi G, Wolsey LA, (eds) 50 years of integer programming 1958–2008. Springer, Berlin, Heidelberg (2010), pp 727–801. doi:10.1007/978-3-540-68279-0_19, ISBN 978-3-540-68274-5

  • Richard J-PP, Li Y, Miller LA (2009) Valid inequalities for MIPs and group polyhedra from approximate liftings. Math Program 118(2):253–277. doi:10.1007/s10107-007-0190-9

    Article  Google Scholar 

  • Stein WA et al (2015) Sage Mathematics Software (Version 6.6). The Sage Development Team. http://www.sagemath.org

  • Trotter LE Jr (1975) A class of facet producing graphs for vertex packing polyhedra. Discrete Math 12(4):373–388

    Article  Google Scholar 

  • Wolsey LA (1975) Faces for a linear inequality in 0–1 variables. Math Program 8(1):165–178

    Article  Google Scholar 

  • Zhou Y (2014) Electronic compendium of extreme functions for the 1-row Gomory–Johnson infinite group problem. https://github.com/mkoeppe/infinite-group-relaxation-code/

Download references

Acknowledgments

Thanks go to Yuan Zhou for compiling the electronic compendium of extreme functions in Zhou (2014), and Chun Yu Hong and Yuan Zhou for their work on the software (Hong et al. 2014).

Author information

Authors and Affiliations

  1. Department of Applied Mathematics and Statistics, The Johns Hopkins University, Baltimore, MD, 21218, USA

    Amitabh Basu

  2. Department of Mathematics, Institute for Operations Research, ETH Zürich, Zurich, Switzerland

    Robert Hildebrand

  3. Department of Mathematics, University of California, Davis, Davis, CA, 95616, USA

    Matthias Köppe

Authors
  1. Amitabh Basu
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Robert Hildebrand
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Matthias Köppe
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Matthias Köppe.

Additional information

The authors gratefully acknowledge partial support from the National Science Foundation through Grants DMS-0914873 (R. Hildebrand, M. Köppe) and DMS-1320051 (M. Köppe).

Appendices

Appendix 1: Updated compendium of extreme functions

Tables 1, 2, 3, 4, 5 and 6 contain the updated compendium of extreme functions.

Table 1 An updated compendium of known extreme functions for the infinite group problem I: Parametrized classes of continuous functions for the 1-dimensional case with up to two slopes
Full size table
Table 2 An updated compendium of known extreme functions for the infinite group problem II: Parametrized classes of continuous functions for the 1-dimensional case with at least three slopes
Full size table
Table 3 An updated compendium of known extreme functions for the infinite group problem III: Parametrized families of discontinuous functions for the 1-dimensional case
Full size table
Table 4 An updated compendium of known extreme functions for the infinite group problem IV: “Sporadic” functions for the 1-dimensional case. These functions were found by computer experiments. They have not been described in the literature as a member of a parametrized family; but there is no reason to assume this could not be done
Full size table
Table 5 An updated compendium of known extreme functions for the infinite group problem V. Procedures
Full size table
Table 6 List of notation in the infinite group problem literature
Full size table

Appendix 2: List of notation in the literature

Table 6 compares the notation in the present survey with that in selected original articles on the infinite group problem and the surveys (Richard and Dey 2010; Conforti et al. 2011a).

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Basu, A., Hildebrand, R. & Köppe, M. Light on the infinite group relaxation I: foundations and taxonomy. 4OR-Q J Oper Res 14, 1–40 (2016). https://doi.org/10.1007/s10288-015-0292-9

Download citation

  • Received:

  • Revised:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10288-015-0292-9

Keywords

Mathematics Subject Classification

Search

Navigation