Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
4OR
Published in: 4OR 2/2016

08-08-2015 | Invited Survey

Light on the infinite group relaxation II: sufficient conditions for extremality, sequences, and algorithms

Authors: Amitabh Basu, Robert Hildebrand, Matthias Köppe

Published in: 4OR | Issue 2/2016

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

This is the second part of 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, 1972a; Math Program 3:359–389, 1972b). 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.
next article A line search trust-region algorithm with nonmonotone adaptive radius for a system of nonlinear equations

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

inform now
Footnotes
1
The function is available in the Electronic Compendium (Zhou 2014) as gmic.
 
2
See Definition 3.7 (Basu et al. 2015, Part I).
 
3
See the definition in (3.1) (Basu et al. 2015, Part I).
 
4
This is a superadditive pseudo-periodic function in the terminology of Richard et al. (2009).
 
5
See Sect. 3.6 (Basu et al. 2015, Part I).
 
6
The statement of Proposition 6.1 remains true for generalizations of sequential limits; for example, we may consider the convergence of nets of minimal functions.
 
7
The sequence and its limit can be constructed using drlm_gj_2_slope_extreme_limit_to_ nonextreme.
 
8
See, for example, Hunter and Nachtergaele (2001) for an introduction to Sobolev spaces.
 
9
These parameters are collected in the list delta, which is an argument to the function bhk_irrational. The parameters are \(\mathbb Q\)-linearly independent for example when one parameter is rational, e.g., 1/200 , the other irrational, e.g., sqrt(2)/200 . When the irrational number is algebraic (for example, when it is constructed using square roots), the code will construct an appropriate real number field that is a field extension of the rationals. In this field, the computations are done in exact arithmetic.
 
10
Such a sequence and the limit can be constructed using bhk_irrational_extreme_limit_to_ rational_nonextreme.
 
11
This can also be done with a finite left derivative. Note that not all extreme functions have a finite left or right derivative at the origin. That is, there exist extreme functions that are discontinuous on both sides of the origin. See Table 4 for examples.
 
12
The first n terms of such a sequence of \(\epsilon _i\) are generated by e = generate_example_e_ for_psi_n(n= n).
 
13
The construction of \(\psi _n\) is furnished by h = psi_n_in_bccz_counterexample_ construction(e=e), where e is the list [ \(\epsilon _1, \dots , \epsilon _n\) ].
 
14
The function can be created by h = bccz_counterexample(); however, h(x) can be exactly evaluated only on the set \(\bigcup _{i=0}^\infty \hbox {cl}X_i^-\) defined below; for other values, the function will return an approximation.
 
15
In fact, if \(\mu ^- < 1\), then \(\psi \) is actually Lipschitz continuous and thus absolutely continuous and hence almost everywhere differentiable. The convergence then holds even in the sense of the space \(W^{1,1}_{\mathrm {loc}}(\mathbb R)\).
 
16
If h is the function \(\pi \), e.g., after typing h = dg_2_step_mir(), then the algorithm is invoked by typing extremality_test(h, show_plots=True). In the irrational case no proof of finite convergence of the procedure is known.
 
17
Under these hypotheses, \(\pi \) is the continuous interpolation of \(\pi |_{\frac{1}{q}\mathbb Z}\).
 
18
The function is available in the electronic compendium (Zhou 2014) as kzh_2q_example_1.
 
Literature
Aczél J, Dhombres JG (1989) Functional equations in several variables. Encylopedia of mathematics and its applications, vol. 31. Cambridge University Press, Cambridge
Aliprantis C, Border K (2006) Infinite dimensional analysis: a Hitchhiker’s guide, 2nd edn. Springer, Berlin
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, 25–27 June 2007. 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–408CrossRef
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–39CrossRef
Balas E (1975) Facets of the knapsack polytope. Math Program 8(1):146–164CrossRef
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–324CrossRef
Balas E, Ceria S, Cornuéjols G (1996a) Mixed 0–1 programming by lift-and-project in a branch-and-cut framework. Manag Sci 42(9):1229–1246CrossRef
Balas E, Ceria S, Cornuéjols G, Natraj NR (1996b) Gomory cuts revisited. Oper Res Lett 19(1):1–9CrossRef
Basu A, Conforti M, Cornuéjols G, Zambelli G (2010a) Maximal lattice-free convex sets in linear subspaces. Math Oper Res 35:704–720
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
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
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–576CrossRef
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-dimensional case and applications to 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
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, pp 309–325, ISBN 0-89871-552-0
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–154CrossRef
Conforti M, Cornuéjols G, Zambelli G (2011a) Corner polyhedra and intersection cuts. Surv Oper Res Manage Sci 16:105–120
Cornuéjols G (2007) Revival of the Gomory cuts in the 1990s. Ann Oper Res 149(1):63–66CrossRef
Cornuéjols G, Pulleyblank WR (1982) The travelling salesman polytope and \(\{0, 2\}\)-matchings. North-Holland Math Stud 66:27–55CrossRef
Cornuéjols G, Naddef D, Pulleyblank WR (1983) Halin graphs and the travelling salesman problem. Math Program 26(3):287–294CrossRef
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–27CrossRef
Dantzig G, Fulkerson R, Johnson S (1954) Solution of a large-scale traveling-salesman problem. J Oper Res Soc Am 2(4):393–410
Dey SS, Wolsey LA (2010a) Constrained infinite group relaxations of MIPs. SIAM J Optim 20(6):2890–2912
Dey SS, Wolsey LA (2010b) Two row mixed-integer cuts via lifting. Math Program 124:143–174
Gomory RE (1958) Outline of an algorithm for integer solutions to linear programs. Bull Am Math Soc 64:275–278CrossRef
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
Gomory RE (1965) On the relation between integer and noninteger solutions to linear programs. Proc Natl Acad Sci USA 53(2):260CrossRef
Gomory RE (1969) Some polyhedra related to combinatorial problems. Linear Algebra Appl 2(4):451–558CrossRef
Gomory RE (2007) The atoms of integer programming. Ann Oper Res 149(1):99–102CrossRef
Gomory RE, Johnson EL, Evans L (2003) Corner polyhedra and their connection with cutting planes. Math Program 96(2):321–339CrossRef
Grötschel M, Padberg MW (1979a) On the symmetric travelling salesman problem I: inequalities. Math Program 16(1):265–280CrossRef
Grötschel M, Padberg MW (1979b) On the symmetric travelling salesman problem II: lifting theorems and facets. Math Program 16(1):281–302CrossRef
Grötschel M, Padberg MW (1985) Polyhedral theory. In: Lawler EL, Lenstra JK, Kan AHGR, Shmoys DB (eds) The traveling salesman problem. Wiley, Chichester, NY, pp 251–305
Grötschel M, Pulleyblank WR (1986) Clique tree inequalities and the symmetric traveling salesman problem. Math Oper Res 11:537–569CrossRef
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–179CrossRef
Kianfar K, Fathi Y (2009) Generalized mixed integer rounding inequalities: facets for infinite group polyhedra. Math Program 120:313–346CrossRef
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]
Nemhauser GL, Trotter LE Jr (1974) Properties of vertex packing and independence system polyhedra. Math Program 6(1):48–61CrossRef
Padberg MW (1973) On the facial structure of set packing polyhedra. Math Program 5(1):199–215CrossRef
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
Trotter LE Jr (1975) A class of facet producing graphs for vertex packing polyhedra. Discrete Math 12(4):373–388CrossRef
Wolsey LA (1975) Faces for a linear inequality in 0–1 variables. Math Program 8(1):165–178CrossRef
Metadata
Title
Light on the infinite group relaxation II: sufficient conditions for extremality, sequences, and algorithms
Authors
Amitabh Basu
Robert Hildebrand
Matthias Köppe
Publication date
08-08-2015
Publisher
Springer Berlin Heidelberg
Published in
4OR / Issue 2/2016
Print ISSN: 1619-4500
Electronic ISSN: 1614-2411
DOI
https://doi.org/10.1007/s10288-015-0293-8

Other articles of this Issue 2/2016

4OR 2/2016 Go to the issue

Research paper

A line search trust-region algorithm with nonmonotone adaptive radius for a system of nonlinear equations

PhD Thesis

Heuristic and metaheuristic algorithms for the generation of optimal experimental designs

Research paper

Parallel-machine scheduling with release dates and rejection

Research Paper

Hierarchical optimization with double due dates on an unbounded parallel-batching machine to minimize maximum lateness

Research Paper

Pooling heterogeneous products for manufacturing environments

Research paper

Model-hierarchical column generation and heuristic for the routing and wavelength assignment problem

Premium Partners

    Image Credits