A novel dual-decomposition method for non-convex mixed integer quadratically constrained quadratic problems

arXiv2302.09872MaRDI QIDQ6508892

Fabrício Vieira Oliveira, Nikita Belyak

Abstract: In this paper, we propose the novel $extitp$-branch-and-bound method for solving two-stage stochastic programming problems whose deterministic equivalents are represented by mixed-integer quadratically constrained quadratic programming (MIQCQP) models. The precision of the solution generated by the $extitp$-branch-and-bound method can be arbitrarily adjusted by altering the value of the precision factor $extitp$. The proposed method combines two key techniques. The first one, named $extitp$-Lagrangian decomposition, generates a mixed-integer relaxation of a dual problem with a separable structure for a primal MIQCQP problem. The second one is a version of the classical dual decomposition approach that is applied to solve the Lagrangian dual problem and ensures that integrality and non-anticipativity conditions are met in the optimal solution. The $extitp$-branch-and-bound method's efficiency has been tested on randomly generated instances and demonstrated superior performance over commercial solver Gurobi. This paper also presents a comparative analysis of the $extitp$-branch-and-bound method efficiency considering two alternative solution methods for the dual problems as a subroutine. These are the proximal bundle method and Frank-Wolfe progressive hedging. The latter algorithm relies on the interpolation of linearisation steps similar to those taken in the Frank-Wolfe method as an inner loop in the classic progressive heading.

Has companion code repository: https://github.com/gamma-opt/p-bnb

This page was built for publication: A novel dual-decomposition method for non-convex mixed integer quadratically constrained quadratic problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6508892)