Séminaire - 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.