LOGIN TO YOUR ACCOUNT

Username
Password
Remember Me
Or use your Academic/Social account:

CREATE AN ACCOUNT

Or use your Academic/Social account:

Congratulations!

You have just completed your registration at OpenAire.

Before you can login to the site, you will need to activate your account. An e-mail will be sent to you with the proper instructions.

Important!

Please note that this site is currently undergoing Beta testing.
Any new content you create is not guaranteed to be present to the final version of the site upon release.

Thank you for your patience,
OpenAire Dev Team.

Close This Message

CREATE AN ACCOUNT

Name:
Username:
Password:
Verify Password:
E-mail:
Verify E-mail:
*All Fields Are Required.
Please Verify You Are Human:
fbtwitterlinkedinvimeoflicker grey 14rssslideshare1
Languages: French
Types: Article
Subjects: 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

Cite this article