Abstract FR:

Dans le cadre de cette these, nous definissons deux niveaux de formalisation d'un probleme reel d'optimisation combinatoire : le modele de haut niveau et le modele de bas niveau, le premier etant destine a une analyse du probleme, et le deuxieme a l'implementation de l'algorithme de resolution. L'objectif principal de ce travail est de proposer des regles de choix de la methode de resolution et du modele de bas niveau a partir de proprietes decrivant le modele de haut niveau. Nous etudions la complexite theorique des problemes correspondant a certains modeles de bas niveau et prouvons leur non-approximabilite, ce qui montre la necessite de trouver une methode de resolution et un modele de bas niveau appropries pour les resoudre. Sur l'exemple de trois problemes industriels de grande taille que nous resolvons avec succes, nous illustrons comment choisir une telle methode et un tel modele. Apres avoir formalise un ensemble de proprietes de probleme, nous introduisons des regles, destinees a guider le chercheur dans le choix de la methode et du modele, et dont ces proprietes sont les premisses. Les regles sont validees sur un ensemble de 23 problemes reels collectes dans la litterature du domaine.