Abstract FR:

L'objet de cette thèse consiste en la comparaison et l'amélioration des algorithmes de résolution de programmes linéaires fondés sur le principe de cheminement à l'intérieur strict du polytope des points réalisables. Ceci nous conduit tout d'abord à faire un état de l'art des méthodes intérieures en programmation linéaire proposées depuis 1947, et à en extraire celles qui semblent avoir, selon la littérature, les meilleures performances ou susceptibles d'être sensiblement améliorées : c'est à dire, les méthodes duales purement affines, les méthodes affines utilisant une fonction potentielle, et les méthodes primales-duales de path-following, simple et prédictive-corrective de type S. Mehrotra, qui est actuellement l'une des plus rapides. Plus précisément, en nous basant sur les travaux d'Adler et al. , l'algorithme dual affine de I. I. Dikin ainsi que l'algorithme polynomial affine de C. C. Gonzaga ont été implémentés avec la bibliothèque fortran IPMLO. Pour les méthodes de path-following, nous avons utilise le code PDLBM de la méthode primale-duale avec fonction barrière logarithmique de McShane et al. , ainsi que 2 codes de la méthode primale-duale prédictive-corrective : l'excellent code universitaire HOPDM 2. 13 de J. Gondzio et le code professionnel CPLEX 3. 0 qui sont parmi les plus rapides et les plus précis existants. Pour effectuer des comparaisons plus pertinentes des algorithmes expérimentés, nous nous plaçons dans un contexte unique de programmation adapté aux besoins actuels de la recherche : notamment, d'une part, nous raffinons les critères de performances existants, en proposons de nouveaux et comparons les performances des codes pour l'obtention de solutions approchées. Pour éprouver plus sévèrement les algorithmes, nous simulons des conditions expérimentales particulièrement défavorables et difficiles pour une approche intérieure. D'autre part, la rapidité de convergence des méthodes intérieures étant toujours et particulièrement sensible au choix des initialisations -celles ci n'étant pas déterminées d'une manière parfaite- il nous a aussi paru important de tester la robustesse des performances et de nos comparaisons numériques des codes, en faisant varier la position du point de départ dans le polyèdre. A notre connaissance, de tels tests de robustesse n'avaient pas été encore entrepris. Par ailleurs, lors d'une 1ère série d'expérimentations, nous mettons en évidence les points faibles des méthodes duales affines et des méthodes primales-duales déjà existantes : le problème de convergence trop lente ou de convergence non polynomiale de la méthode duale affine, et le manque de robustesse de la méthode primale-duale. Pour y remédier, nous proposons et mettons en œuvre quatre améliorations importantes de la méthode duale ; notamment, une méthode de recentrage du premier point réalisable sous une contrainte plancher, ainsi qu'une adaptation de la méthode polynomiale de Gonzaga, qui vont constituer deux codes particulièrement efficaces : REO2affine et GONZédal. L'une de ces deux méthodes pourra améliorer la robustesse des méthodes primales-duales. Avec notre nouveau protocole expérimental et grâce à nos améliorations de la méthode duale, nous mettons en évidence des phénomènes numériques tout à fait intéressants, inconnus jusqu'alors, qui vont remettre en question les conclusions établies par la communauté scientifique. Lors de tests numériques très poussés, nous confirmons que les meilleures méthodes primales-duales sont incontestablement plus rapides que les meilleures méthodes duales, mais dans des proportions bien moindres qu'il n'y paraissait. De plus, les codes duaux se sont avérés nettement plus robustes que les codes primaux-duaux. En conclusion, nous nous demandons alors légitimement, lorsque l'on conçoit un logiciel - que l'on veut efficace - de programmation mathématique, s'il n'est pas préférable de lui donner à la fois des qualités de rapidité et de robustesse plutôt que seulement la première de celles-ci.