Advanced Search
Article Contents
Article Contents

Analyzing the computational impact of MIQCP solver components

Abstract Related Papers Cited by
  • 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.
    Mathematics Subject Classification: Primary: 90C11, Secondary: 90C26, 90C30.


    \begin{equation} \\ \end{equation}
  • [1]

    T. Achterberg, "Constraint Integer Programming," PhD thesis, Technische Universitt Berlin, 2007.


    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.


    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.


    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.


    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.


    T. Berthold, "Primal Heuristics for Mixed Integer Programs," Master's thesis, Technische Universitt Berlin, 2006.


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


    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.


    T. Berthold, S. Heinz and S. VigerskeExtending a CIP framework to solve MIQCPs, in Lee and Leyffer [16], 427-444.


    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.


    P. Bonami, M. Kilinç and J. LinderothAlgorithms and software for convex mixed integer nonlinear programs, in Lee and Leyffer [16], 1-40.


    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.


    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.


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


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


    J. Lee and S. Leyffer, "Mixed Integer Nonlinear Programming," in "The IMA Volumes in Mathematics and its Applications," Springer, 154 (2012).


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


    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.


    R. Misener and C. A. FloudasGloMIQO: Global mixed-integer quadratic optimizer, J. Glob. Optim., to appear.


    H. Mittelmann, "MIQP Test Instances," http://plato.asu.edu/ftp/miqp.html.


    N. Sawaya, "Reformulations, Relaxations and Cutting Planes for Generalized Disjunctive Programming," PhD thesis, Carnegie Mellon University, 2006.


    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.


    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.


    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.


    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.


    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.


    K. Wolter, "Implementation of Cutting Plane Separators for Mixed Integer Programs," Master's thesis, Technische Universitt Berlin, 2006.


    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.


    IBM, "CPLEX," http://ibm.com/software/integration/optimization/cplex.

  • 加载中

Article Metrics

HTML views() PDF downloads(131) Cited by(0)

Access History



    DownLoad:  Full-Size Img  PowerPoint