Etude de Resolution Search pour la Programmation Linéaire en Variables Binaires
Institution:
Montpellier 2Disciplines:
Directors:
Abstract EN:
In this thesis, we are interested in the exact resolution of 0-1 integer linear programming problems. Our work revolves around the study of Resolution search (Chvatal (1997)) for solving the 0-1 multidimensional knapsack problem. As a first step, we propose an implicit enumeration algorithm based on an analysis of the reduced costs at the optimality of the problem's LP-relaxation and on the decomposition of the search space in hyperplanes. We propose an original branching strategy which focuses on pruning the search tree as soon as possible. This strategy is effective for solving difficult instances, however, it makes the algorithm depends on to the knowledge of a good starting solution. In a second step, we propose an exact method combining Resolution search with an implicit enumeration similar to the first algorithm. The resulting cooperation enables to obtain good solutions rapidly and to prove the optimality of several larger instances. Finally, we show that the scope of Resolution search can be extended to nonlinear combinatorial optimization problems and we present an application to a scheduling problem in the field of telecommunications
Abstract FR:
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