Techniques hybrides de propagation de contraintes et de programmation mathématique
Institution:
AvignonDisciplines:
Directors:
Abstract EN:
Cette thèse s'intéresse à des techniques hybrides de programmation linéaire et de programmation par contraintes pour la résolution de problèmes d'optimisation combinatoire. Les problèmes cibles sont le problème du sac-à-dos multi-dimensionnel et le problème d'allocation de fréquences. Nous proposons une méthode de séparation, évaluation et géneration de plan coupants pour la résolution à l'optimum de modèles en nombres entiers. Ce schéma est appliqué au sein d'une méthode hybride de programmation par contraintes associée à une relaxation résolue par programmation linéaire. L'originalité de l'approche proposée repose sur l'utilisation des coûts réduits des variables de la relaxation linéaire pour dériver de nouvelles règles de filtrage dans le processus de propagation de contraintes. Pour le problème d'allocation de fréquences, cette méthode est appliquée à une nouvelle formulation, basée sur une approche plus réaliste des perturbations de type électromagnétique avec l'introduction de contraintes cumulatives. Une contrainte cumulative intègre la fréquence associée au trajet et l'ensemble des fréquences associées aux trajets perturbateurs
Abstract FR:
This thesis deals with the integration of Constraint and Linear Programming techniques for solving combinatorial optimization problems. The target problems are the Multidimensional Zero-One Knapsack Problem and the Frequency Assignment Problem. We propose a branch and cut method for solving Integer Linear programming models. This framework is applied in the core of an hybrid Constraint Programming method associated to a relaxation solved by Linear Programming. The originality of the proposed approach is to use the reduced costs of the linear relaxation's variables for generating logic constraints to improve the constraint propagation process. For the frequency assignment problem, this method is applied to a new model based on a more realistic approach of the disturbances of electromagnetic constraints by introducing the cumulative constraints. A cumulative constraint contains the frequency associated with a link and the set of frequencies associated with the disturbance links