A novel dual-decomposition method for non-convex two-stage stochastic mixed-integer quadratically constrained quadratic problems
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , |
|---|---|
| Format: | Preprint |
| Publié: |
2023
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866912236506710016 |
|---|---|
| author | Belyak, Nikita Oliveira, Fabricio |
| author_facet | Belyak, Nikita Oliveira, Fabricio |
| contents | We propose the novel p-branch-and-bound method for solving two-stage stochastic programming problems whose deterministic equivalents are represented by non-convex mixed-integer quadratically constrained quadratic programming (MIQCQP) models. The precision of the solution generated by the p-branch-and-bound method can be arbitrarily adjusted by altering the value of the precision factor p. The proposed method combines two key techniques. The first one, named p-Lagrangian decomposition, generates a mixed-integer relaxation of a dual problem with a separable structure for a primal non-convex 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 once the optimal solution is obtained. This paper also presents a comparative analysis of the p-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 hedging. The p-branch-and-bound method's efficiency was tested on randomly generated instances and demonstrated superior performance over commercial solver Gurobi. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2302_09872 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | A novel dual-decomposition method for non-convex two-stage stochastic mixed-integer quadratically constrained quadratic problems Belyak, Nikita Oliveira, Fabricio Optimization and Control Numerical Analysis We propose the novel p-branch-and-bound method for solving two-stage stochastic programming problems whose deterministic equivalents are represented by non-convex mixed-integer quadratically constrained quadratic programming (MIQCQP) models. The precision of the solution generated by the p-branch-and-bound method can be arbitrarily adjusted by altering the value of the precision factor p. The proposed method combines two key techniques. The first one, named p-Lagrangian decomposition, generates a mixed-integer relaxation of a dual problem with a separable structure for a primal non-convex 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 once the optimal solution is obtained. This paper also presents a comparative analysis of the p-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 hedging. The p-branch-and-bound method's efficiency was tested on randomly generated instances and demonstrated superior performance over commercial solver Gurobi. |
| title | A novel dual-decomposition method for non-convex two-stage stochastic mixed-integer quadratically constrained quadratic problems |
| topic | Optimization and Control Numerical Analysis |
| url | https://arxiv.org/abs/2302.09872 |