Premières références pour une optimisation discrète

9

(Toutes mes excuses si cela est déplacé ou trop large. Je suis ouvert aux suggestions sur la façon de le reformuler.)

Je suis intéressé à retracer l'histoire "ancienne" des algorithmes max-flow et des algorithmes d'optimisation discrets en général. Ford-Fulkerson est mon homme de paille d'un point de départ. Quelles ont été les avancées importantes avant cela? Jusqu'où peut-on remonter tout en étant en mesure de faire un argument raisonnable que quelqu'un travaillait sur max-flow? Et les algorithmes graphiques? Et l'optimisation discrète en général?

Je serais également heureux d'obtenir des références aux endroits où cela est discuté.

ds.algorithms graph-algorithms ho.history-overview dan_x
la source

Réponses:

14

Habituellement, Schrijver fournit une bonne source d'histoire. Vous pouvez consulter les livres suivants et un article.

  • Alexander Schrijver. Optimisation combinatoire: polyèdres et efficacité. Springer 2003.
  • Alexander Schrijver. Théorie de la programmation linéaire et entière. Wiley 1998.
  • Alexander Schrijver. Sur l'histoire des problèmes de transport et de débit maximum. Programmation mathématique 91 (3), 2002, 437-445. http://dx.doi.org/10.1007/s101070100259
  • Alexander Schrijver. Sur l'histoire de l'optimisation combinatoire (jusqu'en 1960). Handbook of Discrete Optimization, Elsevier, 2005. http://homepages.cwi.nl/~lex/files/histco.pdf
Yoshio Okamoto
la source
1
+1 pour Schrijver. J'ai ajouté une quatrième source recommandée, qui pointe vers les premiers articles de Frobenius [1912] et Kőnig [1915] sur l'appariement bipartite, Boruvka [1926] sur les arbres couvrant minimum, Menger [1927] sur son soi-disant " théorème -arc" et encore [1930] sur le problème des vendeurs ambulants, et Tolstoi [1930] sur le problème des transports. n
Jeffε
@ Jɛ ff E: Merci beaucoup pour cet ajout.
Yoshio Okamoto
Je vous remercie. Le dernier, sur l'histoire de l'optimisation combinatoire, est exactement ce que je cherchais.
dan_x
7

La plupart des gens citent le papier «Ponts de Königsburg» d'Euler de 1741 comme l'algorithme de graphique le plus ancien. Malheureusement, Euler ne décrit pas réellement son algorithme en détail, mais ne donne qu'un exemple sans enthousiasme:

«Quand il a été déterminé qu'un tel voyage peut être fait, il faut encore trouver comment il doit être organisé. Pour cela, j'utilise la règle suivante: que les paires de ponts qui mènent d'une zone à une autre soient supprimées mentalement, réduisant ainsi considérablement le nombre de ponts; il est alors facile de construire la route requise à travers les ponts restants. et les ponts qui ont été supprimés ne modifieront pas de manière significative l'itinéraire trouvé, comme cela deviendra clair après un peu de réflexion. Je ne pense donc pas qu'il soit utile de donner plus de détails concernant la recherche des itinéraires. "

La première preuve complète que tous les graphes même connectés ont des tournées eulériennes est apparemment due à Heirholzer plus d'un siècle plus tard.

  • Leonhard Euler. Solutio problematis ad geometriam situs relevantis. Commentarii academiae scientiarum Petropolitanae 8: 128–140, 1741. Présenté à l'Académie de Saint-Pétersbourg le 26 août 1735. Réimprimé dans Opera Omnia 1 (7): 1–10.

  • Carl Hierholzer. Über die Möglichkeit, einen Linienzug Ohne Wiederholung und ohne Unterbrechnung zu umfahren. Mathematische Annalen 6: 30–32, 1873.

Jeffε
la source