Enhancements of discretization approaches for non-convex mixed-integer quadratically constrained quadratic programming: Part I

Beach B, Burlacu R, Bärmann A, Hager L, Hildebrand R (2024)

Publication Type: Journal article

Publication year: 2024

Journal

Computational Optimization and Applications Springer Verlag (Germany)

DOI: 10.1007/s10589-023-00543-7

Abstract

We study mixed-integer programming (MIP) relaxation techniques for the solution of non-convex mixed-integer quadratically constrained quadratic programs (MIQCQPs). We present MIP relaxation methods for non-convex continuous variable products. In this paper, we consider MIP relaxations based on separable reformulation. The main focus is the introduction of the enhanced separable MIP relaxation for non-convex quadratic products of the form z= xy , called hybrid separable (HybS). Additionally, we introduce a logarithmic MIP relaxation for univariate quadratic terms, called sawtooth relaxation, based on Beach (Beach in J Glob Optim 84:869–912, 2022). We combine the latter with HybS and existing separable reformulations to derive MIP relaxations of MIQCQPs. We provide a comprehensive theoretical analysis of these techniques, underlining the theoretical advantages of HybS compared to its predecessors. We perform a broad computational study to demonstrate the effectiveness of the enhanced MIP relaxation in terms of producing tight dual bounds for MIQCQPs. In Part II, we study MIP relaxations that extend the MIP relaxation normalized multiparametric disaggregation technique (NMDT) (Castro in J Glob Optim 64:765–784, 2015) and present a computational study which also includes the MIP relaxations from this work and compares them with a state-of-the-art of MIQCQP solvers.

Authors with CRIS profile

Andreas Bärmann Lehrstuhl für Analytics & Mixed-Integer Optimization Lukas Hager Lehrstuhl für Analytics & Mixed-Integer Optimization

Involved external institutions

Virginia Polytechnic Institute and State University (VirginiaTech) US United States (USA) (US) Fraunhofer-Institut für Integrierte Schaltungen (IIS) DE Germany (DE)

How to cite

APA:

Beach, B., Burlacu, R., Bärmann, A., Hager, L., & Hildebrand, R. (2024). Enhancements of discretization approaches for non-convex mixed-integer quadratically constrained quadratic programming: Part I. Computational Optimization and Applications. https://doi.org/10.1007/s10589-023-00543-7

MLA:

Beach, Benjamin, et al. "Enhancements of discretization approaches for non-convex mixed-integer quadratically constrained quadratic programming: Part I." Computational Optimization and Applications (2024).

BibTeX: Download