Séminaire Lucas Letocart

Jeudi 05 septembre 2019 (14h00, Salle C103)

Lucas Letocart, LIPN, Université Paris 13, France.

Titre : Column generation methods for quadratic programming

Résumé : The purpose of this talk is to present three column generation methods for quadratic problems. First, we analyze a simplicial decomposition like algorithmic framework that handles convex quadratic programs in an effective way. In particular, we propose two tailored strategies for solving the master problem and we describe a few techniques for speeding up the solution of the pricing problem. Then, we propose a methodological analysis on a family of reformulations combining Dantzig-Wolfe decomposition and Quadratic Convex Reformulation principles for binary quadratic problems. As a representative case study, we apply them to a cardinality constrained quadratic knapsack problem. Finally, we propose a column generation method for quadratically constrained 0-1 quadratic problems based on a Dantzig-Wolfe reformulation that leads to a linear master and an unconstrained 0-1 pricing problem. The domain of this relaxation is contained in the cone of Completely Positive matrices.