Soutenance de th
Forum 'Annonces' - Sujet créé le 2008-11-23
Bonjour,
J'ai le plaisir de vous annoncer la soutenance de ma thèse qui aura lieu le jeudi 27 novembre 2008 à 14h30 sur le site EERIE de l'Ecole des Mines d'Alès à Nîmes.
Titre: Etude de Resolution Search pour la Programmation Linéaire en Variables Binaires
Membres du jury:
- Mr PLATEAU Gérard, Professeur, Rapporteur, LIPN Université Paris XIII
¨ Mr FEILLET Dominique, Professeur, Rapporteur, Ecole des Mines de Saint-Etienne
¨ Mr MACULAN Nelson, Professeur, Examinateur, Université Fédérale de Rio de Janeiro
¨Mr HANAFI SaÏd, Professeur, Examinateur, LAMIH Université de Valenciennes
¨ Mr COGIS Olivier, Professeur, Examinateur, LIRMM Université Montpellier II
¨ Mr BOURREAU ERIC, Maître de Conférences, Examinateur,
LIRMM Université Montpellier II
- Mr WILBAUT Christophe, Maître de Conférences, Invité, LAMIH Université de Valenciennes
- Mr VASQUEZ Michel, Enseignant Chercheur HDR, Directeur, LGI2P Ecole des Mines d'Alès
¨ Mr VIMONT Yannick, Professeur, Co-Encadrant, Ecole des Mines d'Alès
Résumé: Dans cette thèse, nous nous intéressons à la résolution exacte de programmes linéaires en variables binaires. L'ensemble de nos travaux s'articule autour de l'étude de Resolution search (Chvatal 1997) pour la résolution du problème du sac à dos multidimensionnel en 0-1. Dans un premier temps, nous proposons un algorithme d'énumération implicite centré sur une analyse des coûts réduits à l'optimum de la relaxation continue ainsi que sur une décomposition de l'espace de recherche en hyperplans. Nous proposons une stratégie de branchement originale visant à élaguer au plus tôt l'arbre de recherche. Cette stratégie est efficace pour résoudre des instances jugées difficiles mais rend l'algorithme dépendant de la connaissance d'une bonne solution de départ. Dans un deuxième temps, nous proposons une méthode de résolution plus autonome combinant Resolution search avec une énumération implicite inspirée du premier algorithme. Cette coopération permet d'obtenir rapidement de bonnes solutions et prouve les optimums d'instances de plus grande taille. Finalement, nous montrons que le champ d'application de Resolution search peut être étendu à des problèmes d'optimisation combinatoire non linéaire et présentons une application à la résolution d'un problème de planification dans le domaine des télécommunications.
Cordialement,
Sylvain Boussier
J'ai le plaisir de vous annoncer la soutenance de ma thèse qui aura lieu le jeudi 27 novembre 2008 à 14h30 sur le site EERIE de l'Ecole des Mines d'Alès à Nîmes.
Titre: Etude de Resolution Search pour la Programmation Linéaire en Variables Binaires
Membres du jury:
- Mr PLATEAU Gérard, Professeur, Rapporteur, LIPN Université Paris XIII
¨ Mr FEILLET Dominique, Professeur, Rapporteur, Ecole des Mines de Saint-Etienne
¨ Mr MACULAN Nelson, Professeur, Examinateur, Université Fédérale de Rio de Janeiro
¨Mr HANAFI SaÏd, Professeur, Examinateur, LAMIH Université de Valenciennes
¨ Mr COGIS Olivier, Professeur, Examinateur, LIRMM Université Montpellier II
¨ Mr BOURREAU ERIC, Maître de Conférences, Examinateur,
LIRMM Université Montpellier II
- Mr WILBAUT Christophe, Maître de Conférences, Invité, LAMIH Université de Valenciennes
- Mr VASQUEZ Michel, Enseignant Chercheur HDR, Directeur, LGI2P Ecole des Mines d'Alès
¨ Mr VIMONT Yannick, Professeur, Co-Encadrant, Ecole des Mines d'Alès
Résumé: Dans cette thèse, nous nous intéressons à la résolution exacte de programmes linéaires en variables binaires. L'ensemble de nos travaux s'articule autour de l'étude de Resolution search (Chvatal 1997) pour la résolution du problème du sac à dos multidimensionnel en 0-1. Dans un premier temps, nous proposons un algorithme d'énumération implicite centré sur une analyse des coûts réduits à l'optimum de la relaxation continue ainsi que sur une décomposition de l'espace de recherche en hyperplans. Nous proposons une stratégie de branchement originale visant à élaguer au plus tôt l'arbre de recherche. Cette stratégie est efficace pour résoudre des instances jugées difficiles mais rend l'algorithme dépendant de la connaissance d'une bonne solution de départ. Dans un deuxième temps, nous proposons une méthode de résolution plus autonome combinant Resolution search avec une énumération implicite inspirée du premier algorithme. Cette coopération permet d'obtenir rapidement de bonnes solutions et prouve les optimums d'instances de plus grande taille. Finalement, nous montrons que le champ d'application de Resolution search peut être étendu à des problèmes d'optimisation combinatoire non linéaire et présentons une application à la résolution d'un problème de planification dans le domaine des télécommunications.
Cordialement,
Sylvain Boussier