Analyzing the computational impact of MIQCP solver components

Timo Berthold; Ambros M. Gleixner; Stefan Heinz; Stefan Vigerske

doi:10.3934/naco.2012.2.739

Article Contents

2012, Volume 2, Issue 4: 739-748. Doi: 10.3934/naco.2012.2.739

This issue Previous Article Two-stage stochastic programs: Integer variables, dominance relations and PDE constraints Next Article Simulation of Lévy-Driven models and its application in finance

Analyzing the computational impact of MIQCP solver components

1.
Zuse Institute Berlin, Takustr. 7, 14195 Berlin
2.
Humboldt-Universität, Department of Mathematics, Unter den Linden 6, 10099 Berlin

Received: May 2012

Revised: October 2012

Published: November 2012

Abstract / Introduction Related Papers Cited by

Abstract

We provide a computational study of the performance of a state-of-the-art solver for nonconvex mixed-integer quadratically constrained programs (MIQCPs). Since successful general-purpose solvers for large problem classes necessarily comprise a variety of algorithmic techniques, we focus especially on the impact of the individual solver components. The solver SCIP used for the experiments implements a branch-and-cut algorithm based on a linear relaxation to solve MIQCPs to global optimality. Our analysis is based on a set of 86~publicly available test instances.

Keywords:

Mixed-integer quadratically constrained programming,
mixed-integer programming,
branch-and-cut,
nonconvex,
global optimization,
software engineering.

Mathematics Subject Classification: Primary: 90C11, Secondary: 90C26, 90C30.

Citation:

Related Papers

Cited by

References

[1]	T. Achterberg, "Constraint Integer Programming," PhD thesis, Technische Universitt Berlin, 2007.
[2]	T. Achterberg and T. Berthold, Hybrid branching, in "Proc. of CPAIOR 2009" (eds. W. J. van Hoeve and J. N. Hooker), Springer, 5547 (2009), 309-311.
[3]	T. Achterberg, T. Berthold, T. Koch and K. Wolter, Constraint integer programming: A new approach to integrate CP and MIP, in "Proc. of CPAIOR 2008" (eds. L. Perron and M. Trick), Springer, 5015 (2008), 6-20.
[4]	K. Abhishek, S. Leyffer and J. T. Linderoth, FilMINT: An outer-approximation-based solver for nonlinear mixed integer programs, INFORMS J. Comput., 22 (2010), 555-567.doi: 10.1287/ijoc.1090.0373.
[5]	P. Belotti, J. Lee, L. Liberti, F. Margot and A. Wächter, Branching and bounds tightening techniques for non-convex MINLP, Optim. Methods Softw., 24 (2009), 597-634.doi: 10.1080/10556780903087124.
[6]	T. Berthold, "Primal Heuristics for Mixed Integer Programs," Master's thesis, Technische Universitt Berlin, 2006.
[7]	T. Berthold and A. M. Gleixner, Undercover - a primal MINLP heuristic exploring a largest sub-MIP, ZIB-Report 12-07, Zuse Institute Berlin, 2012. Available from: http://vs24.kobv.de/opus4-zib/frontdoor/index/index/docId/1463/.
[8]	T. Berthold, S. Heinz, M. E. Pfetsch and S. Vigerske, Large neighborhood search beyond MIP, in "Proceedings of the 9th Metaheuristics International Conference (MIC 2011)" (eds. L. D. Gaspero, A. Schaerf and T. Stützle), (2011), 51-60.
[9]	T. Berthold, S. Heinz and S. Vigerske, Extending a CIP framework to solve MIQCPs, in Lee and Leyffer [16], 427-444.
[10]	P. Bonami, L. T. Biegler, A. R. Conn, G. Cornuéjols, I. E. Grossmann, C. D. Laird, J. Lee, A. Lodi, F. Margot, N. W. Sawaya and A. Wächter, An algorithmic framework for convex mixed integer nonlinear programs, Discrete Optim., 5 (2008), 186-204.doi: 10.1016/j.disopt.2006.10.011.
[11]	P. Bonami, M. Kilinç and J. Linderoth, Algorithms and software for convex mixed integer nonlinear programs, in Lee and Leyffer [16], 1-40.
[12]	M. R. Bussieck, A. S. Drud and A. Meeraus, MINLPLib - a collection of test models for mixed-integer nonlinear programming, INFORMS J. Comput., 15 (2003), 114-119.doi: 10.1287/ijoc.15.1.114.15159.
[13]	M. R. Bussieck and S. Vigerske, MINLP solver software, in "Wiley Encyclopedia of Operations Research and Management Science" (eds. J. J. C. et. al.), Wiley & Sons, Inc., 2010.
[14]	F. Domes and A. Neumaier, Constraint propagation on quadratic constraints, Constraints, 15 (2010), 404-429.doi: 10.1007/s10601-009-9076-1.
[15]	O. Günlük, J. Lee and R. Weismantel, MINLP strengthening for separable convex quadratic transportation-cost UFL, IBM Research Report, RC23771, 2007.
[16]	J. Lee and S. Leyffer, "Mixed Integer Nonlinear Programming," in "The IMA Volumes in Mathematics and its Applications," Springer, 154 (2012).
[17]	Y. Lin and L. Schrage, The global solver in the LINDO API, Optim. Methods Softw., 24 (2009), 657-668.doi: 10.1080/10556780902753221.
[18]	G. P. McCormick, Computability of global solutions to factorable nonconvex programs: Part I-Convex underestimating problems, Math. Program., 10 (1976), 147-175.doi: 10.1007/BF01580665.
[19]	R. Misener and C. A. Floudas, GloMIQO: Global mixed-integer quadratic optimizer, J. Glob. Optim., to appear.
[20]	H. Mittelmann, "MIQP Test Instances," http://plato.asu.edu/ftp/miqp.html.
[21]	N. Sawaya, "Reformulations, Relaxations and Cutting Planes for Generalized Disjunctive Programming," PhD thesis, Carnegie Mellon University, 2006.
[22]	J. P. M. Silva and K. A. Sakallah, GRASP - A new search algorithm for satisfiability, in "ICCAD'96: Proceedings of the 1996 IEEE/ACM international conference on Computer-aided design," IEEE Computer Society, Washington, DC, USA, 1996, 220-227.
[23]	M. Tawarmalani and N. V. Sahinidis, "Convexification and Global Optimization in Continuous and Mixed-Integer Nonlinear Programming: Theory, Algorithms, Software, and Applications," Kluwer Academic Publishers, 2002.
[24]	S. Vigerske, "Decomposition of Multistage Stochastic Programs and a Constraint Integer Programming Approach to Mixed-Integer Nonlinear Programming," PhD thesis, Humboldt-Universität zu Berlin, 2012, to be published.
[25]	J. P. Vielma, S. Ahmed and G. L. Nemhauser, A lifted linear programming branch-and-bound algorithm for mixed-integer conic quadratic programs, INFORMS J. Comput., 20 (2008), 438-450.doi: 10.1287/ijoc.1070.0256.
[26]	A. Wächter and L. T. Biegler, On the implementation of a primal-dual interior point filter line search algorithm for large-scale nonlinear programming, Math. Program., 106 (2006), 25-57.doi: 10.1007/s10107-004-0559-y.
[27]	K. Wolter, "Implementation of Cutting Plane Separators for Mixed Integer Programs," Master's thesis, Technische Universitt Berlin, 2006.
[28]	T. Yunes, I. D. Aron and J. N. Hooker, An integrated solver for optimization problems, Oper. Res., 58 (2010), 342-356.doi: 10.1287/opre.1090.0733.
[29]	IBM, "CPLEX," http://ibm.com/software/integration/optimization/cplex.