Light on the infinite group relaxation I: foundations and taxonomy

详细信息    查看全文

• 作者：Amitabh Basu ; Robert Hildebrand ; Matthias Köppe
• 关键词：Cutting planes ; Cut ; generating functions ; Minimal and extreme functions ; Integer programming ; Infinite group problem
• 刊名：4OR: A Quarterly Journal of Operation Research
• 出版年：2016
• 出版时间：March 2016
• 年：2016
• 卷：14
• 期：1
• 页码：1-40
• 全文大小：2,877 KB
• 参考文献：Aczél J, Dhombres JG (1989) Functional equations in several variables, vol 31. Cambridge University Press, CambridgeCrossRef
  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, 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–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. Manage Sci 42(9):1229–1246CrossRef
  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 CrossRef
  Basu A, Conforti M, Cornuéjols G, Zambelli G (2010a) Maximal lattice-free convex sets in linear subspaces. Math Oper Res 35:704–720CrossRef
  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 CrossRef
  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 CrossRef
  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 CrossRef
  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 CrossRef
  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\) = 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 CrossRef
  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
  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 CrossRef
  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
  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
  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 Mathematics Studies 66:27–55CrossRef
  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 CrossRef
  Dantzig G, Fulkerson R, Johnson S (1954) Solution of a large-scale traveling-salesman problem. J Oper Res Soc Am 2(4):393–410
  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 CrossRef
  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 CrossRef
  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 CrossRef
  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 CrossRef
  Dey SS, Wolsey LA (2010a) Constrained infinite group relaxations of MIPs. SIAM J Optim 20(6):2890–2912CrossRef
  Dey SS, Wolsey LA (2010b) Two row mixed-integer cuts via lifting. Math Program 124:143–174CrossRef
  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 Nat Acad Sci USA 53(2):260CrossRef
  Gomory RE (1969) Some polyhedra related to combinatorial problems. Linear Algebra Appl 2(4):451–558CrossRef
  Gomory RE, Johnson EL, Evans L (2003) Corner polyhedra and their connection with cutting planes. Math Program 96(2):321–339CrossRef
  Gomory RE (2007) The atoms of integer programming. Ann Oper Res 149(1):99–102CrossRef
  Gomory RE, Johnson EL (1972a) Some continuous functions related to corner polyhedra, I. Math Program 3:23–85. doi:10.​1007/​BF01584976 CrossRef
  Gomory RE, Johnson EL (1972b) Some continuous functions related to corner polyhedra, II. Math Program 3:359–389. doi:10.​1007/​BF01585008 CrossRef
  Gomory RE, Johnson EL (2003) T-space and cutting planes. Math Program 96:341–375. doi:10.​1007/​s10107-003-0389-3 CrossRef
  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, H A, Kan GR, 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
  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–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 (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 CrossRef
  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
  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 CrossRef
  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–388CrossRef
  Wolsey LA (1975) Faces for a linear inequality in 0–1 variables. Math Program 8(1):165–178CrossRef
  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/​
  
• 作者单位：Amitabh Basu (1)
  Robert Hildebrand (2)
  Matthias Köppe (3)
  
  1. Department of Applied Mathematics and Statistics, The Johns Hopkins University, Baltimore, MD, 21218, USA
  2. Department of Mathematics, Institute for Operations Research, ETH Zürich, Zurich, Switzerland
  3. Department of Mathematics, University of California, Davis, Davis, CA, 95616, USA
  
• 刊物类别：Business and Economics
• 刊物主题：Economics
  Operation Research and Decision Theory
  Optimization
  Industrial and Production Engineering
  
• 出版者：Springer Berlin / Heidelberg
• ISSN：1614-2411

文摘

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.