The p-Lagrangian relaxation for separable nonconvex MIQCQP problems
Loading...
Access rights
openAccess
Journal Title
Journal ISSN
Volume Title
A1 Alkuperäisartikkeli tieteellisessä aikakauslehdessä
This publication is imported from Aalto University research portal.
View publication in the Research portal
View/Open full text file from the Research portal
Other link related to publication
View publication in the Research portal
View/Open full text file from the Research portal
Other link related to publication
Date
2022-02-22
Major/Subject
Mcode
Degree programme
Language
en
Pages
34
Series
JOURNAL OF GLOBAL OPTIMIZATION
Abstract
This paper presents a novel technique to compute Lagrangian bounds for nonconvex mixed-integer quadratically constrained quadratic programming problems presenting a separable structure (i.e., a separable problems) such as those arising in deterministic equivalent representations of two-stage stochastic programming problems. In general, the nonconvex nature of these models still poses a challenge to the available solvers, which do not consistently perform well for larger-scale instances. Therefore, we propose an appealing alternative algorithm that allows for overcoming computational performance issues. Our novel technique, named the p-Lagrangian decomposition, is a decomposition method that combines Lagrangian decomposition with mixed-integer programming-based relaxations. These relaxations are obtained using the reformulated normalised multiparametric disaggregation technique and can be made arbitrarily precise by means of a precision parameter p. We provide a technical analysis showing the convergent behaviour of the approach as the approximation is made increasingly precise. We observe that the proposed method presents significant reductions in computational time when compared with a previously proposed techniques in the literature and the direct employment of a commercial solver. Moreover, our computational experiments show that the employment of a simple heuristic can recover solutions with small duality gaps.Description
Keywords
Other note
Citation
Andrade , T , Belyak , N , Eberhard , A , Hamacher , S & Oliveira , F 2022 , ' The p-Lagrangian relaxation for separable nonconvex MIQCQP problems ' , JOURNAL OF GLOBAL OPTIMIZATION , vol. 84 , no. 1 , pp. 43-76 . https://doi.org/10.1007/s10898-022-01138-y
