L’aide à la décision a pour but d’assister un opérateur humain dans ses choix. La nécessité d’employer de telles techniques s’est imposée avec la volonté de traiter des problèmes dépendant d’une quantité de données toujours plus importante. L’intérêt de l’aide à la décision est encore plus manifeste lorsqu’on souhaite obtenir non pas une solution quelconque, mais une des meilleures solutions d’un problème combinatoire selon un critère donné. On passe alors d’un problème de décision (déterminer l’existence d’une solution) à un problème d’optimisation monocritère (déterminer une des meilleures solutions possibles selon un critère). Un décideur peut aussi souhaiter considérer plusieurs critères, et ainsi faire passer le problème de décision initial à un problème d’optimisation multicritère. La difficulté de ce type de problèmes provient du fait que les critères considérés sont généralement antagonistes, et qu’il n’existe donc pas de solution meilleure que les autres pour l’ensemble des critères. Dans ce cas, il s’agit plutôt de déterminer une solution qui offre un bon compromis entre les critères. Dans cette thèse, nous étudions dans un premier temps la complexité théorique de tâches d’optimisation complexes sur les langages de la logique propositionnelle, puis nous étudions leur résolution pratique via le recours à des logiciels bâtis pour résoudre de manière efficace en pratique des problèmes de décision combinatoires, les prouveurs SAT. / Decision aiding aims at helping a decision-maker to pick up a solution among several others. The usefulness of such approaches is as prominent as the size of the problems under consideration increases. The need of decision aiding techniques is salient when the problem does not just consist in deciding whether a solutions exists, but to find one of the best solutions according to a given criterion. In this case, the problem goes from a decision problem (decide whether a solution exists) to a single criterion optimization problem (find one of the best solutions according to a criterion). A decision-maker may even want to consider multiple criteria, which turns the initial decision problem into a multicriteria optimization problem. The main issue arising in such cases lies in the fact that the criteria under consideration are often antagonistic, which implies that there is no solution which is the best for each of the objectives. In this case, a good compromise solution is looked for. In this thesis, we first focus on the complexity of optimization requests based on a set of propositional languages. We then study the practical aspects of the resolution of such problems, using pieces of software designed for dealing with combinatorial decision problems, namely SAT solvers.
| Identifer | oai:union.ndltd.org:theses.fr/2015ARTO0405 |
| Date | 26 June 2015 |
| Creators | Lonca, Emmanuel |
| Contributors | Artois, Le Berre, Daniel |
| Source Sets | Dépôt national des thèses électroniques françaises |
| Language | French |
| Detected Language | French |
| Type | Electronic Thesis or Dissertation, Text |
Page generated in 0.0023 seconds