Thursday 27
Non-linear optimisation, bi-level optimisation and yield management
Claudia D'Ambrosio
› 10:30 - 11:00 (30min)
› Bât. A - TD 34
Approches exactes pour le problème du sac à dos quadratique avec contrainte de cardinalité
Lucas Létocart  1@  , Monique Guignard-Spielberg  2@  , Gérard Plateau  1@  , Frédéric Roupin  1@  , Angelika Wiegele  3@  
1 : Laboratoire d'Informatique de Paris-Nord  (LIPN)  -  Website
Université Paris XIII - Paris Nord, CNRS : UMR7030, Institut Galilée
Institut Galilée 99, avenue J.B Clément 93430 VILLETANEUSE -  France
2 : OPIM Dept., the Wharton School, Univ. of Pennsylvania, Philadelphia, USA
3 : Institut für Mathematik, Alpen-Adria-Universität Klagenfurt, Austria

Le problème du sac à dos quadratique avec contrainte de cardinalité (E-kQKP) consiste à maximiser une fonction quadratique à coefficients positifs soumise à deux contraintes linéaires, l'une portant sur la capacité du sac et l'autre imposant le nombre d'objets à mettre dans le sac. Ce problème NP-difficile est une extension du problème du sac à dos quadratique dans lequel le nombre d'objets à mettre dans le sac est fixé à k.
Plusieurs approches exactes, basées sur une évaluation et séparation progressive, pour ce problème seront proposées et de nombreux résultats expérimentaux seront présentés afin de comparer ces différentes approches:
- résolution directe par un solveur (Cplex) en utilisant une relaxation linéaire ou une relaxation quadratique convexe,
- convexifications (Reformulation Quadratique Convexe (QCR) et une nouvelle variante permettant d'obtenir de meilleurs majorants à la racine de l'arbre de recherche) puis résolution du problème convexifié par un solveur,
- résolution par le solveur non linéaire BiqCrunch en intégrant une algorithmique spécifique, notamment pour la détermination de solutions réalisables et une approche basée sur la programmation semi-définie pour l'obtention des majorants,
- et résolution par un branch and bound spécifique intégrant différentes stratégies de branchement, des heuristiques dédiées, des inégalités valides lors de la résolution de la relaxation semi-définie (via csdp et conic bundle) en chaque noeud de l'arbre de recherche.

 


Online user: 2