Algorithmic and modeling insights via volumetric comparison of polyhedral relaxations. (English) Zbl 1394.52011
Summary: This is mostly a survey on some mathematical results concerning volumes of polytopes of interest in non-convex optimization. Our motivation is in geometrically comparing relaxations in the context of mixed-integer linear and nonlinear optimization, with the goal of gaining algorithmic and modeling insights. We consider relaxations of: fixed-charge formulations, vertex packing polytopes, boolean-quadric polytopes, and relaxations of graphs of monomials on box domains. Besides surveying the area, we do give a few new results, and we provide many directions for further work.
MSC:
| 52B11 | \(n\)-dimensional polytopes |
| 52B12 | Special polytopes (linear programming, centrally symmetric, etc.) |
| 90C10 | Integer programming |
| 90C11 | Mixed integer programming |
| 90C26 | Nonconvex programming, global optimization |
| 90C27 | Combinatorial optimization |
| 90C57 | Polyhedral combinatorics, branch-and-bound, branch-and-cut |
| 52A38 | Length, area, volume and convex sets (aspects of convex geometry) |
Keywords:
polytope; volume; global optimization; mixed-integer nonlinear optimization; fixed charge; facility location; vertex packing; Boolean quadric; monomial; spatial branch-and-boundReferences:
| [1] | Lee, J., Leyffer, S. (eds.): Mixed Integer Nonlinear Programming, Volume 154 of The IMA Volumes in Mathematics and its Applications. Springer, New York (2012) |
| [2] | Belotti, P; Lee, J; Liberti, L; Margot, F; Wächter, A, Branching and bounds tightening techniques for non-convex MINLP, Optim. Methods Softw., 24, 597-634, (2009) · Zbl 1179.90237 · doi:10.1080/10556780903087124 |
| [3] | Berge, C.: Principles of combinatorics. Translated from the French. Mathematics in Science and Engineering, Vol. 72. Academic, New York, London (1971) · Zbl 0227.05002 |
| [4] | Berstein, Y; Lee, J; Onn, S; Weismantel, R, Parametric nonlinear discrete optimization over well-described sets and matroid intersections, Math. Program., 124, 233-253, (2010) · Zbl 1198.90334 · doi:10.1007/s10107-010-0358-6 |
| [5] | Bonami, P; Biegler, LT; Conn, AR; Cornuéjols, G; Grossmann, IE; Laird, CD; Lee, J; Lodi, A; Margot, F; Sawaya, N; Wächter, A, An algorithmic framework for convex mixed integer nonlinear programs, Discrete Optim., 5, 186-204, (2008) · Zbl 1151.90028 · doi:10.1016/j.disopt.2006.10.011 |
| [6] | Brightwell, G; Winkler, P, Counting linear extensions, Order, 8, 225-242, (1991) · Zbl 0759.06001 · doi:10.1007/BF00383444 |
| [7] | Cafieri, S; Lee, J; Liberti, L, On convex relaxations of quadrilinear terms, J. Global Optim., 47, 661-685, (2010) · Zbl 1202.90236 · doi:10.1007/s10898-009-9484-1 |
| [8] | Loera, JA; Hemmecke, R; Köppe, M; Weismantel, R, Integer polynomial optimization in fixed dimension, Math. Oper. Res., 31, 147-153, (2006) · Zbl 1278.90267 · doi:10.1287/moor.1050.0169 |
| [9] | De Simone, C.: The cut polytope and the Boolean quadric polytope. Discrete Math. 79(1), 71-75 (1989/90) · Zbl 0683.90068 |
| [10] | Dittmer, S., Pak, I.: Counting linear extensions of restricted posets. arXiv:1802.06312. https://arxiv.org/abs/1802.06312 (2018) · Zbl 0741.90054 |
| [11] | Speakman, Emily E.: Volumetric Guidance for Handling Triple Products in Spatial Branch-and-Bound. Ph.D., University of Michigan (2017) |
| [12] | Grünbaum, B; Sreedharan, VP, An enumeration of simplicial 4-polytopes with 8 vertices, J. Comb. Theory, 2, 437-465, (1967) · Zbl 0156.43304 · doi:10.1016/S0021-9800(67)80055-3 |
| [13] | Hemmecke, R; Köppe, M; Lee, J; Weismantel, R; Jünger, M (ed.); Liebling, TM (ed.); Naddef, D (ed.); Nemhauser, GL (ed.); Pulleyblank, WR (ed.); Reinelt, G (ed.); Rinaldi, G (ed.); Wolsey, LA (ed.), Nonlinear integer programming, 561-618, (2010), Berlin, Heidelberg |
| [14] | Jeroslow, RG, There cannot be any algorithm for integer programming with quadratic constraints, Oper. Res., 21, 221-224, (1973) · Zbl 0257.90029 · doi:10.1287/opre.21.1.221 |
| [15] | Ko, C-W; Lee, J; Steingrímsson, E, The volume of relaxed Boolean-quadric and cut polytopes, Discrete Math, 163, 293-298, (1997) · Zbl 0872.90062 · doi:10.1016/0012-365X(95)00343-U |
| [16] | Lawrence, J, Polytope volume computation, Math. Comput., 57, 259-271, (1991) · Zbl 0734.52009 · doi:10.1090/S0025-5718-1991-1079024-2 |
| [17] | Lee, J., Skipper, D.: Volume computation for sparse boolean quadric relaxations. arXiv:1703.02444. https://arxiv.org/abs/1703.02444 (2017) · Zbl 0813.90094 |
| [18] | Lee, J, All-different polytopes, J. Comb. Optim., 6, 335-352, (2002) · Zbl 1007.90041 · doi:10.1023/A:1014804110661 |
| [19] | Lee, J, Mixed integer nonlinear programming: some modeling and solution issues, IBM J. Res. Dev., 51, 489-497, (2007) · doi:10.1147/rd.513.0489 |
| [20] | Lee, J; Morris, WD, Jr. geometric comparison of combinatorial polytopes, Discrete Appl. Math., 55, 163-182, (1994) · Zbl 0813.90094 · doi:10.1016/0166-218X(94)90006-X |
| [21] | Lee, J; Leung, J; Vries, S, Separating type-I odd-cycle inequalities for a binary-encoded edge-coloring formulation, J. Comb. Optim., 9, 59-67, (2005) · Zbl 1066.90109 · doi:10.1007/s10878-005-5484-3 |
| [22] | Mahadev, N.V.R., Peled, U.N.: Threshold Graphs and Related Topics, volume 56 of Annals of Discrete Mathematics. North-Holland Publishing Co., Amsterdam (1995) · Zbl 0852.05001 |
| [23] | Misener, R; Floudas, CA, ANTIGONE: algorithms for continuous/integer global optimization of nonlinear equations, J. Global Optim., 59, 503-526, (2014) · Zbl 1301.90063 · doi:10.1007/s10898-014-0166-2 |
| [24] | Onn, S.: Convex Discrete Optimization. European Mathematical Society, Zurich Lectures in Advanced Mathematics (2010) · Zbl 1219.90003 |
| [25] | Padberg, M, The Boolean quadric polytope: some characteristics, facets and relatives, Math. Program., 45, 139-172, (1989) · Zbl 0675.90056 · doi:10.1007/BF01589101 |
| [26] | Papachristodoulou, A., Anderson, J., Valmorbid, G., Prajna, S., Seiler, P., Parrilo, P.A.: SOSTOOLS: Sum of squares optimization toolbox for MATLAB. http://arxiv.org/abs/1310.4716. http://www.mit.edu/ parrilo/sostools (2013) |
| [27] | Pitowsky, I, Correlation polytopes: their geometry and complexity, Math. Program., 50, 395-414, (1991) · Zbl 0741.90054 · doi:10.1007/BF01594946 |
| [28] | Speakman, E., Lee, J.: On branching-point selection for trilinear monomials in spatial branch-and-bound: the hull relaxation. J. Global Optim. https://doi.org/10.1007/s10898-018-0620-7 (2018) · Zbl 1278.90267 |
| [29] | Speakman, E., Yu, H., Lee, J.: Experimental validation of volume-based comparison for double-McCormick relaxations. In: Salvagnin, D., Lombardi, M. (eds) Integration of AI and OR Techniques in Constraint Programming: 14th International Conference, CPAIOR 2017, Padua, Italy, June 5-8, 2017, Proceedings, pp. 229-243. Springer (2017) · Zbl 1492.90140 |
| [30] | Speakman, E; Lee, J, Quantifying double mccormick, Math. Oper. Res., 42, 1230-1253, (2017) · Zbl 1386.90121 · doi:10.1287/moor.2017.0846 |
| [31] | Stanley, R.P.: Enumerative combinatorics, 2nd edn. Volume 1, volume 49 of Cambridge Studies in Advanced Mathematics. Cambridge University Press (2012) · Zbl 1247.05003 |
| [32] | Stanley, RP, Two poset polytopes, Discrete Comput. Geom., 1, 9-23, (1986) · Zbl 0595.52008 · doi:10.1007/BF02187680 |
| [33] | Steingrímsson, E, A decomposition of \(2\)-weak vertex-packing polytopes, Discrete Comput. Geom., 12, 465-479, (1994) · Zbl 0813.52009 · doi:10.1007/BF02574393 |
| [34] | Tawarmalani, M., Sahinidis, N.V.: Convexification and Global Optimization in Continuous and Mixed-Integer Nonlinear Programming: Theory, Algorithms, Software, and Applications Nonconvex Optimization and Its Applications. Springer, New York (2002) · Zbl 1031.90022 · doi:10.1007/978-1-4757-3532-1 |
| [35] | Vigerske, S., Gleixner, A.: SCIP: global optimization of mixed-integer nonlinear programs in a branch-and-cut framework. Optim. Methods Softw. https://doi.org/10.1080/10556788.2017.1335312 (2017) · Zbl 1398.90112 |
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.
