Unconstrained 0-1 polynomial optimization through convex quadratic reformulation

Unconstrained 0-1 polynomial optimization through convex quadratic reformulation 


Operations Seminar by Sourour Elloumi and Arnaud Lazare - N1 - 220
April 2018, Monday 23 (11:30 am)

 

****

This paper addresses the resolution of unconstrained binary polynomial programs(P). Wepropose a new 3-phases algorithm to solve(P). The first phase consists in reformulating(P)into a quadratic program (QP)using standard linearization inequalities. In the second phase, we reformulate(P) into a convex quadratic program (QPC). This convexification is computed thanks to a semidefinite relaxation. We compute the optimal value of the continuous relaxationof (QPC) using the binary identity. Moreover, in order to start the third phase (Branchand Bound phase) with a tight bound, we use new valid equalities depending on the chosenquadratization. These equalities highly increase the quality of the bound as it will be shown by testing our method on several benchmark instances and comparing it to other polynomial solvers.

***