[LEL19b] Stability in quadratic convex reformulation of unconstrained binary polynomial optimization

Conférence Internationale avec comité de lecture : EURO, June 2019, pp.1-2, Dublin, Irlande,
Résumé: We address the problem of stability in quadratic convex reformulation of poly- nomial programs. We present the main ideas behind PQCR, our three-phases algorithm to solve unconstrained binary polynomial programs. The first phase consists in a quadratic reformulation (quadratization) of the polynomial pro- gram (P) to obtain an equivalent non-convex quadratic program (QP). Then in the second phase, we compute a tight convex reformulation of (QP) using semidefinite programming. This convex reformulation uses valid equalities com- ing from the first phase. We then solve the obtained quadratic convex program by a branch and bound algorithm. We observe that the bound at the root node is dependent on the quadratic reformulation performed in the first phase and can thus vary between two quadratizations. In this paper, we highlight some properties for stabilizing families of quadratisation, i.e. that lead to the same bound after convexification.


@inproceedings {
title="{Stability in quadratic convex reformulation of unconstrained binary polynomial optimization}",
author=" A. Lazare and S. Elloumi and A. Lambert ",
address="Dublin, Irlande",