[LEL18a] Unconstrained 0-1 polynomial optimization through convex quadratic reformulation

Conférence Internationale avec comité de lecture : ISMP, July 2018, pp.1-2, Bordeaux, France,

Auteurs: A. Lazare , S. Elloumi , A. Lambert

Mots clés: Binary polynomial optimization, convex reformulation, quadratic reformumation, semidefinite programming

Résumé: This paper addresses the resolution of unconstrained binary polynomial programs (P ). We propose 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 (QP C). This convexification is computed thanks to a semidefinite relaxation. We compute the optimal value of the continuous relaxa- tion of (QP C) using the binary identity. Moreover, in order to start the third phase (Branch and Bound phase) with a tight bound, we use new valid equalities depending on the chosen quadratization. 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.

BibTeX

@inproceedings {
	LEL18a,
	title	=	"{Unconstrained 0-1 polynomial optimization through convex quadratic reformulation}",
	author	=	" A. Lazare and S. Elloumi and A. Lambert ",
	booktitle	=	"{ISMP}",
	year	=	2018,
	month	=	"July",
	pages	=	"1-2",
	address	=	"Bordeaux, France",
}