Treatment of Degeneracy in Linear and Quadratic Programming

Dans cette thèse, nous considérons la résolution de problèmes d'optimisation quadratique dégénérés sur base de techniques initialement développées pour l'optimisation linéaire, ca-pables de tirer avantage de la dégénérescence. Nous commençons par améliorer l'efficacité de la règle de pivotage positive edge en fournissant une implémentation basée sur le logiciel libre CLP. Nous proposons ensuite le logiciel de haut niveau CyLP permettant de définir et d'expérimenter facilement avec de nouvelles règles de pivotage pour la méthode du Simplexe. CyLP offre de plus des services de modélisation puissants réduisant l'effort nécessaire à la modélisation de problèmes linéaires, en variables entières et quadratiques. À l'aide de CyLP, nous appliquons la règle positive edge à la variante du Simplexe suggérée par Wolfe pour résoudre les problèmes quadratiques. Nous incorporons également positive edge dans une méthode de gradient réduit. Nos tests démontrent l'efficacité de positive edge sur les problèmes quadratiques pour lesquels le terme linéaire est dominant. Chaque méthode est capable de fournir des niveaux substantiels d'accélération sur un certain sous-ensemble de problèmes lorsqu'elle est équipée de positive edge. Nous suggérons des pistes de recherche pour la conception de nouvelles méthodes qui incorporent positive edge et accélèrent la résolution sur une plus large gamme de problèmes.