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 and Optimization, 2012, 2 (4) : 739-748. doi: 10.3934/naco.2012.2.739
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. 

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

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

[20]

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

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

show all references

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. 

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

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

[20]

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

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

[1]

René Henrion, Christian Küchler, Werner Römisch. Discrepancy distances and scenario reduction in two-stage stochastic mixed-integer programming. Journal of Industrial and 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 and 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 and 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 and 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 and 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 and Heterogeneous Media, 2013, 8 (3) : 783-802. doi: 10.3934/nhm.2013.8.783

[7]

Mahdi Roozbeh, Saman Babaie–Kafaki, Zohre Aminifard. Two penalized mixed–integer nonlinear programming approaches to tackle multicollinearity and outliers effects in linear regression models. Journal of Industrial and Management Optimization, 2021, 17 (6) : 3475-3491. doi: 10.3934/jimo.2020128

[8]

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

[9]

Fanwen Meng, Kiok Liang Teow, Kelvin Wee Sheng Teo, Chee Kheong Ooi, Seow Yian Tay. Predicting 72-hour reattendance in emergency departments using discriminant analysis via mixed integer programming with electronic medical records. Journal of Industrial and Management Optimization, 2019, 15 (2) : 947-962. doi: 10.3934/jimo.2018079

[10]

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 and Management Optimization, 2016, 12 (2) : 431-447. doi: 10.3934/jimo.2016.12.431

[11]

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

[12]

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

[13]

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

[14]

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

[15]

Xiaojin Zheng, Zhongyi Jiang. Tighter quadratically constrained convex reformulations for semi-continuous quadratic programming. Journal of Industrial and Management Optimization, 2021, 17 (5) : 2331-2343. doi: 10.3934/jimo.2020071

[16]

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

[17]

Zhimin Liu, Shaojian Qu, Hassan Raza, Zhong Wu, Deqiang Qu, Jianhui Du. Two-stage mean-risk stochastic mixed integer optimization model for location-allocation problems under uncertain environment. Journal of Industrial and Management Optimization, 2021, 17 (5) : 2783-2804. doi: 10.3934/jimo.2020094

[18]

Meijuan Shang, Yanan Liu, Lingchen Kong, Xianchao Xiu, Ying Yang. Nonconvex mixed matrix minimization. Mathematical Foundations of Computing, 2019, 2 (2) : 107-126. doi: 10.3934/mfc.2019009

[19]

Mahmoud Ameri, Armin Jarrahi. An executive model for network-level pavement maintenance and rehabilitation planning based on linear integer programming. Journal of Industrial and Management Optimization, 2020, 16 (2) : 795-811. doi: 10.3934/jimo.2018179

[20]

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

 Impact Factor: 

Metrics

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

[Back to Top]