Problèmes d'optimisation combinatoire sous contraintes : vers la conception automatique de méthodes de résolution adaptées à chaque instance

Other literature type French OPEN
Lobjois, Lionel (1999)
  • Subject: Optimisation combinatoire | Problèmes de satisfaction de contraintes valuées (VCSP) | Programmation par contraintes (PPC) | Méthodes de séparation et évaluation | Locales et hybrides | Estimation stochastique | Estimateur de Knuth | Adaptation automatique | 000 | Combinatorial Optimization | Valued Constraint Satisfaction Problems (VCSP) | Constraint Programming (CP) | Branch&Bound | Local Search | Hybrid methods | Knuth estimator | Automatic algorithm tuning

Nous étudions dans cette thèse deux voies pour résoudre plus efficacement les problèmes d'optimisation combinatoire exprimés dans le cadre génétique VCSP (Valued Constraint Satisfaction Problem), extension du cadre CSP (Constraint Satisfaction Problem) pour l'optimisation. La première voie concerne la recherche de nouvelles méthodes globalement plus performantes par la coopération entre méthodes complètes et méthodes incomplètes. Nous proposons en particulier une nouvelle méthode hybride dédiée à la résolution de VCSP en contexte interruptible et la comparons aux recherches locales standards. La seconde voie concerne la recherche d'outil d'aide à la décison permettant d'utiliser une méthode adaptée à chaque situation, c'est-à-dire adaptée à l'instance à résoudre et au temps imparti à la résolution de cette instance. Nous proposons tout d'abord une adaptation de la méthode proposée par Knuth en 1975 afin d'estimer le temps de résolution des méthodes complètes de type séparation et évaluation. Nous envisageons ensuite une série d'application potentielles pour cet estimateur. Nous proposons notamment la méthode SPP (algorithm Selection by Performance Prediction) capable de sélectionner, instance par instance, l'algorithme le plus performant parmi une base d'algorithmes complets. Nous terminons ce mémoire par quelques voies permettant d'étendre cette méthode à une construction automatique d'algorithmes complets "optimisés" pour chaque instance. We study in this thesis two paths to better solve combinatorial optimization problems expressed in the generic V CSP (Valued Constraint Satisfaction Problem) framework, an extension of the well known USP framework to optimization problems. The first way concerns the hybridization of complete and incomplete methods. We propose a new hybrid method to solve VCSP in an anytime context and present comparisons to standard local searches. The second way concerns the design of decision-making tools allowing one to use an appropriate method when facing a particular problem instance. We propose first an adaptation of the estimator proposed by Knuth in 1975 in order to estimate the computation time of Branch and Bound methods. We then consider a list of potential applications for this estimator. We propose a method called SPP (algorithm Selection by Performance Prediction) to select, for each particular problem instance, the most appropriate BXLB algorithm from among several promising ones. We finish by suggesting some new ways to extend this method to the automatic configuration of complete algorithms for each particular problem instance.
Share - Bookmark