Document Open Access Logo

An Adaptive Refinement Algorithm for Discretizations of Nonconvex QCQP

Authors Akshay Gupte , Arie M. C. A. Koster , Sascha Kuhnke

PDF
Thumbnail PDF

File

LIPIcs.SEA.2022.24.pdf
  • Filesize: 1.33 MB
  • 14 pages

Document Identifiers

Author Details

Akshay Gupte
  • School of Mathematics, The University of Edinburgh, UK
Arie M. C. A. Koster
  • Lehrstuhl II für Mathematik, RWTH Aachen University, Germany
Sascha Kuhnke
  • Lehrstuhl II für Mathematik, RWTH Aachen University, Germany

Funding

The second and third authors' visit was supported by a grant from DAAD, the German Academic Exchange Service.
  • Gupte, Akshay: Initial phase of this research supported by NSF grant DMS-1913294.

Acknowledgements

This research was initiated during the second and third authors' visit to Clemson University, USA, in 2019, where the first author was a faculty member.

Cite As Get BibTex

Akshay Gupte, Arie M. C. A. Koster, and Sascha Kuhnke. An Adaptive Refinement Algorithm for Discretizations of Nonconvex QCQP. In 20th International Symposium on Experimental Algorithms (SEA 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 233, pp. 24:1-24:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022) https://doi.org/10.4230/LIPIcs.SEA.2022.24

Abstract

We present an iterative algorithm to compute feasible solutions in reasonable running time to quadratically constrained quadratic programs (QCQPs), which form a challenging class of nonconvex continuous optimization. This algorithm is based on a mixed-integer linear program (MILP) which is a restriction of the original QCQP obtained by discretizing all quadratic terms. In each iteration, this MILP restriction is solved to get a feasible QCQP solution. Since the quality of this solution heavily depends on the chosen discretization of the MILP, we iteratively adapt the discretization values based on the MILP solution of the previous iteration. To maintain a reasonable problem size in each iteration of the algorithm, the discretization sizes are fixed at predefined values. Although our algorithm did not always yield good feasible solutions on arbitrary QCQP instances, an extensive computational study on almost 1300 test instances of two different problem classes - box-constrained quadratic programs with complementarity constraints and disjoint bilinear programs, demonstrates the effectiveness of our approach. We compare the quality of our solutions against those from heuristics and local optimization algorithms in two state-of-the-art commercial solvers and observe that on one instance class we clearly outperform the other methods whereas on the other class we obtain competitive results.

Subject Classification

ACM Subject Classification
  • Theory of computation → Mixed discrete-continuous optimization
  • Mathematics of computing → Nonconvex optimization
Keywords
  • Quadratically Constrained Quadratic Programs
  • Mixed Integer Linear Programming
  • Heuristics
  • BoxQP
  • Disjoint Bilinear

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Supplementary Materials

References

  1. Mohammed Alfaki and Dag Haugland. Comparison of discrete and continuous models for the pooling problem. In Alberto Caprara and Spyros Kontogiannis, editors, 11th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems, volume 20 of OpenAccess Series in Informatics (OASIcs), pages 112-121, 2011. URL: https://doi.org/10.4230/OASIcs.ATMOS.2011.112.
  2. Timo Berthold. RENS. Mathematical Programming Computation, 6(1):33-54, 2014. URL: https://doi.org/10.1007/s12532-013-0060-9.
  3. Timo Berthold and Ambros M Gleixner. Undercover: a primal MINLP heuristic exploring a largest sub-MIP. Mathematical Programming, 144(1-2):315-346, 2014. URL: https://doi.org/10.1007/s10107-013-0635-2.
  4. Endre Boros, Peter L Hammer, and Gabriel Tavares. Local search heuristics for quadratic unconstrained binary optimization (QUBO). Journal of Heuristics, 13(2):99-132, 2007. Google Scholar
  5. Samuel Burer and Anureet Saxena. The MILP road to MIQCP. In Jon Lee and Sven Leyffer, editors, Mixed Integer Nonlinear Programming, volume 154 of IMA Volumes in Mathematics and its Applications, pages 373-405. Springer, 2012. Google Scholar
  6. Robert Burlacu, Björn Geißler, and Lars Schewe. Solving mixed-integer nonlinear programmes using adaptively refined mixed-integer linear programmes. Optimization Methods and Software, 35(1):37-64, 2020. Google Scholar
  7. C. D'Ambrosio, A. Frangioni, L. Liberti, and A. Lodi. Experiments with a feasibility pump approach for nonconvex MINLPs. In P. Festa, editor, Experimental Algorithms, volume 6049 of Lecture Notes in Computer Science, pages 350-360. Springer, Berlin, Heidelberg, 2010. URL: https://doi.org/10.1007/978-3-642-13193-6_30.
  8. Claudia D'Ambrosio, Antonio Frangioni, Leo Liberti, and Andrea Lodi. A storm of feasibility pumps for nonconvex MINLP. Mathematical Programming, 136(2):375-402, 2012. URL: https://doi.org/10.1007/s10107-012-0608-x.
  9. Sanjeeb Dash, Oktay Günlük, and Robert Hildebrand. Binary extended formulations of polyhedral mixed-integer sets. Mathematical Programming, 170(1):207-236, 2018. URL: https://doi.org/10.1007/s10107-018-1294-0.
  10. Santanu S Dey and Akshay Gupte. Analysis of MILP techniques for the pooling problem. Operations Research, 63(2):412-427, 2015. URL: https://doi.org/10.1287/opre.2015.1357.
  11. Fabio Furini, Emiliano Traversi, Pietro Belotti, Antonio Frangioni, Ambros Gleixner, Nick Gould, Leo Liberti, Andrea Lodi, Ruth Misener, Hans Mittelmann, et al. QPLIB: a library of quadratic programming instances. Mathematical Programming Computation, 11(2):237-265, 2019. Google Scholar
  12. Laura Galli and Adam N Letchford. A binarisation heuristic for non-convex quadratic programming with box constraints. Operations Research Letters, 46(5):529-533, 2018. Google Scholar
  13. S. Goderbauer, B. Bahl, P. Voll, M.E. Luebbecke, A. Bardow, and A.M.C.A. Koster. An adaptive discretization MINLP algorithm for optimal synthesis of decentralized energy supply systems. Computers & Chemical Engineering, 95:38-48, 2016. URL: https://doi.org/10.1016/j.compchemeng.2016.09.008.
  14. Akshay Gupte, Shabbir Ahmed, Myun S. Cheon, and Santanu S Dey. Solving mixed integer bilinear problems using MILP formulations. SIAM Journal on Optimization, 23(2):721-744, 2013. URL: https://doi.org/10.1137/110836183.
  15. Akshay Gupte, Shabbir Ahmed, Santanu S. Dey, and Myun Seok Cheon. Relaxations and discretizations for the pooling problem. Journal of Global Optimization, 67(3):631-669, 2017. URL: https://doi.org/10.1007/s10898-016-0434-4.
  16. Scott P Kolodziej, Ignacio E Grossmann, Kevin C Furman, and Nicolas W Sawaya. A discretization-based approach for the optimization of the multiperiod blend scheduling problem. Computers & Chemical Engineering, 53:122-142, 2013. Google Scholar
  17. Arie M. C. A. Koster and Sascha Kuhnke. An adaptive discretization algorithm for the design of water usage and treatment networks. Optimization and Engineering, 20(2):497-542, June 2019. URL: https://doi.org/10.1007/s11081-018-9413-6.
  18. Leo Liberti, Nenad Mladenović, and Giacomo Nannicini. A recipe for finding good solutions to MINLPs. Mathematical Programming Computation, 3(4):349-390, 2011. URL: https://doi.org/10.1007/s12532-011-0031-y.
  19. Harsha Nagarajan, Mowen Lu, Site Wang, Russell Bent, and Kaarthik Sundar. An adaptive, multivariate partitioning algorithm for global optimization of nonconvex programs. Journal of Global Optimization, 74(4):639-675, 2019. Google Scholar
  20. Giacomo Nannicini and Pietro Belotti. Rounding-based heuristics for nonconvex MINLPs. Mathematical Programming Computation, 4(1):1-31, 2012. URL: https://doi.org/10.1007/s12532-011-0032-x.
  21. Carlos J Nohra, Arvind U Raghunathan, and Nikolaos Sahinidis. Spectral relaxations and branching strategies for global optimization of mixed-integer quadratic programs. SIAM Journal on Optimization, 31(1):142-171, 2021. Google Scholar
  22. Foad Mahdavi Pajouh, Balabhaskar Balasundaram, and Oleg A Prokopyev. On characterization of maximal independent sets via quadratic optimization. Journal of Heuristics, 19(4):629-644, 2013. URL: https://doi.org/10.1007/s10732-011-9171-5.
  23. Jaehyun Park and Stephen Boyd. General heuristics for nonconvex quadratically constrained quadratic programming. arXiv Preprint, May 2017. URL: http://arxiv.org/abs/1703.07870.
  24. V. Pham, C. Laird, and M. El-Halwagi. Convex hull discretization approach to the global optimization of pooling problems. Industrial and Engineering Chemistry Research, 48(4):1973-1979, 2009. Google Scholar
  25. Wim van Ackooij, Welington de Oliveira, and Yongjia Song. Adaptive partition-based level decomposition methods for solving two-stage stochastic programs with fixed recourse. INFORMS Journal on Computing, 30(1):57-70, 2018. URL: https://doi.org/10.1287/ijoc.2017.0765.
  26. Luis N Vicente, Paul H Calamai, and Joaquim J Júdice. Generation of disjointly constrained bilinear programming test problems. Computational Optimization and Applications, 1(3):299-306, 1992. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact