• Refine Query
  • Source
  • Publication year
  • to
  • Language
  • 1
  • Tagged with
  • 1
  • 1
  • 1
  • 1
  • 1
  • 1
  • 1
  • 1
  • 1
  • 1
  • 1
  • 1
  • 1
  • 1
  • 1
  • About
  • The Global ETD Search service is a free service for researchers to find electronic theses and dissertations. This service is provided by the Networked Digital Library of Theses and Dissertations.
    Our metadata is collected from universities around the world. If you manage a university/consortium/country archive and want to be added, details can be found on the NDLTD website.
1

Max-résolution et apprentissage pour la résolution du problème de satisfiabilité maximum / Max-resolution and learning for solving the Max-SAT problem

Abramé, André 25 September 2015 (has links)
Cette thèse porte sur la résolution du problème d'optimisation Maximum Satisfiability (Max-SAT). Nous y étudions en particulier les mécanismes liés à la détection et à la transformation des sous-ensembles inconsistants par la règle de la max-résolution. Dans le contexte des solveurs de type séparation et évaluation, nous présentons plusieurs contributions liées au calcul de la borne inférieure. Cela va du schéma d'application de la propagation unitaire utilisé pour détecter les sous-ensembles inconsistants à l'extension des critères d'apprentissage et à l'évaluation de l'impact des transformations par max-résolution sur l'efficacité des solveurs. Nos contributions ont permis l'élaboration d'un nouvel outil de résolution compétitif avec les meilleurs solveurs de l'état de l'art. Elles permettent également de mieux comprendre le fonctionnement des méthodes de type séparation et évaluation et apportent des éléments théoriques pouvant expliquer l'efficacité et les limites des solveurs existants. Cela ouvre de nouvelles perspectives d'amélioration, en particulier sur l'augmentation de l'apprentissage et la prise en compte de la structure interne des instances. Nous présentons également un exemple d'utilisation de la règle de la max-résolution dans un algorithme de recherche local. / This PhD thesis is about solving the Maximum Satisfiability (Max-SAT) problem. We study the mechanisms related to the detection and transformations of the inconsistent subsets by the max-resolution rule. In the context of the branch and bound (BnB) algorithms, we present several contributions related to the lower bound computation. They range from the study of the unit propagation scheme used to detect inconsistent subsets to the extension of the learning criteria and to the evaluation of the impact of the max-resolution transformations on the BnB solvers efficiency. Thanks to our contributions, we have implemented a new solver which is competitive with the state of art ones. We give insights allowing a better understanding of the behavior of BnB solvers as well as theoretical elements which contribute to explain the efficiency of these solvers and their limits. It opens new development perspectives on the learning mechanisms used by BnB solvers which may lead to a better consideration of the instances structural properties. We also present an example of integration of the max-resolution inference rule in a local search algorithm.

Page generated in 0.0708 seconds