A Combinatorial Approach for Small and Strong Formulations of Disjunctive Constraints

References

• [1] Achterberg T, Koch T, Martin A (2005) Branching rules revisited. Oper. Res. Lett. 33(1):42–54.Crossref, Google Scholar
• [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
• [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
• [4] Aichholzer O, Aurenhammer F, Hurtado F, Krasser H (2003) Towards compatible triangulations. Theoret. Comput. Sci. 296(1):3–13.Crossref, Google Scholar
• [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
• [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
• [7] Apt KR (2003) Principles of Constraint Programming (Cambridge University Press, Cambridge, UK).Crossref, Google Scholar
• [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
• [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] 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] Bertsimas D, Shioda R (2009) Algorithm for cardinality-constrained quadratic optimization. Comput. Optim. Appl. 43(1):1–22.Crossref, Google Scholar
• [12] Bienstock D (1996) Computational study of a family of mixed-integer quadratic programming problems. Math. Programming 74(2):121–140.Crossref, Google Scholar
• [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
• [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
• [15] Conforti M, Cornuéjols G, Zambelli G (2014) Integer Programming (Springer, New York).Crossref, Google Scholar
• [16] Cornaz D, Fonlupt J (2006) Chromatic characterization of biclique covers. Discrete Math. 306(5):495–507.Crossref, Google Scholar
• [17] Crama Y, Hammer PL (2011) Boolean Functions: Theory, Algorithms, and Applications (Cambridge University Press, Cambridge, UK).Crossref, Google Scholar
• [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
• [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
• [20] Fishburn PC, Hammer PL (1996) Bipartite dimensions and bipartite degrees of graphs. Discrete Math. 160(1–3):127–148.Crossref, Google Scholar
• [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
• [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
• [23] Garey MR, Johnson DS (1979) Computers and Intractability (W. H. Freeman and Company, New York).Google Scholar
• [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
• [25] Hooker JN (2002) Logic, optimization, and constraint programming. INFORMS J. Comput. 14(4):295–321.Link, Google Scholar
• [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] 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
• [28] Jaffar J, Maher MJ (1994) Constraint logic programming: A survey. J. Logic Programming 20(1):503–581.Crossref, Google Scholar
• [29] Jeroslow RG, Lowe JK (1984) Modelling with integer variables. Mathematical Programming Study, vol. 22 (Springer, Berlin), 167–184.Crossref, Google Scholar
• [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
• [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
• [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
• [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
• [34] Kuhn HW (1960) Some combinatorial lemmas in topology. IBM J. Res. Development 4(5):518–528.Crossref, Google Scholar
• [35] Land A, Doig A (1960) An automatic method for solving discrete programming problems. Econometrica 28(3):497–520.Crossref, Google Scholar
• [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
• [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
• [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
• [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
• [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
• [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
• [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
• [43] Orlin J (1977) Contentment in graph theory: Covering graphs with cliques. Indagationes Mathematicae (Proc.) 80(5):406–424.Crossref, Google Scholar
• [44] Ostrowski J, Linderoth J, Rossi F, Smriglio S (2011) Orbital branching. Math. Programming 126(1):147–178.Crossref, Google Scholar
• [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
• [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
• [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
• [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] Sahinidis NV (1996) BARON: A general purpose global optimization software package. J. Global Optim. 8(2):201–205.Crossref, Google Scholar
• [50] Savage C (1997) A survey of combinatorial gray codes. SIAM Rev. 39(4):605–629.Crossref, Google Scholar
• [51] Todd MJ (1977) Union Jack triangulations. Karamardian S, ed. Fixed Points: Algorithms and Applications (Elsevier, Amsterdam), 315–336.Crossref, Google Scholar
• [52] Vielma JP (2015) Mixed integer linear programming formulation techniques. SIAM Rev. 57(1):3–57.Crossref, Google Scholar
• [53] Vielma JP (2017) Embedding formulations and complexity for unions of polyhedra. Management Sci. 64(10):4471–4965.Google Scholar
• [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
• [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
• [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
• [57] Vielma JP, Keha AB, Nemhauser GL (2008) Nonconvex, lower semicontinuous piecewise linear optimization. Discrete Optim. 5(2):467–488.Crossref, Google Scholar
• [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
• [59] Yildiz S, Vielma JP (2013) Incremental and encoding formulations for mixed integer programming. Oper. Res. Lett. 41:654–658.Crossref, Google Scholar
• [60] Ziegler G (2007) Lectures on Polytopes (Springer, New York).Google Scholar