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).

[2]

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

[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.

[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.

[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.

[6]

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

[7]

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

[8]

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

[9]

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

[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.

[11]

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

[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.

[13]

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

[14]

F. Domes and A. Neumaier, Constraint propagation on quadratic constraints,, Constraints, 15 (2010), 404. 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, (2007).

[16]

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

[17]

Y. Lin and L. Schrage, The global solver in the LINDO API,, Optim. Methods Softw., 24 (2009), 657. 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. doi: 10.1007/BF01580665.

[19]

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

[20]

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

[21]

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

[22]

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

[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, (2012).

[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.

[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.

[27]

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

[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.

[29]

IBM, "CPLEX,", , ().

show all references

References:
[1]

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

[2]

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

[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.

[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.

[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.

[6]

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

[7]

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

[8]

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

[9]

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

[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.

[11]

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

[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.

[13]

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

[14]

F. Domes and A. Neumaier, Constraint propagation on quadratic constraints,, Constraints, 15 (2010), 404. 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, (2007).

[16]

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

[17]

Y. Lin and L. Schrage, The global solver in the LINDO API,, Optim. Methods Softw., 24 (2009), 657. 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. doi: 10.1007/BF01580665.

[19]

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

[20]

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

[21]

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

[22]

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

[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, (2012).

[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.

[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.

[27]

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

[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.

[29]

IBM, "CPLEX,", , ().

[1]

René Henrion, Christian Küchler, Werner Römisch. Discrepancy distances and scenario reduction in two-stage stochastic mixed-integer programming. Journal of Industrial & Management Optimization, 2008, 4 (2) : 363-384. doi: 10.3934/jimo.2008.4.363

[2]

Elham Mardaneh, Ryan Loxton, Qun Lin, Phil Schmidli. A mixed-integer linear programming model for optimal vessel scheduling in offshore oil and gas operations. Journal of Industrial & Management Optimization, 2017, 13 (4) : 1601-1623. doi: 10.3934/jimo.2017009

[3]

Ye Tian, Cheng Lu. Nonconvex quadratic reformulations and solvable conditions for mixed integer quadratic programming problems. Journal of Industrial & Management Optimization, 2011, 7 (4) : 1027-1039. doi: 10.3934/jimo.2011.7.1027

[4]

Yongjian Yang, Zhiyou Wu, Fusheng Bai. A filled function method for constrained nonlinear integer programming. Journal of Industrial & Management Optimization, 2008, 4 (2) : 353-362. doi: 10.3934/jimo.2008.4.353

[5]

Louis Caccetta, Syarifah Z. Nordin. Mixed integer programming model for scheduling in unrelated parallel processor system with priority consideration. Numerical Algebra, Control & Optimization, 2014, 4 (2) : 115-132. doi: 10.3934/naco.2014.4.115

[6]

Edward S. Canepa, Alexandre M. Bayen, Christian G. Claudel. Spoofing cyber attack detection in probe-based traffic monitoring systems using mixed integer linear programming. Networks & Heterogeneous Media, 2013, 8 (3) : 783-802. doi: 10.3934/nhm.2013.8.783

[7]

Zhiguo Feng, Ka-Fai Cedric Yiu. Manifold relaxations for integer programming. Journal of Industrial & Management Optimization, 2014, 10 (2) : 557-566. doi: 10.3934/jimo.2014.10.557

[8]

Wan Nor Ashikin Wan Ahmad Fatthi, Adibah Shuib, Rosma Mohd Dom. A mixed integer programming model for solving real-time truck-to-door assignment and scheduling problem at cross docking warehouse. Journal of Industrial & Management Optimization, 2016, 12 (2) : 431-447. doi: 10.3934/jimo.2016.12.431

[9]

Zhenbo Wang, Shu-Cherng Fang, David Y. Gao, Wenxun Xing. Global extremal conditions for multi-integer quadratic programming. Journal of Industrial & Management Optimization, 2008, 4 (2) : 213-225. doi: 10.3934/jimo.2008.4.213

[10]

Jing Quan, Zhiyou Wu, Guoquan Li. Global optimality conditions for some classes of polynomial integer programming problems. Journal of Industrial & Management Optimization, 2011, 7 (1) : 67-78. doi: 10.3934/jimo.2011.7.67

[11]

Ziye Shi, Qingwei Jin. Second order optimality conditions and reformulations for nonconvex quadratically constrained quadratic programming problems. Journal of Industrial & Management Optimization, 2014, 10 (3) : 871-882. doi: 10.3934/jimo.2014.10.871

[12]

Mohamed A. Tawhid, Ahmed F. Ali. A simplex grey wolf optimizer for solving integer programming and minimax problems. Numerical Algebra, Control & Optimization, 2017, 7 (3) : 301-323. doi: 10.3934/naco.2017020

[13]

Abdel-Rahman Hedar, Alaa Fahim. Filter-based genetic algorithm for mixed variable programming. Numerical Algebra, Control & Optimization, 2011, 1 (1) : 99-116. doi: 10.3934/naco.2011.1.99

[14]

Xinmin Yang, Xiaoqi Yang. A note on mixed type converse duality in multiobjective programming problems. Journal of Industrial & Management Optimization, 2010, 6 (3) : 497-500. doi: 10.3934/jimo.2010.6.497

[15]

Ardeshir Ahmadi, Hamed Davari-Ardakani. A multistage stochastic programming framework for cardinality constrained portfolio optimization. Numerical Algebra, Control & Optimization, 2017, 7 (3) : 359-377. doi: 10.3934/naco.2017023

[16]

Murat Adivar, Shu-Cherng Fang. Convex optimization on mixed domains. Journal of Industrial & Management Optimization, 2012, 8 (1) : 189-227. doi: 10.3934/jimo.2012.8.189

[17]

Paul B. Hermanns, Nguyen Van Thoai. Global optimization algorithm for solving bilevel programming problems with quadratic lower levels. Journal of Industrial & Management Optimization, 2010, 6 (1) : 177-196. doi: 10.3934/jimo.2010.6.177

[18]

Dan Xue, Wenyu Sun, Hongjin He. A structured trust region method for nonconvex programming with separable structure. Numerical Algebra, Control & Optimization, 2013, 3 (2) : 283-293. doi: 10.3934/naco.2013.3.283

[19]

Victor Gergel, Konstantin Barkalov, Alexander Sysoyev. Globalizer: A novel supercomputer software system for solving time-consuming global optimization problems. Numerical Algebra, Control & Optimization, 2018, 8 (1) : 47-62. doi: 10.3934/naco.2018003

[20]

Jayadev S. Athreya, Gregory A. Margulis. Values of random polynomials at integer points. Journal of Modern Dynamics, 2018, 12: 9-16. doi: 10.3934/jmd.2018002

 Impact Factor: 

Metrics

  • PDF downloads (1)
  • HTML views (0)
  • Cited by (7)

[Back to Top]