1,721,100 research outputs found
Algorithms for elementary path problem : application to kidney exchange
No full textCette thèse traite de problèmes de chemins élémentaires et leur application au problème d’échange de reins. Nous nous concentrons sur des programmes d’échange de reins qui incluent des donneurs altruistes, qui sont essentiels pour les patients avec une maladie rénale, mais représentent un défi pour les méthodes de recherche opérationnelle. Notre objectif est de développer un algorithme efficace qui pourra être utilisé pour résoudre des instances futures, qui sont susceptibles d’impliquer un grand nombre de participants. Nous rencontrons des problèmes étroitement lié au notre : problèmes de packing, de tournée de véhicules, de stable. Pour ce dernier, nous présentons une nouvelle formulation étendue et prouvons qu’elle est idéale et compacte pour les graphes parfaits sans griffe. Nous nous focalisons ensuite sur la conception d’une génération de colonnes dédiée au problème d’échange de reins et nous attaquons à son problème de pricing, NP-difficile. Nous abordons le problème du chemin élémentaire minimum avec contrainte de taille, qui modélise la recherche de chaînes de dons intéressantes à ajouter dans la phase du pricing. Nous étudions des approches dynamiques, en particulier la relaxation NG-route et l’heuristique de color coding, et les améliorons en exploitant la contrainte de taille et la faible densité des graphes considérés. Nous nous intéressons ensuite au color coding dans un contexte plus général, proposant de nouvelles stratégies randomisées qui apportent une garantie d’amélioration. Ces stratégies s’appuient sur un ordonnancement du graphe et introduisent un biais dans la loi de probabilité pour augmenter les chances de trouver une solution optimale.This thesis deals with elementary path problems and their application to the kidney exchange problem. We focus on kidney exchange programs including altruistic donors, which are crucial for patients with renal disease and challenging for operations research methods. The goal of this work is to develop an efficient algorithm that can be used to solve future instances, which are likely to involve a large number of donors and patients. While we progress on this topic, we encounter closely related problems on packing, vehicle routing and stable set. For this last problem, we introduce a new extended formulation and prove it is ideal and compact for claw-free perfect graphs by characterizing its polytope. We then concentrate on the design of a column generation dedicated to the kidney exchange problem and confront its NP-hard pricing problem. The specific problem that we address is the elementary path problem with length constraint, which models the search for interesting chains of donation to add during the pricing step. We investigate dynamic approaches, in particular the NG-route relaxation and the color coding heuristic, and improve them by exploiting the length constraint and sparsity of graphs. We study the color coding in a more general context, providing a guaranteed improvement by proposing new randomized strategies. They are based on ordering the graph before coloring it and introduce a bias in the probability distribution to increase the probability of finding an optimal solution
Lagrangian Decomposition for Optimal Cost Partitioning
Get PDFOptimal cost partitioning of classical planning heuristics has been shown to lead to excellent heuristic values but is often prohibitively expensive to compute. Lagrangian decomposition and Lagrangian relaxation are classical tools in mathematical programming that apply to optimization problems with a special block structure. We analyze the application of Lagrangian decomposition to cost partitioning in the context of operator-counting heuristics and interpret Lagrangian multipliers as cost functions for the combined heuristics. This allows us to view the computation of an optimal cost partitioning as an iterative process that can be seeded with any cost partitioning and improves over time. We derive an any-time algorithm to compute an optimal non-negative cost partitioning of abstraction heuristics without involving an LP solver. In each iteration, the computation reduces to independent shortest path problems in all abstractions. Finally, we discuss the extension to general cost functions
Résolution de problèmes combinatoires par des approches fondées sur la notion d'explication
No full textConstraint programming is a search paradigm for solving combinatorial optimization pro- blems, that has been used to design generic solvers. Numerous researches are conducted to deal with over-constrained and dynamic problems. One of those, is based on the concept of explanations. Explanations provide a trace of the behavior of the solver and have been initially introduce to improve backtracking based algorithms. They have been used to design clever but costly ways of exploring the search space since that day. This phd thesis study explanation based algorithms on industrial as well as academical problems. We study the interest of explanation within generic decomposition techniques and imple- ment such an algorithm for a hard real time task allocation problem. This approach outlines the role of explanations within the cooperation of di®erent solving techniques. We also show that the explanation network is a relevant information to analyse the struc- tures of a problem and understand the relationships between its di®erent parts (variables and constraints). This information, used to improve the search heuristic, is another step toward generic search techniques. Finally, explanations have been often used for look-back but are still under-exploited for look-ahead in CP. Nogood recording techniques have never been successful contrary to what happended in the SAT community. We implement in this thesis such a nogood recording in the case of the minimum open stack problem.La programmation par contraintes est un paradigme de résolution des problèmes combinatoires sur lequel ont été bâtis des outils génériques de résolution, des solveurs. De nombreuses recherches sont menées pour élargir le champ d'application de ces outils µa des problèmes dynamiques et sur-contraints. Un axe prometteur s'appuie sur la notion d'explications. Les explications constituent une trace explicite du comportement du solveur et ont été initialement introduites pour améliorer les algorithmes de recherche arborescente. Depuis ce jour, elles ont ouvert la voie à des méthodes d'exploration plus intelligentes (mais aussi plus coûteuses) de l'espace de recherche. Cette thèse porte sur l'élaboration d'algorithmes de résolution s'appuyant sur la notion d'explications et les étudie sur des problèmes autant académiques qu'industriels. D'une part, nous examinons l'intérêt des explications dans le cadre de techniques génériques de décomposition. La mise au point d'un tel algorithme dans le contexte d'ordonnancement temps réel a montré la souplesse de la technique pour permettre la coopération de méthodes analytiques pointues avec un solveur de contraintes. D'autre part, nous montrons que le réseau d'explication constitue une information particulièrement pertinente pour révéler à un utilisateur les structures ou relations entretenues par différents éléments (variables/contraintes) du problème. Cette information, également exploitable dynamiquement par le solveur est un pas supplémentaire vers des approches de résolution génériques. Enfin, les explications ont été jusqu'ici très utilisées dans un cadre rétrospectif et pourraient l'être davantage dans un cadre prospectif (à l'image de leur exploitation par la communauté SAT). Nous revenons ainsi dans cette thèse sur des techniques de nogoods recording dans le cadre du problème de MOSP (Minimum Open Stack Problem)
Programmation linéaire et dynamique pour la programmation par contraintes
No full textInternational audienc
Recherche arborescente, L'art d'anticiper et de tirer les leçons du passé
No full textInternational audienc
Contraintes NP-Difficiles avec des coûts: exemples d’applications et de filtrage
No full textNational audienc
Résolution de problèmes combinatoires par des approches fondées sur la notion d'explication
No full textConstraint programming is a search paradigm for solving combinatorial optimization pro- blems, that has been used to design generic solvers. Numerous researches are conducted to deal with over-constrained and dynamic problems. One of those, is based on the concept of explanations. Explanations provide a trace of the behavior of the solver and have been initially introduce to improve backtracking based algorithms. They have been used to design clever but costly ways of exploring the search space since that day. This phd thesis study explanation based algorithms on industrial as well as academical problems. We study the interest of explanation within generic decomposition techniques and imple- ment such an algorithm for a hard real time task allocation problem. This approach outlines the role of explanations within the cooperation of di®erent solving techniques. We also show that the explanation network is a relevant information to analyse the struc- tures of a problem and understand the relationships between its di®erent parts (variables and constraints). This information, used to improve the search heuristic, is another step toward generic search techniques. Finally, explanations have been often used for look-back but are still under-exploited for look-ahead in CP. Nogood recording techniques have never been successful contrary to what happended in the SAT community. We implement in this thesis such a nogood recording in the case of the minimum open stack problem.La programmation par contraintes est un paradigme de résolution des problèmes combinatoires sur lequel ont été bâtis des outils génériques de résolution, des solveurs. De nombreuses recherches sont menées pour élargir le champ d'application de ces outils µa des problèmes dynamiques et sur-contraints. Un axe prometteur s'appuie sur la notion d'explications. Les explications constituent une trace explicite du comportement du solveur et ont été initialement introduites pour améliorer les algorithmes de recherche arborescente. Depuis ce jour, elles ont ouvert la voie à des méthodes d'exploration plus intelligentes (mais aussi plus coûteuses) de l'espace de recherche. Cette thèse porte sur l'élaboration d'algorithmes de résolution s'appuyant sur la notion d'explications et les étudie sur des problèmes autant académiques qu'industriels. D'une part, nous examinons l'intérêt des explications dans le cadre de techniques génériques de décomposition. La mise au point d'un tel algorithme dans le contexte d'ordonnancement temps réel a montré la souplesse de la technique pour permettre la coopération de méthodes analytiques pointues avec un solveur de contraintes. D'autre part, nous montrons que le réseau d'explication constitue une information particulièrement pertinente pour révéler à un utilisateur les structures ou relations entretenues par différents éléments (variables/contraintes) du problème. Cette information, également exploitable dynamiquement par le solveur est un pas supplémentaire vers des approches de résolution génériques. Enfin, les explications ont été jusqu'ici très utilisées dans un cadre rétrospectif et pourraient l'être davantage dans un cadre prospectif (à l'image de leur exploitation par la communauté SAT). Nous revenons ainsi dans cette thèse sur des techniques de nogoods recording dans le cadre du problème de MOSP (Minimum Open Stack Problem)
- …
