p-Lagrangian relaxation is a novel technique to solve nonconvex mixed-integer quadratically constrained quadratic programming (MIQCQP) with separable structures, 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 for 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 relaxation, is a primal-dual decomposition method that combines a bundle-method inspired Lagrangian decomposition with mixed-integer programming-based relaxations. These relaxations are obtained using the reformulated normalised multiparametric disaggregation technique (RNMDT) 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, in addition to demonstrating superior performance in terms of convergence behaviour, the proposed method presents significant reductions in computational time.
- Blood units inventory management
- Combining Progressive Hedging with a Frank--Wolfe Method to Compute Lagrangian Dual Bounds in Stochastic Mixed-Integer Programming
- A Lagrangean decomposition approach for oil supply chain investment planning under uncertainty with risk considerations
- A Strategy Based on Convex Relaxation for Solving the Oil Refinery Operations Planning Problem
- Enhancing the normalized multiparametric disaggregation technique for mixed-integer quadratic programming