A l’initiative du LMAH, Lucas Letocart, LIPN, Université Paris 13 propose un séminaire intitulé 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 simplical 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.
