EURO 2024 Copenhagen
Abstract Submission

EURO-Online login

2274. Polynomial Optimization: Tightening branch-and-bound schemes with conic constraints

Invited abstract in session WA-4: Algorithms for Mixed-Integer Nonlinear Programming and Nonconvex Optimization, stream MINLP.

Wednesday, 8:30-10:00
Room: 1001 (building: 202)

Authors (first author is the speaker)

1. Brais González Rodríguez
University of Vigo
2. Raúl Alvite Pazó
University of Santiago de Compostela
3. Samuel Alvite Pazó
University of Santiago de Compostela
4. Bissan Ghaddar
Ivey Business School
5. Julio González-Díaz
Statistics, Mathematical Analysis and Optimization, University of Santiago de Compostela

Abstract

Conic optimization has recently emerged as a powerful tool for designing tractable and guaranteed algorithms for non-convex polynomial optimization problems. On the one hand, tractability is crucial for efficiently solving large-scale problems and, on the other hand, strong bounds are needed to ensure high-quality solutions. In this research, we consider constraints based on linear, second-order cone, and semidefinite programming and study their impact when used to tighten the baseline relaxations of a given global optimization algorithm. We describe how to design these conic constraints and their performance with respect to each other and with respect to the standard RLT relaxations for polynomial optimization problems. Our finding is that the different variants of nonlinear constraints (second-order cone and semidefinite) are the best performing ones in around $50\%$ of the instances in widely used test sets. Additionally, we present a machine learning approach to decide on the most suitable constraints to add to a given instance. The computational results show that the machine learning approach significantly outperforms each of the individual approaches.

Keywords

Status: accepted

Back to the list of papers