Quadratic convex reformulations for quadratic 0-1 programming

摘要

This is a summary of the author's PhD thesis supervised by A. Billionnet and S. Elloumi and defended on November 2006 at the CNAM, Paris (Conservatoire National des Arts et Metiers). The thesis is written in French and is available from http://www.cedric.cnam.fr/PUBLIS/RC1115. This work deals with exact solution methods based on reformulations for quadratic 0-1 programs under linear constraints. These problems are generally not convex; more precisely, the associated continuous relaxation is not a convex problem. We developed approaches with the aim of making the initial problem convex and of obtaining a good lower bound by continuous relaxation. The main contribution is a general method (called QCR) that we implemented and applied to classical combinatorial optimization problems.