2012, 2(4): 739-748. doi: 10.3934/naco.2012.2.739

Analyzing the computational impact of MIQCP solver components

1. 

Zuse Institute Berlin, Takustr. 7, 14195 Berlin, Germany, Germany, Germany

2. 

Humboldt-Universität, Department of Mathematics, Unter den Linden 6, 10099 Berlin

Received  May 2012 Revised  October 2012 Published  November 2012

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.
Citation: Timo Berthold, Ambros M. Gleixner, Stefan Heinz, Stefan Vigerske. Analyzing the computational impact of MIQCP solver components. Numerical Algebra, Control & Optimization, 2012, 2 (4) : 739-748. doi: 10.3934/naco.2012.2.739
References:
[1]

T. Achterberg, "Constraint Integer Programming,", PhD thesis, (2007).   Google Scholar

[2]

T. Achterberg and T. Berthold, Hybrid branching,, in, 5547 (2009), 309.   Google Scholar

[3]

T. Achterberg, T. Berthold, T. Koch and K. Wolter, Constraint integer programming: A new approach to integrate CP and MIP,, in, 5015 (2008), 6.   Google Scholar

[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.  doi: 10.1287/ijoc.1090.0373.  Google Scholar

[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.  doi: 10.1080/10556780903087124.  Google Scholar

[6]

T. Berthold, "Primal Heuristics for Mixed Integer Programs,", Master's thesis, (2006).   Google Scholar

[7]

T. Berthold and A. M. Gleixner, Undercover - a primal MINLP heuristic exploring a largest sub-MIP,, ZIB-Report 12-07, (2012), 12.   Google Scholar

[8]

T. Berthold, S. Heinz, M. E. Pfetsch and S. Vigerske, Large neighborhood search beyond MIP,, in, (2011), 51.   Google Scholar

[9]

T. Berthold, S. Heinz and S. Vigerske, Extending a CIP framework to solve MIQCPs,, in Lee and Leyffer [16], (): 427.   Google Scholar

[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.  doi: 10.1016/j.disopt.2006.10.011.  Google Scholar

[11]

P. Bonami, M. Kilinç and J. Linderoth, Algorithms and software for convex mixed integer nonlinear programs,, in Lee and Leyffer [16], (): 1.   Google Scholar

[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.  doi: 10.1287/ijoc.15.1.114.15159.  Google Scholar

[13]

M. R. Bussieck and S. Vigerske, MINLP solver software,, in, (2010).   Google Scholar

[14]

F. Domes and A. Neumaier, Constraint propagation on quadratic constraints,, Constraints, 15 (2010), 404.  doi: 10.1007/s10601-009-9076-1.  Google Scholar

[15]

O. Günlük, J. Lee and R. Weismantel, MINLP strengthening for separable convex quadratic transportation-cost UFL,, IBM Research Report, (2007).   Google Scholar

[16]

J. Lee and S. Leyffer, "Mixed Integer Nonlinear Programming,", in, 154 (2012).   Google Scholar

[17]

Y. Lin and L. Schrage, The global solver in the LINDO API,, Optim. Methods Softw., 24 (2009), 657.  doi: 10.1080/10556780902753221.  Google Scholar

[18]

G. P. McCormick, Computability of global solutions to factorable nonconvex programs: Part I-Convex underestimating problems,, Math. Program., 10 (1976), 147.  doi: 10.1007/BF01580665.  Google Scholar

[19]

R. Misener and C. A. Floudas, GloMIQO: Global mixed-integer quadratic optimizer,, J. Glob. Optim., ().   Google Scholar

[20]

H. Mittelmann, "MIQP Test Instances,", , ().   Google Scholar

[21]

N. Sawaya, "Reformulations, Relaxations and Cutting Planes for Generalized Disjunctive Programming,", PhD thesis, (2006).   Google Scholar

[22]

J. P. M. Silva and K. A. Sakallah, GRASP - A new search algorithm for satisfiability,, in, (1996), 220.   Google Scholar

[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).   Google Scholar

[24]

S. Vigerske, "Decomposition of Multistage Stochastic Programs and a Constraint Integer Programming Approach to Mixed-Integer Nonlinear Programming,", PhD thesis, (2012).   Google Scholar

[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.  doi: 10.1287/ijoc.1070.0256.  Google Scholar

[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.  doi: 10.1007/s10107-004-0559-y.  Google Scholar

[27]

K. Wolter, "Implementation of Cutting Plane Separators for Mixed Integer Programs,", Master's thesis, (2006).   Google Scholar

[28]

T. Yunes, I. D. Aron and J. N. Hooker, An integrated solver for optimization problems,, Oper. Res., 58 (2010), 342.  doi: 10.1287/opre.1090.0733.  Google Scholar

[29]

IBM, "CPLEX,", , ().   Google Scholar

show all references

References:
[1]

T. Achterberg, "Constraint Integer Programming,", PhD thesis, (2007).   Google Scholar

[2]

T. Achterberg and T. Berthold, Hybrid branching,, in, 5547 (2009), 309.   Google Scholar

[3]

T. Achterberg, T. Berthold, T. Koch and K. Wolter, Constraint integer programming: A new approach to integrate CP and MIP,, in, 5015 (2008), 6.   Google Scholar

[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.  doi: 10.1287/ijoc.1090.0373.  Google Scholar

[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.  doi: 10.1080/10556780903087124.  Google Scholar

[6]

T. Berthold, "Primal Heuristics for Mixed Integer Programs,", Master's thesis, (2006).   Google Scholar

[7]

T. Berthold and A. M. Gleixner, Undercover - a primal MINLP heuristic exploring a largest sub-MIP,, ZIB-Report 12-07, (2012), 12.   Google Scholar

[8]

T. Berthold, S. Heinz, M. E. Pfetsch and S. Vigerske, Large neighborhood search beyond MIP,, in, (2011), 51.   Google Scholar

[9]

T. Berthold, S. Heinz and S. Vigerske, Extending a CIP framework to solve MIQCPs,, in Lee and Leyffer [16], (): 427.   Google Scholar

[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.  doi: 10.1016/j.disopt.2006.10.011.  Google Scholar

[11]

P. Bonami, M. Kilinç and J. Linderoth, Algorithms and software for convex mixed integer nonlinear programs,, in Lee and Leyffer [16], (): 1.   Google Scholar

[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.  doi: 10.1287/ijoc.15.1.114.15159.  Google Scholar

[13]

M. R. Bussieck and S. Vigerske, MINLP solver software,, in, (2010).   Google Scholar

[14]

F. Domes and A. Neumaier, Constraint propagation on quadratic constraints,, Constraints, 15 (2010), 404.  doi: 10.1007/s10601-009-9076-1.  Google Scholar

[15]

O. Günlük, J. Lee and R. Weismantel, MINLP strengthening for separable convex quadratic transportation-cost UFL,, IBM Research Report, (2007).   Google Scholar

[16]

J. Lee and S. Leyffer, "Mixed Integer Nonlinear Programming,", in, 154 (2012).   Google Scholar

[17]

Y. Lin and L. Schrage, The global solver in the LINDO API,, Optim. Methods Softw., 24 (2009), 657.  doi: 10.1080/10556780902753221.  Google Scholar

[18]

G. P. McCormick, Computability of global solutions to factorable nonconvex programs: Part I-Convex underestimating problems,, Math. Program., 10 (1976), 147.  doi: 10.1007/BF01580665.  Google Scholar

[19]

R. Misener and C. A. Floudas, GloMIQO: Global mixed-integer quadratic optimizer,, J. Glob. Optim., ().   Google Scholar

[20]

H. Mittelmann, "MIQP Test Instances,", , ().   Google Scholar

[21]

N. Sawaya, "Reformulations, Relaxations and Cutting Planes for Generalized Disjunctive Programming,", PhD thesis, (2006).   Google Scholar

[22]

J. P. M. Silva and K. A. Sakallah, GRASP - A new search algorithm for satisfiability,, in, (1996), 220.   Google Scholar

[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).   Google Scholar

[24]

S. Vigerske, "Decomposition of Multistage Stochastic Programs and a Constraint Integer Programming Approach to Mixed-Integer Nonlinear Programming,", PhD thesis, (2012).   Google Scholar

[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.  doi: 10.1287/ijoc.1070.0256.  Google Scholar

[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.  doi: 10.1007/s10107-004-0559-y.  Google Scholar

[27]

K. Wolter, "Implementation of Cutting Plane Separators for Mixed Integer Programs,", Master's thesis, (2006).   Google Scholar

[28]

T. Yunes, I. D. Aron and J. N. Hooker, An integrated solver for optimization problems,, Oper. Res., 58 (2010), 342.  doi: 10.1287/opre.1090.0733.  Google Scholar

[29]

IBM, "CPLEX,", , ().   Google Scholar

[1]

Yasmine Cherfaoui, Mustapha Moulaï. Biobjective optimization over the efficient set of multiobjective integer programming problem. Journal of Industrial & Management Optimization, 2021, 17 (1) : 117-131. doi: 10.3934/jimo.2019102

[2]

Mahdi Karimi, Seyed Jafar Sadjadi. Optimization of a Multi-Item Inventory model for deteriorating items with capacity constraint using dynamic programming. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2021013

[3]

Ahmad Z. Fino, Wenhui Chen. A global existence result for two-dimensional semilinear strongly damped wave equation with mixed nonlinearity in an exterior domain. Communications on Pure & Applied Analysis, 2020, 19 (12) : 5387-5411. doi: 10.3934/cpaa.2020243

[4]

Liping Tang, Ying Gao. Some properties of nonconvex oriented distance function and applications to vector optimization problems. Journal of Industrial & Management Optimization, 2021, 17 (1) : 485-500. doi: 10.3934/jimo.2020117

[5]

Hui Gao, Jian Lv, Xiaoliang Wang, Liping Pang. An alternating linearization bundle method for a class of nonconvex optimization problem with inexact information. Journal of Industrial & Management Optimization, 2021, 17 (2) : 805-825. doi: 10.3934/jimo.2019135

[6]

Yahia Zare Mehrjerdi. A new methodology for solving bi-criterion fractional stochastic programming. Numerical Algebra, Control & Optimization, 2020  doi: 10.3934/naco.2020054

[7]

Pablo Neme, Jorge Oviedo. A note on the lattice structure for matching markets via linear programming. Journal of Dynamics & Games, 2020  doi: 10.3934/jdg.2021001

[8]

Ke Su, Yumeng Lin, Chun Xu. A new adaptive method to nonlinear semi-infinite programming. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2021012

[9]

Tengfei Yan, Qunying Liu, Bowen Dou, Qing Li, Bowen Li. An adaptive dynamic programming method for torque ripple minimization of PMSM. Journal of Industrial & Management Optimization, 2021, 17 (2) : 827-839. doi: 10.3934/jimo.2019136

[10]

Huiying Fan, Tao Ma. Parabolic equations involving Laguerre operators and weighted mixed-norm estimates. Communications on Pure & Applied Analysis, 2020, 19 (12) : 5487-5508. doi: 10.3934/cpaa.2020249

[11]

Jie Zhang, Yuping Duan, Yue Lu, Michael K. Ng, Huibin Chang. Bilinear constraint based ADMM for mixed Poisson-Gaussian noise removal. Inverse Problems & Imaging, , () : -. doi: 10.3934/ipi.2020071

[12]

Ferenc Weisz. Dual spaces of mixed-norm martingale hardy spaces. Communications on Pure & Applied Analysis, , () : -. doi: 10.3934/cpaa.2020285

[13]

Jianli Xiang, Guozheng Yan. The uniqueness of the inverse elastic wave scattering problem based on the mixed reciprocity relation. Inverse Problems & Imaging, , () : -. doi: 10.3934/ipi.2021004

[14]

Riadh Chteoui, Abdulrahman F. Aljohani, Anouar Ben Mabrouk. Classification and simulation of chaotic behaviour of the solutions of a mixed nonlinear Schrödinger system. Electronic Research Archive, , () : -. doi: 10.3934/era.2021002

[15]

Juan Pablo Pinasco, Mauro Rodriguez Cartabia, Nicolas Saintier. Evolutionary game theory in mixed strategies: From microscopic interactions to kinetic equations. Kinetic & Related Models, 2021, 14 (1) : 115-148. doi: 10.3934/krm.2020051

[16]

Ali Mahmoodirad, Harish Garg, Sadegh Niroomand. Solving fuzzy linear fractional set covering problem by a goal programming based solution approach. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2020162

[17]

C. J. Price. A modified Nelder-Mead barrier method for constrained optimization. Numerical Algebra, Control & Optimization, 2020  doi: 10.3934/naco.2020058

[18]

Touria Karite, Ali Boutoulout. Global and regional constrained controllability for distributed parabolic linear systems: RHUM approach. Numerical Algebra, Control & Optimization, 2020  doi: 10.3934/naco.2020055

[19]

Shenglan Xie, Maoan Han, Peng Zhu. A posteriori error estimate of weak Galerkin fem for second order elliptic problem with mixed boundary condition. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020340

[20]

Ying Liu, Yanping Chen, Yunqing Huang, Yang Wang. Two-grid method for semiconductor device problem by mixed finite element method and characteristics finite element method. Electronic Research Archive, 2021, 29 (1) : 1859-1880. doi: 10.3934/era.2020095

 Impact Factor: 

Metrics

  • PDF downloads (54)
  • HTML views (0)
  • Cited by (12)

[Back to Top]