Je suis intéressé par l'implémentation de SM pour la tâche LP, mais j'ai entendu parler d'éventuels pièges: le livre de Cormen dit qu'il est possible d'avoir des données d'entrée qui feront que l'implémentation naïve se comportera en temps exponentiel. J'ai également entendu que l'implémentation naïve peut boucler pour une sorte de données.
Existe-t-il un livre / papier / source qui explique les nuances de la mise en œuvre pratique de SM?
Merci d'avance.
Réponses:
Je recommande fortement l'article de Bixby, le "père" de CPLEX, qui étudie non seulement les aspects de mise en œuvre de l'algorithme simplex (révisé): Robert E. Bixby , Solving Real-World Linear Programs: A Decade and More of Progress , Operations Research (50) 2002, 3-15 .
la source
L'algorithme simplex n'est pas dans P. CLRS déclare donc que, même si en pratique il fonctionne "bien", il y a quelques entrées qui font fonctionner l'algorithme en temps exponentiel. Ceci est strictement lié à l'algorithme, pas à sa mise en œuvre: vous y serez confronté indépendamment de la façon dont vous implémentez l'algorithme. Cependant, LP est en P. Cela a été prouvé par Khachian en 1979, mais son algorithme ellipsoïde n'est pas pratique. Aujourd'hui, les méthodes des points intérieurs sont largement utilisées. Le premier a été découvert par Karmarkar en 1984.
Si vous êtes intéressé par les implémentations pratiques, jetez un œil à:
GUROBI, gratuit pour une utilisation académique, est actuellement le meilleur optimiseur disponible (versions parallèle séquentielle et à mémoire partagée):
http://www.gurobi.com
la bibliothèque GLPK:
http://www.gnu.org/software/glpk/
il s'agit d'un projet open source, fournissant des implémentations pour:
la source
Le livre de programmation linéaire de Vanderbei passe par de nombreux détails de bas niveau ... Mais comme les autres réponses / commentaires l'ont suggéré, l'implémentation du solveur LP est une tâche difficile et ingrate. Le solveur standard est probablement la voie à suivre ... (Il existe également des solveurs LP open source ...)
la source
Ce ne sont pas seulement des implémentations naïves qui se comportent parfois en temps exponentiel. En fait, je pense que toutes les règles déterministes et randomisées connues ont des entrées super-polynomiales dans le pire des cas. La plupart des entrées connues qui produisent ce comportement du pire des cas sont hautement structurées, une question connexe:
La structure des instances pathologiques pour les algorithmes simplex
Cependant, dans la pratique, SM fonctionne bien. Cela a été officialisé par l'introduction d'une analyse lissée qui est fondamentalement l'analyse du pire des cas avec des entrées légèrement perturbées. Selon cette analyse, SM est un polytime, en d'autres termes, pour chaque entrée (même pathologique) il y a une légère perturbation qui permet à l'algorithme de bien fonctionner. Cette idée a été transformée en un algorithme randomisé qui fonctionne en polytime. Cependant, pour autant que je sache, il y a encore un débat sur la question de savoir si cet algorithme peut être qualifié de «vrai» algorithme simplex. Je ne sais pas non plus si les packages standard implémentent quelque chose dans le sens de cela, mais vous devriez pouvoir trouver une implémentation si vous recherchez autour, car le résultat a plus de 5 ans.
la source
Vous pouvez vérifier Luenberger, Ye, Linear and Nonlinear Programming, 3rd ed. Cela semble assez complet, mais je ne suis pas encore allé assez loin pour dire si cela répond complètement à votre question.
la source