Séminaire (organisé par l’équipe de recherche RO)

Xiaokang CAO


Le problème de renouvellement des équipements multi-période (MPR)


Mardi 13 avril à 12h en RD134


Résumé :

Le problème de renouvellement des équipements multi-période (MPR) consiste à déterminer les dates de renouvellements d’un ensemble des équipements, étant donné des budgets disponibles sur un ensemble des périodes consécutives. Ce problème est issu d’applications industrielles.

Nous avons proposé un modèle mathématique proche de celui de multi sac-à-dos, appelé le problème de multi sac-à-dos multi-période (MPMKP). Ce modèle nous permet d’utiliser des budgets de manière flexible. Du point de vue théorique, c’est un problème qui ressemble dans certains aspects à quelques autres problèmes de la littérature, mais qui n’a pas été explicitement étudié. Tous ces problèmes peuvent être vus comme des variantes du problème de sac-à-dos.

Nous avons d’abord étudié les liens avec d’autres problèmes de sac-à-dos. Nous avons ensuite fait une étude complète sur la complexité à travers quelques cas spéciaux. En particulier, on a montré qu’un cas spécial peut être résolu en temps polynomial via un modèle de max flow cout min et deux autres cas peuvent être résolus par la programmation dynamique en temps pseudo-polynomial, alors que le problème général est NP-difficile au sens fort.

Nous avons proposé ensuite deux heuristiques et une méta-heuristique pour ce problème. Nous avons comparé nos approches avec deux heuristiques de la littérature adaptées à notre problème ainsi que les résultats obtenus avec le solveur MIP de CPLEX sur un nombre important d’instances générées. La relaxation lagrangienne et des inégalités valides sont également à l’étude.

Mots-clés :

Sac-à-dos multi-période, complexité, programmation dynamique, heuristique.

Seminars


Mardi 10 mai 2016

Séminaire à 14 h 30 en GI042 présenté par Christophe DENIS, Chargé de Formation et de Recherche au Centre de mathématiques et de leurs applications (CMLA), ENS Cachan. « Verificarlo : checking the floating point accuracy of scientific codes »


Lundi 14 mars 2016

Séminaire à 9 h en GI042, présenté par Ahcène Bounceur, Maître de conférence, HDR, à l’Université de Bretagne Occidentale (UBO). « CupCarbon : A New Platform for Simulating Smart Wireless Sensor Networks (SWSN) »


Mardi 9 février 2016

Séminaire à 14 h en GI042 présenté par Fabio D’Andreagiovanni, Chercheur senior et Directeur de projet au département d’optimisation de Zuse Institute Berlin (ZIB), Berlin (Allemagne). « Multiband Robust Optimization : theory and applications »


Jeudi 28 janvier 2016

Séminaire à 15 h 30 en GI042 présenté par Said Tabli, stagiaire au sein du laboratoire Heudiasyc. « Trust Management in Clustered Wireless Sensor Networks »


Pages 1 | 2 | 3 | 4 | 5 | 6 | 7




Actualités
Vidéothèque
Téléchargements
Annuaire



FR SHIC 3272

Collegium UTC/CNRS