\`x^2+y_1+z_12^34\`
Advanced Search
Article Contents
Article Contents

Analyzing the computational impact of MIQCP solver components

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

    Citation:

    \begin{equation} \\ \end{equation}
  • [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. VigerskeExtending 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. LinderothAlgorithms 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. FloudasGloMIQO: 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.

  • 加载中
SHARE

Article Metrics

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

Access History

Catalog

    /

    DownLoad:  Full-Size Img  PowerPoint
    Return
    Return