Wczesne referencje do dyskretnej optymalizacji

(Przepraszamy, jeśli jest to źle umieszczone lub zbyt szerokie. Jestem otwarty na sugestie, jak to przeformułować).

Interesuje mnie prześledzenie „starożytnej” historii algorytmów maksymalnego przepływu i ogólnie dyskretnych algorytmów optymalizacji. Ford-Fulkerson jest moim słomkowym punktem wyjścia. Jakie były wcześniej znaczące postępy? Jak daleko możemy się cofnąć, wciąż będąc w stanie uzasadnić, że ktoś pracował nad maksymalnym przepływem? A co z algorytmami graficznymi? Co powiesz na ogólną optymalizację dyskretną?

Z przyjemnością otrzymam również odniesienia do miejsc, w których jest to omawiane.

Zazwyczaj Schrijver stanowi dobre źródło historii. Możesz spojrzeć na następujące książki i artykuł.

• Alexander Schrijver. Optymalizacja kombinatoryczna: wielościany i wydajność. Springer 2003.
• Alexander Schrijver. Teoria programowania liniowego i liczb całkowitych. Wiley 1998.
• Alexander Schrijver. Na temat historii transportu i problemów z maksymalnym przepływem. Programowanie matematyczne 91 (3), 2002, 437–445. http://dx.doi.org/10.1007/s101070100259
• Alexander Schrijver. O historii optymalizacji kombinatorycznej (do 1960 r.). Handbook of Discrete Optimization, Elsevier, 2005. http://homepages.cwi.nl/~lex/files/histco.pdf

Większość ludzi podaje najstarszy algorytm graficzny Eulera z 1741 r. „Mosty z Królewca”. Niestety Euler tak naprawdę nie opisuje szczegółowo swojego algorytmu, ale podaje tylko pół-serce przykład:

„Gdy zostanie ustalone, że taka podróż może się odbyć, wciąż trzeba znaleźć sposób jej zorganizowania. W tym celu stosuję następującą zasadę: pozwól, aby te pary mostów, które prowadzą z jednego obszaru do drugiego, zostały mentalnie usunięte, tym samym znacznie zmniejszając liczbę mostów; wówczas łatwo jest zbudować wymaganą trasę przez pozostałe mosty. a mosty, które zostały usunięte, nie zmienią znacząco znalezionej trasy, co stanie się jasne po chwili namysłu. Nie uważam zatem, aby warto było podawać dalsze szczegóły dotyczące wyszukiwania tras. ”

Pierwszy kompletny dowód na to, że wszystkie połączone wykresy mają trasy Eulera, najwyraźniej wynika z faktu, że Heirholzer przeszło sto lat później.

• Leonhard Euler. Solutio problematis ad geometriam situs pertinentis. Commentarii academiae scientiarum Petropolitanae 8: 128–140, 1741. Przedstawiony Akademii Akademii w Petersburgu 26 sierpnia 1735 r. Przedruk w Operze 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.