Extending a CIP framework to solve MIQCPs

Please always quote using this URN: urn:nbn:de:0297-zib-11371
  • 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 MIP and CP technologies. In particular, this addresses the linear relaxation and the discrete components of the problem. For relaxation, we use an outer approximation generated by linearization of convex constraints and linear underestimation of nonconvex constraints. 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 indicates the potential of the approach.

Download full text files

Export metadata

  • Export Bibtex

Additional Services

Share in Twitter Search Google Scholar
Metadaten
Author:Timo Berthold, Stefan Heinz, Stefan Vigerske
Document Type:ZIB-Report
Tag:constraint integer programming ; convex relaxation ; mixed integer quadratically constrained programming ; nonconvex
MSC-Classification:90-XX OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING / 90Cxx Mathematical programming [See also 49Mxx, 65Kxx] / 90C11 Mixed integer programming
90-XX OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING / 90Cxx Mathematical programming [See also 49Mxx, 65Kxx] / 90C20 Quadratic programming
90-XX OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING / 90Cxx Mathematical programming [See also 49Mxx, 65Kxx] / 90C26 Nonconvex programming, global optimization
90-XX OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING / 90Cxx Mathematical programming [See also 49Mxx, 65Kxx] / 90C27 Combinatorial optimization
90-XX OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING / 90Cxx Mathematical programming [See also 49Mxx, 65Kxx] / 90C57 Polyhedral combinatorics, branch-and-bound, branch-and-cut
Date of first Publication:2009/07/09
Series (Serial Number):ZIB-Report (09-23)
ISSN:1438-0064
Published in:App. in: Mixed Integer Nonlinear Programming. Jon Lee, Sven Leyffer (eds.) The IMA Volumes in Mathematics and its Applications, 154. Springer 2011, pp. 427-444

$Rev: 13581 $