ULHN - UNIVERSITÉ LE HAVRE NORMANDIE

Accueil > Actualités > Recherche > Séminaire - Column generation methods for quadratic programming

Séminaire - Column generation methods for quadratic programming

jeudi 5 septembre 2019 à 14:00

Manifestation scientifique ouverte au grand public

Manifestation scientifique pour la Recherche

Université Le Havre Normandie, UFR Sciences et Techniques, Salle C103

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.

Mise en ligne : 30-08-2019 - Mise à jour : 04-09-2019

Informations pratiques

LMAH - Laboratoire de Mathématiques Appliquées du Havre - EA 3821

Tél. : 02 32 74 43 46
Courriel : lmah@univ-lehavre.fr

Actualités

Facebook
Plan du site - Mentions légales – © 2014-2019 Université du Havre - 25 rue Philippe Lebon - BP 1123 - 76063 Le Havre Cedex France
téléphone : +33 (0)2 32 74 40 00 communication@univ-lehavre.fr