Return to search

Etude de Resolution Search pour la programmation linéaire en variables binaires

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 (Chvátal (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 présentons une application de Resolution Search à la résolution d'un problème de planification dans le domaine des télécommunications.

Identiferoai:union.ndltd.org:CCSD/oai:tel.archives-ouvertes.fr:tel-00381912
Date27 November 2008
CreatorsBoussier, Sylvain
PublisherUniversité Montpellier II - Sciences et Techniques du Languedoc
Source SetsCCSD theses-EN-ligne, France
LanguageFrench
Detected LanguageFrench
TypePhD thesis

Page generated in 0.0021 seconds