A combinatorial approach for small and strong formulations of disjunctive constraints. (English) Zbl 1434.90170
Summary: A framework is presented for constructing strong mixed-integer programming formulations for logical disjunctive constraints. This approach is a generalization of the logarithmically sized formulations of the second author and G. L. Nemhauser [Math. Program. 128, No. 1–2 (A), 49–72 (2011; Zbl 1218.90137)] for special ordered sets of type 2 (SOS2) constraints, and a complete characterization of its expressive power is offered. The framework is applied to a variety of disjunctive constraints, producing novel small and strong formulations for outer approximations of multilinear terms, generalizations of special ordered sets, piecewise linear functions over a variety of domains, and obstacle avoidance constraints.
MSC:
| 90C27 | Combinatorial optimization |
| 90C11 | Mixed integer programming |
| 90C57 | Polyhedral combinatorics, branch-and-bound, branch-and-cut |
Citations:
Zbl 1218.90137References:
| [1] | [1] Achterberg T, Koch T, Martin A (2005) Branching rules revisited. Oper. Res. Lett. 33(1):42-54.Crossref, Google Scholar · Zbl 1076.90037 · doi:10.1016/j.orl.2004.04.002 |
| [2] | [2] Achterberg T, Berthold T, Koch T, Wolter K (2008) Constraint integer programming: A new approach to integrate CP and MIP. Perron L, Trick MA, eds. Proc. 5th Internat. Conf. CPAIOR 2007 (Springer, Berlin), 6-20.Crossref, Google Scholar · Zbl 1142.68504 · doi:10.1007/978-3-540-68155-7_4 |
| [3] | [3] Adams WP, Henry SM (2012) Base-2 expansions for linearizing products of functions of discrete variables. Oper. Res. 60(6):1477-1490.Link, Google Scholar · Zbl 1287.90033 |
| [4] | [4] Aichholzer O, Aurenhammer F, Hurtado F, Krasser H (2003) Towards compatible triangulations. Theoret. Comput. Sci. 296(1):3-13.Crossref, Google Scholar · Zbl 1045.68140 · doi:10.1016/S0304-3975(02)00428-0 |
| [5] | [5] Androulakis I, Maranas CD (1995) αBB: A global optimization method for general constrained nonconvex problems. J. Global Optim. 7(4):337-363.Crossref, Google Scholar · Zbl 0846.90087 · doi:10.1007/BF01099647 |
| [6] | [6] Appleget JA, Wood RK (2000) Explicit-constraint branching for solving mixed-integer programs. Laguna M, González JL, eds. Computing Tools for Modeling, Optimization, and Simulation: Interfaces in Computer Science and Operations Research, Operations Research/Computer Science Interfaces Series, vol. 12 (Kluwer, Dordrecht, Netherlands), 245-261.Crossref, Google Scholar · doi:10.1007/978-1-4615-4567-5_14 |
| [7] | [7] Apt KR (2003) Principles of Constraint Programming (Cambridge University Press, Cambridge, UK).Crossref, Google Scholar · Zbl 1187.68132 · doi:10.1017/CBO9780511615320 |
| [8] | [8] Balas E (1985) Disjunctive programming and a hierarchy of relaxations for discrete optimization problems. SIAM J. Algorithmic Discrete Methods 6(3):466-486.Crossref, Google Scholar · Zbl 0592.90070 · doi:10.1137/0606047 |
| [9] | [9] Beale EML, Tomlin JA (1970) Special facilities in a general mathematical programming system for non-convex problems using ordered sets of variables. Lawrence J, ed. Proc. 5th Internat. Conf. Oper. Res. (Tavistock Publications, London), 447-454.Google Scholar |
| [10] | [10] Bellingham JS (2002) Coordination and control of UAV fleets using mixed-integer linear programming. Master’s thesis, Massachusetts Institute of Technology, Cambridge, MA.Google Scholar |
| [11] | [11] Bertsimas D, Shioda R (2009) Algorithm for cardinality-constrained quadratic optimization. Comput. Optim. Appl. 43(1):1-22.Crossref, Google Scholar · Zbl 1178.90262 · doi:10.1007/s10589-007-9126-9 |
| [12] | [12] Bienstock D (1996) Computational study of a family of mixed-integer quadratic programming problems. Math. Programming 74(2):121-140.Crossref, Google Scholar · Zbl 0855.90090 · doi:10.1007/BF02592208 |
| [13] | [13] Bixby R, Rothberg E (2007) Progress in computational mixed integer programming—A look back from the other side of the tipping point. Ann. Oper. Res. 149(1):37-41.Crossref, Google Scholar · Zbl 1213.90011 · doi:10.1007/s10479-006-0091-y |
| [14] | [14] Chang TJ, Meade N, Beasley JE, Sharaiha YM (2000) Heuristics for cardinality constrained portfolio optimization. Comput. Oper. Res. 27(13):1271-1302.Crossref, Google Scholar · Zbl 1032.91074 · doi:10.1016/S0305-0548(99)00074-X |
| [15] | [15] Conforti M, Cornuéjols G, Zambelli G (2014) Integer Programming (Springer, New York).Crossref, Google Scholar · Zbl 1307.90001 · doi:10.1007/978-3-319-11008-0 |
| [16] | [16] Cornaz D, Fonlupt J (2006) Chromatic characterization of biclique covers. Discrete Math. 306(5):495-507.Crossref, Google Scholar · Zbl 1087.05043 · doi:10.1016/j.disc.2006.01.010 |
| [17] | [17] Crama Y, Hammer PL (2011) Boolean Functions: Theory, Algorithms, and Applications (Cambridge University Press, Cambridge, UK).Crossref, Google Scholar · Zbl 1237.06001 · doi:10.1017/CBO9780511852008 |
| [18] | [18] de Farias IR Jr., Johnson EL, Nemhauser GL (2001) Branch-and-cut for combinatorial optimization problems without auxiliary binary variables. Knowledge Engrg. Rev. 16(1):25-39.Crossref, Google Scholar · Zbl 1060.90082 · doi:10.1017/S0269888901000030 |
| [19] | [19] Deits R, Tedrake R (2015) Efficient mixed-integer planning for UAVs in cluttered environments. 2015 IEEE Internat. Conf. Robotics Automation (ICRA) (IEEE, New York), 42-49.Crossref, Google Scholar · doi:10.1109/ICRA.2015.7138978 |
| [20] | [20] Fishburn PC, Hammer PL (1996) Bipartite dimensions and bipartite degrees of graphs. Discrete Math. 160(1-3):127-148.Crossref, Google Scholar · Zbl 0861.05035 · doi:10.1016/0012-365X(95)00154-O |
| [21] | [21] Floudas CA, Lin X (2005) Mixed integer linear programming in process scheduling: Modeling, algorithms, and applications. Ann. Oper. Res. 139(1):131-162.Crossref, Google Scholar · Zbl 1091.90055 · doi:10.1007/s10479-005-3446-x |
| [22] | [22] Foulds LR, Haugland D, Jörnsten K (1992) A bilinear approach to the pooling problem. Optimization 24(1/2):165-180.Crossref, Google Scholar · Zbl 0817.90073 · doi:10.1080/02331939208843786 |
| [23] | [23] Garey MR, Johnson DS (1979) Computers and Intractability (W. H. Freeman and Company, New York).Google Scholar · Zbl 0411.68039 |
| [24] | [24] Gruber H, Holzer M (2007) Inapproximability of nondeterministic state and transition complexity assuming P≠NP. Harju T, Karhumäki J, Lepistö A, eds. Developments in Language Theory. DLT 2007, Lecture Notes in Computer Science, vol. 4588 (Springer, New York), 205-216.Crossref, Google Scholar · Zbl 1202.68226 · doi:10.1007/978-3-540-73208-2_21 |
| [25] | [25] Hooker JN (2002) Logic, optimization, and constraint programming. INFORMS J. Comput. 14(4):295-321.Link, Google Scholar · Zbl 1238.90002 |
| [26] | [26] Huchette J, Vielma JP (2017) Nonconvex piecewise linear functions: Advanced formulations and simple modeling tools. Working paper, Massachusetts Institute of Technology, Cambridge.Google Scholar |
| [27] | [27] de Farias IR Jr., Nemhauser GL (2003) A polyhedral study of the cardinality constrained knapsack problem. Math. Programming 96(3):439-467.Crossref, Google Scholar · Zbl 1023.90085 · doi:10.1007/s10107-003-0420-8 |
| [28] | [28] Jaffar J, Maher MJ (1994) Constraint logic programming: A survey. J. Logic Programming 20(1):503-581.Crossref, Google Scholar · doi:10.1016/0743-1066(94)90033-7 |
| [29] | [29] Jeroslow RG, Lowe JK (1984) Modelling with integer variables. Mathematical Programming Study, vol. 22 (Springer, Berlin), 167-184.Crossref, Google Scholar · Zbl 0554.90081 · doi:10.1007/BFb0121015 |
| [30] | [30] Jünger M, Liebling T, Naddef D, Nemhauser G, Pulleyblank W, Reinelt G, Rinaldi G, Wolsey L (2010) 50 Years of Integer Programming 1958-2008 (Springer, New York).Crossref, Google Scholar · Zbl 1181.90003 · doi:10.1007/978-3-540-68279-0 |
| [31] | [31] Keha AB, de Farias IR, Nemhauser GL (2004) Models for representing piecewise linear cost functions. Oper. Res. Lett. 32(1):44-48.Crossref, Google Scholar · Zbl 1056.90107 · doi:10.1016/S0167-6377(03)00059-2 |
| [32] | [32] Keha AB, de Farias IR, Nemhauser GL (2006) A branch-and-cut algorithm without binary variables for nonconvex piecewise linear optimization. Oper. Res. 54(5):847-858.Link, Google Scholar · Zbl 1167.90589 |
| [33] | [33] Kondili E, Pantelides CC, Sargent RWH (1993) A general algorithm for short-term scheduling of batch operations—I. MILP formulation. Comput. Chemical Engrg. 17(2):211-227.Crossref, Google Scholar · doi:10.1016/0098-1354(93)80015-F |
| [34] | [34] Kuhn HW (1960) Some combinatorial lemmas in topology. IBM J. Res. Development 4(5):518-528.Crossref, Google Scholar · Zbl 0109.15603 · doi:10.1147/rd.45.0518 |
| [35] | [35] Land A, Doig A (1960) An automatic method for solving discrete programming problems. Econometrica 28(3):497-520.Crossref, Google Scholar · Zbl 0101.37004 · doi:10.2307/1910129 |
| [36] | [36] Luedtke J, Namazifar M, Linderoth J (2012) Some results on the strength of relaxations of multilinear functions. Math. Programming 136(2):325-351.Crossref, Google Scholar · Zbl 1286.90117 · doi:10.1007/s10107-012-0606-z |
| [37] | [37] Martin A, Moller M, Moritz S (2006) Mixed integer models for the stationary case of gas network optimization. Math. Programming 105(2-3):563-582.Crossref, Google Scholar · Zbl 1085.90035 · doi:10.1007/s10107-005-0665-5 |
| [38] | [38] McCormick G (1976) Computability of global solutions to factorable nonconvex programs: Part I—Convex underestimating problems. Math. Programming 10(1):147-175.Crossref, Google Scholar · Zbl 0349.90100 · doi:10.1007/BF01580665 |
| [39] | [39] Mellinger D, Kushleyev A, Kumar V (2012) Mixed-integer quadratic program trajectory generation for heterogeneous quadrotor teams. 2012 IEEE Internat. Conf. Robotics Automation (IEEE, New York), 477-483.Crossref, Google Scholar · doi:10.1109/ICRA.2012.6225009 |
| [40] | [40] Misener R, Floudas C (2012) Global optimization of mixed-integer quadratically-constrained quadratic programs (MIQCQP) through piecewise-linear and edge-concave relaxations. Math. Programming 136(1):155-182.Crossref, Google Scholar · Zbl 1257.90079 · doi:10.1007/s10107-012-0555-6 |
| [41] | [41] Misener R, Thompson JP, Floudas CA (2011) APOGEE: Global optimization of standard, generalized, and extended pooling problems via linear and logarithmic partitioning schemes. Comput. Chemical Engrg. 35(5):876-892.Crossref, Google Scholar · doi:10.1016/j.compchemeng.2011.01.026 |
| [42] | [42] Muldoon FM, Adams WP, Sherali HD (2013) Ideal representations of lexicographic orderings and base-2 expansions of integer variables. Oper. Res. Lett. 41(1):32-39.Crossref, Google Scholar · Zbl 1266.90131 · doi:10.1016/j.orl.2012.10.005 |
| [43] | [43] Orlin J (1977) Contentment in graph theory: Covering graphs with cliques. Indagationes Mathematicae (Proc.) 80(5):406-424.Crossref, Google Scholar · Zbl 0374.05041 · doi:10.1016/1385-7258(77)90055-5 |
| [44] | [44] Ostrowski J, Linderoth J, Rossi F, Smriglio S (2011) Orbital branching. Math. Programming 126(1):147-178.Crossref, Google Scholar · Zbl 1206.90101 · doi:10.1007/s10107-009-0273-x |
| [45] | [45] Prodan I, Stoican F, Olaru S, Niculescu S-I (2012) Enhancements on the hyperplanes arrangements in mixed-integer programming techniques. J. Optim. Theory Appl. 154(2):549-572.Crossref, Google Scholar · Zbl 1256.90029 · doi:10.1007/s10957-012-0022-9 |
| [46] | [46] Prodan I, Stoican F, Olaru S, Niculescu S-I (2016) Mixed-Integer Representations in Control Design: Mathematical Foundations and Applications, SpringerBriefs in Electrical and Computer Engineering (Springer, New York).Crossref, Google Scholar · Zbl 1337.93001 · doi:10.1007/978-3-319-26995-5 |
| [47] | [47] Quesada I, Grossmann IE (1995) A global optimization algorithm for linear fractional and bilinear programs. J. Global Optim. 6(1):39-76.Crossref, Google Scholar · Zbl 0835.90074 · doi:10.1007/BF01106605 |
| [48] | [48] Ryan DM, Foster BA (1981) An integer programming approach to scheduling. Wren A, ed. Computer Scheduling of Public Transport (Elsevier, Amsterdam), 269-280.Google Scholar |
| [49] | [49] Sahinidis NV (1996) BARON: A general purpose global optimization software package. J. Global Optim. 8(2):201-205.Crossref, Google Scholar · Zbl 0856.90104 · doi:10.1007/BF00138693 |
| [50] | [50] Savage C (1997) A survey of combinatorial gray codes. SIAM Rev. 39(4):605-629.Crossref, Google Scholar · Zbl 1049.94513 · doi:10.1137/S0036144595295272 |
| [51] | [51] Todd MJ (1977) Union Jack triangulations. Karamardian S, ed. Fixed Points: Algorithms and Applications (Elsevier, Amsterdam), 315-336.Crossref, Google Scholar · Zbl 0424.90084 · doi:10.1016/B978-0-12-398050-2.50021-9 |
| [52] | [52] Vielma JP (2015) Mixed integer linear programming formulation techniques. SIAM Rev. 57(1):3-57.Crossref, Google Scholar · Zbl 1338.90277 · doi:10.1137/130915303 |
| [53] | [53] Vielma JP (2017) Embedding formulations and complexity for unions of polyhedra. Management Sci. 64(10):4471-4965.Google Scholar |
| [54] | [54] Vielma JP, Nemhauser G (2011) Modeling disjunctive constraints with a logarithmic number of binary variables and constraints. Math. Programming 128(1-2):49-72.Crossref, Google Scholar · Zbl 1218.90137 · doi:10.1007/s10107-009-0295-4 |
| [55] | [55] Vielma JP, Ahmed S, Nemhauser G (2008) A lifted linear programming branch-and-bound algorithm for mixed-integer conic quadratic programs. INFORMS J. Comput. 20(3):438-450.Link, Google Scholar · Zbl 1243.90170 |
| [56] | [56] Vielma JP, Ahmed S, Nemhauser G (2010) Mixed-integer models for nonseparable piecewise-linear optimization: Unifying framework and extensions. Oper. Res. 58(2):303-315.Link, Google Scholar · Zbl 1226.90046 |
| [57] | [57] Vielma JP, Keha AB, Nemhauser GL (2008) Nonconvex, lower semicontinuous piecewise linear optimization. Discrete Optim. 5(2):467-488.Crossref, Google Scholar · Zbl 1190.90149 · doi:10.1016/j.disopt.2007.07.001 |
| [58] | [58] Wicaksono DS, Karimi IA (2008) Piecewise MILP under- and overestimators for global optimisation of bilinear programs. AIChE J. 54(4):991-1008.Crossref, Google Scholar · doi:10.1002/aic.11425 |
| [59] | [59] Yildiz S, Vielma JP (2013) Incremental and encoding formulations for mixed integer programming. Oper. Res. Lett. 41:654-658.Crossref, Google Scholar · Zbl 1287.90040 · doi:10.1016/j.orl.2013.09.004 |
| [60] | [60] Ziegler G (2007) Lectures on Polytopes (Springer, |
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.
