Conforti, Michele; Cornuéjols, Gérard; Zambelli, Giacomo Extended formulations in combinatorial optimization. (English) Zbl 1219.90193 4OR 8, No. 1, 1-48 (2010). Summary: This survey is concerned with the size of perfect formulations for combinatorial optimization problems. By “perfect formulation”, we mean a system of linear inequalities that describes the convex hull of feasible solutions, viewed as vectors. Natural perfect formulations often have a number of inequalities that is exponential in the size of the data needed to describe the problem. Here we are particularly interested in situations where the addition of a polynomial number of extra variables allows a formulation with a polynomial number of inequalities. Such formulations are called “compact extended formulations”. We survey various tools for deriving and studying extended formulations, such as Fourier’s procedure for projection, Minkowski-Weyl’s theorem, Balas’ theorem for the union of polyhedra, Yannakakis’ theorem on the size of an extended formulation, dynamic programming, and variable discretization. For each tool that we introduce, we present one or several examples of how this tool is applied. In particular, we present compact extended formulations for several graph problems involving cuts, trees, cycles and matchings, and for the mixing set. We also present Bienstock’s approximate compact extended formulation for the knapsack problem, Goemans’ result on the size of an extended formulation for the permutahedron, and the Faenza-Kaibel extended formulation for orbitopes. Cited in 67 Documents MSC: 90C57 Polyhedral combinatorics, branch-and-bound, branch-and-cut 90C27 Combinatorial optimization 90C10 Integer programming Keywords:polyhedral combinatorics; extended formulations; projections; matchings PDFBibTeX XMLCite \textit{M. Conforti} et al., 4OR 8, No. 1, 1--48 (2010; Zbl 1219.90193) Full Text: DOI References: [1] Ajtai M, Komlós J, Szemerédi E (1983) An O(n log n) sorting network. In: Proceedings of the 15th annual ACM symposium on theory of computing. pp 1–9 [2] Alon N, Yuster R, Zwick U (1995) Color-coding. J ACM 42: 844–856 · Zbl 0885.68116 [3] Avis D, Fukuda K (1992) A pivoting algorithm for convex hulls and vertex enumeration of arrangements and polyhedra. Discrete Comput Geom 8: 295–313 · Zbl 0752.68082 [4] Balas E (1998) Disjunctive programming: properties of the convex hull of feasible points, GSIA Management Science Research Report MSRR 348, Carnegie Mellon University (1974). published as invited paper in Discrete Appl Math 89: 1–44 · Zbl 0921.90118 [5] Balas E (1985) Disjunctive programming and a hierarchy of relaxations for discrete optimization problems. SIAM J Alg Discrete Methods 6: 466–486 · Zbl 0592.90070 [6] Balas E, Pulleyblank WR (1983) The perfectly matchable subgraph polytope of a bipartite graph. Networks 13: 495–516 · Zbl 0525.90069 [7] Balas E, Pulleyblank WR (1989) The perfectly matchable subgraph polytope of an arbitrary graph. Combinatorica 9: 321–337 · Zbl 0723.05087 [8] Barahona F (1993) On cuts and matchings in planar graphs. Math Program 60: 53–68 · Zbl 0795.90017 [9] Barahona F (1993) Reducing matching to polynomial size linear programming. SIAM J Optim 3: 688–695 · Zbl 0806.90100 [10] Bienstock D (2008) Approximate formulations for 0 knapsack sets. Oper Res Lett 36: 317–320 · Zbl 1152.90535 [11] Bienstock D, McClosky B (2008) Tightening simple mixed-integer sets with guaranteed bounds, manuscript. http://www.caam.rice.edu/\(\sim\)bjm4/ak.pdf · Zbl 1274.90294 [12] Carr R, Konjevod G, Little G, Natarajan V, Parekh O (2007) Compacting cuts: a new linear formulation for minimum cut. Proc Symp Discrete Alg 43–52 · Zbl 1302.90168 [13] Conforti M, Cornuéjols G and Zambelli G (2009) Polyhedral approaches to mixed integer linear programming, in 50 Years of integer programming 1958–2008. Springer, Berlin, pp 343–385 · Zbl 1187.90002 [14] Conforti M, Di Summa M, Eisenbrand F, Wolsey LA (2009) Network formulations of mixed-integer programs. Math Oper Res 34: 194–209 · Zbl 1218.90133 [15] Conforti M, Wolsey L (2008) Compact formulations as a union of polyhedra. Math Program 114: 277–289 · Zbl 1145.90044 [16] Conforti M, Wolsey L, Zambelli G (2008) Projecting an extended formulation for mixed-integer covers on bipartite graphs, working paper. http://www.math.unipd.it/\(\sim\)giacomo/papers/mix-tree.pdf · Zbl 1218.90134 [17] Cormen TH, Leiserson CE, Rivest RL, Stein C (2001) Introduction to algorithms. MIT Press, Cambridge [18] Edmonds J (1965) Maximum matching and a polyhedron with 0,1-vertices. J Res Natl Bur Stand Sect B 69: 125–130 · Zbl 0141.21802 [19] Edmonds J (1970) Submodular functions, matroids, and certain polyhedra. In: Guy R, Hanani H, Sauer N, Schönheim J (eds) Combinatorial structures and their applications. Proceedings calgary international conference on combinatorial structures and their applications, Calgary, Alberta, 1969. Gordon and Breach, New York, pp 69–87 [20] Edmonds J (1971) Matroids and the greedy algorithm. Math Program 1: 127–136 · Zbl 0253.90027 [21] Edmonds J (1973) Edge-disjoint branchings, in combinatorial algorithms. In: Rustin R (ed) Courant computer science symosium 9, Monteray, California, 1972. Algorithmic Press, New York, pp 91–96 [22] Edmonds J, Johnson EL (1973) Matching, Euler tours and the Chinese postman. Math Program 5: 88–124 · Zbl 0281.90073 [23] Faenza Y, Kaibel V (2009) Extended formulations for packing and partitioning orbitopes. Math Oper Res 34: 686–697 · Zbl 1218.90124 [24] Fourier JBJ (1826) Solution d’une question particulière du calcul des inégalités. Nouveau Bulletin des Sciences par la Société Philomatique de Paris, pp 317–319 [25] Fulkerson DR (1970) Blocking polyhedra. In: Harris B (ed) Graph theory and its applications. Proceedings advanced seminar Madison, Wisconsin (1969). Academic Press, New York, pp 93–112 [26] Gerards B (1991) Compact systems for T-join and perfect matching polyhedra of graphs with bounded genus. Oper Res Lett 10: 377–382 · Zbl 0748.90045 [27] Giles R, Trotter L Jr. (1981) On the stable set polytope for K 1,3-free graphs. J Combin Theory B 31: 313–326 · Zbl 0494.05032 [28] Goemans MX (2010) Smallest compact formulation for the permutahedron, working paper. MIT Department of Mathematics [29] Guenin B (2001) A characterization of weakly bipartite graphs. J Combin Theory B 83: 112–168 · Zbl 1030.05103 [30] Günlük O, Pochet Y (2001) Mixing mixed-integer inequalities. Math Program 90: 429–458 · Zbl 1041.90033 [31] Heller I, Tompkins CB (1956) An extension of a theorem of Danzig’s. In: Kuhn HW, Tucker AW (eds) Linear inequalities and related systems. Princeton University Press, Princeton, pp 247–254 · Zbl 0072.37804 [32] Hoffman AJ, Kruskal JB (1956) Integral boundary points of polyhedra. In: Kuhn HW, Tucker AW (eds) Linear inequalities and related systems. Princeton University Press, Princeton, pp 223–246 · Zbl 0072.37803 [33] Ibarra OH, Kim CE (1975) Fast approximation algorithms for the knapsack and sum of subset problems. J ACM 22: 463–468 · Zbl 0345.90049 [34] Jeroslow R (1975) On defining sets of vertices of the hypercube by linear inequalities. Discrete Math 11: 119–124 · Zbl 0297.52009 [35] Kaibel V, Pashkovich K (2010) D.O. Theis, symmetry matters for sizes of extended formulations, accepted in IPCO 2010 · Zbl 1285.90052 [36] Kaibel V, Pfetsch ME (2008) Packing and partitioning orbitopes. Math Program A 114: 1–36 · Zbl 1171.90004 [37] Karp RM (1972) Reducibility among combinatorial problems. In: Miller RE, Thatcher JW (eds) Complexity of computer computations. Plenum Press, New York, pp 85–103 [38] Lawler EL (1977) Fast approximation algorithms for knapsack problems. In: Symposium on foundations of computer science. pp 206–213 [39] Meyer RR (1974) On the existence of optimal solutions to integer and mixed integer programming problems. Math Program 7: 223–235 · Zbl 0292.90036 [40] Miller A, Wolsey LA (2003) Tight formulations for some simple MIPs and convex objective IPs. Math Program B 98: 73–88 · Zbl 1047.90035 [41] Padberg MW, Rao MR (1982) Odd minimum cut-sets and b-matchings. Math Oper Res 7: 67–80 · Zbl 0499.90056 [42] Pochet Y, Wolsey LA (1994) Polyhedra for lot-sizing with Wagner–Whitin costs. Math Program 67: 297–324 · Zbl 0822.90049 [43] Pochet Y, Wolsey LA (2006) Production planning by mixed integer programming. Springer Series in Operations Research and Financial Engineering, New York · Zbl 1102.90039 [44] Pulleyblank WR, Shepherd FB (1993) Formulations for the stable set polytope. In: Rinaldi G, Wolsey LA (eds) Proceedings of IPCO III. Springer, Berlin, pp 267–279 · Zbl 0945.68524 [45] Schrijver A (1986) Theory of linear and integer programming. Wiley, New York · Zbl 0665.90063 [46] Schrijver A (2003) Combinatorial optimization, polyhedra and efficiency. Springer, Berlin · Zbl 1041.90001 [47] Seymour PD (1979) Sums of circuits. In: Bondy JA, Murty USR (eds) Graph theory and related topics. Academic Press, New York, pp 341–355 [48] Van Vyve M (2005) The continuous mixing polyhedron. Math Oper Res 30: 441–452 · Zbl 1082.90075 [49] Van Vyve M, Wolsey LA (2006) Approximate extended formulations. Math Program 105: 501–522 · Zbl 1085.90051 [50] Yannakakis M (1991) Expressing combinatorial optimization problems by linear programs. J Comput Syst Sci 43: 441–466 · Zbl 0748.90074 [51] Ziegler GM (1995) Lectures on polytopes. Springer, New York · Zbl 0823.52002 This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.