Abstract
This paper discusses how to build a solver for mixed integer quadratically constrained programs (MIQCPs) by extending a framework for constraint integer programming (CIP). The advantage of this approach is that we can utilize the full power of advanced MILP and CP technologies, in particular for the linear relaxation and the discrete components of the problem. We use an outer approximation generated by linearization of convex constraints and linear underestimation of nonconvex constraints to relax the problem. Further, we give an overview of the reformulation, separation, and propagation techniques that are used to handle the quadratic constraints efficiently. We implemented these methods in the branch-cut-and-price framework SCIP. Computational experiments indicating the potential of the approach and evaluating the impact of the algorithmic components are provided.
AMS(MOS) subject classifications. 90C11, 90C20, 90C26, 90C27, 90C57.
Supported by the DFG Research Center Matheon Mathematics for key technologies in Berlin, http://www.matheon.de.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Key words
References
K. Abhishek, S. Leyffer, and J. Linderoth, FilMINT: An outer-approximation-based solver for nonlinear mixed integer programs, INFORMS Journal on Computing, 22 (2010), pp. 555–567.
T. Achterberg, Constraint Integer Programming, PhD thesis, Technische Universit ¨at Berlin, 2007.
, SCIP: Solving Constraint Integer Programs, Math. Program. Comput.,1 (2009), pp. 1–41.
T. Achterberg, T. Berthold, T. Koch, and K. Wolter, Constraint integer programming: A new approach to integrate CP and MIP, in Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems, 5th International Conference, CPAIOR 2008, L. Perron and M. Trick, eds., Vol. 5015 of LNCS, Springer, 2008, pp. 6–20.
X. Bao, N. Sahinidis, and M. Tawarmalani, Multiterm polyhedral relaxations for nonconvex, quadratically-constrained quadratic programs, Optimization Methods and Software, 24 (2009), pp. 485–504.
P. Belotti, J. Lee, L. Liberti, F. Margot, and A. W¨achter, Branching and bounds tightening techniques for non-convex MINLP, Optimization Methods and Software, 24 (2009), pp. 597–634.
A. Ben-Tal and A. Nemirovski, On polyhedral approximations of the second- order cone, Math. Oper. Res., 26 (2001), pp. 193–205.
M. B´enichou, J. M. Gauthier, P. Girodet, G. Hentges, G. Ribi`ere, and O. Vincent, Experiments in mixed-integer linear programming, Math. Program., 1 (1971), pp. 76–94.
T. Berthold, Primal heuristics for mixed integer programs. Diploma thesis, Technische Universit¨at Berlin, 2006.
, RENS – relaxation enforced neighborhood search, ZIB-Report 07–28, Zuse Institute Berlin, 2007.
T. Berthold, S. Heinz, and M.E. Pfetsch, Nonlinear pseudo-boolean optimization: relaxation or propagation?, in Theory and Applications of Satisfiability Testing – SAT 2009, O. Kullmann, ed., no. 5584 in LNCS, Springer, 2009, pp. 441–446.
R.E. Bixby, M. Fenelon, Z. Gu, E. Rothberg, and R. Wunderling, MIP: theory and practice – closing the gap, in System Modelling and Optimization: Methods, Theory and Applications, M. Powell and S. Scholtes, eds., Kluwer, 2000, pp. 19–50.
P. Bonami, L.T. Biegler, A.R. Conn, G. Cornu´ejols, I.E. Grossmann, C.D. Laird, J. Lee, A. Lodi, F. Margot, N.W. Sawaya, and A. W¨achter, An algorithmic framework for convex mixed integer nonlinear programs, Discrete Optim., 5 (2008), pp. 186–204.
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), pp. 114–119.
CMU-IBM MINLP Project. http://egon.cheme.cmu.edu/ibm/page.htm.
F. Domes and A. Neumaier, Quadratic constraint propagation, Constraints, 15 (2010), pp. 404–429.
J.N. Hooker, Integrated Methods for Optimization, International Series in Operations Research & Management Science, Springer, New York, 2007.
R. Horst and H. Tuy, Global Optimization: Deterministic Approaches, Springer, 1990.
IBM, CPLEX. http://ibm.com/software/integration/optimization/cplex.
Y. Lin and L. Schrage, The global solver in the LINDO API, Optimization Methods and Software, 24 (2009), pp. 657–668.
G. McCormick, Computability of global solutions to factorable nonconvex programs: Part I-Convex Underestimating Problems, Math. Program., 10 (1976), pp. 147–175.
H. Mittelmann, MIQP test instances. http://plato.asu.edu/ftp/miqp.html.
MOSEK Corporation, The MOSEK optimization tools manual, 6.0 ed., 2009.
A. Saxena, P. Bonami, and J. Lee, Convex relaxations of non-convex mixed integer quadratically constrained programs: Projected formulations, Tech. Rep. RC24695, IBM Research, 2008. to appear in Math. Program.
M. Tawarmalani, J.-P.P. Richard, and K. Chung, Strong valid inequalities for orthogonal disjunctions and bilinear covering sets, Math. Program., 124 (2010), pp. 481–512.
M. Tawarmalani and N. Sahinidis, Convexification and Global Optimization in Continuous and Mixed-Integer Nonlinear Programming: Theory, Algorithms, Software, and Applications, Kluwer Academic Publishers, 2002.
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), pp. 438–450.
A. W¨achter 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), pp. 25–57.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2012 Springer Science+Business Media, LLC
About this paper
Cite this paper
Berthold, T., Heinz, S., Vigerske, S. (2012). Extending a CIP Framework to Solve MIQCPs . In: Lee, J., Leyffer, S. (eds) Mixed Integer Nonlinear Programming. The IMA Volumes in Mathematics and its Applications, vol 154. Springer, New York, NY. https://doi.org/10.1007/978-1-4614-1927-3_15
Download citation
DOI: https://doi.org/10.1007/978-1-4614-1927-3_15
Published:
Publisher Name: Springer, New York, NY
Print ISBN: 978-1-4614-1926-6
Online ISBN: 978-1-4614-1927-3
eBook Packages: Mathematics and StatisticsMathematics and Statistics (R0)