Materiały dotyczące badań operacyjnych

Do zespołu Google ds. badań operacyjnych dołączają osoby z różnych środowisk. Niektórzy są doktoratami i są dobrze znani w danej dziedzinie, a inni to znakomite programiści z entuzjazmem do nauki optymalizacji matematycznej.

Czasami programiści pytają ekspertów LUB, by dowiedzieć się więcej. Zaczęliśmy zbierać odpowiedzi w dokumencie, którego fragment znajduje się poniżej. Są to opinie poszczególnych pracowników Google, a nie oficjalnych rekomendacji Google. Mamy nadzieję, że spodoba Ci się podsłuchiwanie naszej rozmowy zespołowej.

Masowe otwarte kursy online (MOOC)

Szkolenie	Autor	Uwagi	Komentarze
Zajęcia w serwisie Coursera dotyczące optymalizacji dyskretnej	van Hentenryck	MIP i CP	Kvothe@: Podoba mi się. Nie udało się jednak rozwiązać ostatniego zestawu problemów.
Modelowanie podstawowe na potrzeby optymalizacji dyskretnej	Lee & Stuckey	Większa koncentracja na CP
Zaawansowane modelowanie do optymalizacji dyskretnej	Lee & Stuckey
Rozwiązywanie algorytmów w celu optymalizacji dyskretnej	Lee & Stuckey
Modelowanie i rozwiązywanie problemów związanych z AI w Picat	Barták
LUB(1): Modele i aplikacje	Kung		Zaphod@: Te i kolejne 2 pozycje to świetne wprowadzenie do zagadnień związanych z LP/IP.
LUB(2): Algorytmy optymalizacji	Kung
OR(3): Teoria	Kung

Podstawy LP i MIP

Cover utworu	Tytuł	Autor	Komentarze
	Wprowadzenie do optymalizacji liniowej	Bertsimas i Tsitsiklis	BlackLotus@: Dla LP (i w mniejszym stopniu) uważam, że ta książka jest najlepsza. Patrick@: Głosuję na Bertsimas-Tsitsiklis, bo to raczej „drugi kurs” w programie linearnym. Najlepiej będzie, jeśli połączysz go z Wprowadzeniem do optymalizacji linearnej. BadBoy@: Muszę rzucić okiem na to. Zazwyczaj nie podoba mi się sposób, w jaki ci ludzie prezentują różne rzeczy, ale mogę się mylić. Kvothe@: Rozdziały 10 („formuły programowania liczb całkowitych”) i 11 („metody programowania liczb całkowitych”) są świetne.
	Programowanie liniowe	Vanderbei
	Optymalizacja kombinacyjna: wielohedra i skuteczność	Schrijver	SpiderWoman@: Pamiętam, że kiedyś podobała mi się „Optymalizacja kombinacyjna” Schrijvera, ale to bardzo matematyczne działanie, którego nie polecałabym na przykład osobie, która dołącza do zespołu...
	Teoria programowania liniowego i całkowitego	Schrijver	BadBoy@: Świetnie Ci się pokazać w bibliotece podczas wywiadu lub zrobić na kogoś wrażenie. Najprawdopodobniej nie przeczytasz go i nie spodoba Ci się, chyba że masz tytuł doktora w dziedzinie czystej, podwójnie oczyszczonej matematyki. Nie trzeba więc zaczynać od LP ani MIP. Pamiętaj jednak, że zawiera mnóstwo dowodów i interesujących informacji. Są to m.in. macierze całkowicie jednomodalne i co się na nich składają. Ponadto bibliografia zawiera niezwykle szczegółowe informacje i cytaty w oryginalnych językach. To swego rodzaju sztuka programowania komputerowego według Knuth. Tylko ten jest niestrawny. Kvothe@: Nie przeczytałem(-am) jej, ale nie ufam jej tylko na podstawie kroju czcionki.
	Pierwszy kurs optymalizacji liniowej	Jaś	Bezpłatne na licencji CC!
	Wprowadzenie do optymalizacji matematycznej	Fischetti	BadBoy@: Omówiłem wersję włoską. Wygląda bardzo dobrze. Ogólnie podoba mi się to, co robi Fischetti.
	Programowanie liniowe	Chvatal	BadBoy@: Nie lubię tej książki, ale dzięki niej nauczyłem się wszystkiego od LP, a zapis jest rewelacyjny.
	Optymalizacja kombinacyjna	Papadimitriou i Steiglitz	BadBoy@: Podoba mi się. Jest nieaktualna, ale warto ją przeczytać. Kvothe@: To trochę suche jak ja.
	Programowanie liczb całkowitych	Wolsey	Unicorn@: bardzo zwięzłe, ale obejmuje większość interesujących obszarów (z perspektywy rozwiązania)
	Programowanie liczb całkowitych	Conforti, Cornuéjols i Zambelli	Patrick@: To prawdopodobnie najbardziej aktualna książka o teorii i metodologii MIP.
	Aspekty optymalizacji kombinacyjnej	Jünger i Reinelt	Patrick@: Więcej w teorii Różne programy oparte na liczbach całkowitych: analiza postępu z 12 lat”.
	50 lat programowania liczby całkowitej: 1958–2008	Jünger i in., red.	Patrick@: Nieco nieaktualne, ale bardzo dobre omówienie historii i najnowocześniejszego systemu MIP.
	Algorytmy przepływu sieci	Williamson	Unicorn@: Dobra książka, która zawiera wiele najnowszych wyników na temat przepływów w sieci, a jednocześnie jest intuicyjna. Tylko w przypadku przepływów w sieci, więc nie tak ogólne. Dokładniejsza weryfikacja w języku francuskim.
	Oświetlone algorytmy: algorytmy do problemów o wartości NP-Hard	Ogrodowy ogród	Unicorn@: To pewnie nie jest najbardziej zaawansowana książka z tej serii. Jednak zawiera też wprowadzenie do niektórych algorytmów LUB (z perspektywy szkolenia dotyczącego algorytmów). Czytelna. Dokładniejsza weryfikacja w języku francuskim.
	Optymalizacja praktyczna	Gill, Murray i Wright	Unicorn@: Stara książka o ciągłej optymalizacji. Ta książka jest dla Ciebie przydatna, jeśli potrzebujesz wyjaśnień dotyczących tej rodziny algorytmów. (Dokładniejsza weryfikacja w języku francuskim).
	Wprowadzenie do optymalizacji i rachunku częściowego Hadamarda	Delfour	Unicorn@: Bardzo oficjalna książka na temat optymalizacji półróżnicowej. Nie jest łatwo się w nią zaangażować. Dokładniejsza weryfikacja w języku francuskim.
	Hierarchia Moment-SOS: wykłady z zakresu prawdopodobieństwa, statystyk, geometrii obliczeniowej, sterowania i nieliniowych PDE	Henrion, Korda i Lasserre	Unicorn@: Jeśli optymalizujesz kampanię za pomocą wielomianów lub zastanawiasz się, jak daleko z nimi dojść, zapoznaj się z podstawowymi informacjami o hierarchii SoS i nieznanymi aplikacjami. Dokładniejsza weryfikacja w języku francuskim.
	Wprowadzenie do badań operacyjnych	Hillier i Lieberman	Kvothe@: Dobre połączenie teorii i praktyki. Dobry pierwszy tekst dla osób, które dopiero zaczynają swoją przygodę, z ćwiczeniami i mnóstwem ćwiczeń, niektórymi z odpowiedziami na końcu książki. Wady: książka zbyt mocno stara się kierować użytkowników na swoją stronę i używa przestarzałych rozwiązań.

Sprawdź opinie

Opinia	Autor	Komentarze
175 lat programowania liniowego	Chandru i Rao	BadBoy@: To świetna seria artykułów. Zetknąłem się z tym w IBM na początku lat 90. Nie wiem, kto wpadł na pomysł prezentowania takich programów, ale zaangażowali się w to też Vijay Chandru i Jean-Louis Lassez. Dobrze jest to, że do zrozumienia tej funkcji wystarczy Ci jedynie podstawowa algebra liniowa, a także w przypadku LP możesz dowieść prawie każdego ważnego twierdzenia dotyczącego LP. Najlepiej byłoby przeczytać te książki na LP, z kilkoma Chvatal i vanderbei, a potem dodać odniesienia do odpowiednich książek i problemy z implementacją. Chvatal i Vanderbei nie mają solidnego podstaw matematycznych. Jest już stary i wkrótce zostanie nazwany 200 lat programowania liniowego. Możliwe, że były wcześniejsze próby.

Artykuły na temat badań

Artykuł	Autor	Komentarze
Nowy algorytm wielomianu czasu w programowaniu liniowym	Karmarkar	BadBoy@: Artykuł Karmarkar na temat algorytmu Karmarkar. Przykład pokazujący, jak nie należy pisać pracy. Przygotowanie skutecznej implementacji trwało lata, a w międzyczasie odkryli, że jest to kolejna metoda wewnętrznego punktu widzenia.

Modelowanie

MIP

Cover utworu	Tytuł	Autor	Komentarze
	Tworzenie modeli w programowaniu matematycznym	Williams	Skup się na LP i MIP. Temere@: Naprawdę nie podobało mi się. Ma dziwną strukturę (i sztucznie zwiększa liczbę stron). Jest mocno osadzona w „klasycznych zastosowaniach LUB” (skupia się na planowaniu gospodarczym lub na przykład przypominającym zabawkę), ale ma niewielką trafność w stosunku do modeli MIP, które zwykle stosujemy w Google Azalee@: Zgadzam się. BadBoy@: Wciąż uważam, że za czasów ta książka była świetna. Rzuciłem okiem na to ze 2 lata temu. Jest nieaktualny. Poza tym znam autora od 1990 roku i nawiązaliśmy ponowny kontakt na ISMP 2015. To świetny człowiek, na emeryturze podróżuje na konferencje poświęcone pieniądzom i nadal wygłasza świetne prezentacje. Jego prace były znakomite, zwłaszcza na temat eliminacji Fouriera. Ma bardzo szeroką wizję LP. Odegrał kluczową rolę we wprowadzeniu XpressMP.
	Zastosowania optymalizacji za pomocą XpressMP	Guéret, Prins, Sevaux i Heipcke

Przewodniki dotyczące modelowania udostępnione przez Solver

Przewodnik	Opis	Komentarze
Poradnik modelowania MOSEK	Analizuje optymalizację wypukłości stożkowych.	Jednorożec@ Prawdziwe informacje dla mnie przy modelowaniu nieliniowym.
Poradnik MOSEK dotyczący portfolio	Stożkowe modele do optymalizacji portfolio

Recenzje badań: MIP

Opinia	Autor	Opis
Mieszane techniki formułowania programowania liniowego liczb całkowitych	Wilma	Zwraca uwagę na siłę i rozmiar formuł z mieszaną liczbą całkowitą dla złączeń funkcji liniowych liniowych przypominających wielohedra. Więcej teoretycznie, ale w części 8 zastosowano kilka praktycznych metod, takich jak wzory przyrostowe.
Niewypukłe funkcje liniowe liniowy: zaawansowane formuły i proste narzędzia do modelowania.	Huchette i Vielma	Nowsze techniki dla jednostkowych funkcji liniowych, które nie zostały uwzględnione w omówieniu powyżej.

Opinie o badaniach: MINLP

Opinia	Autor	Opis
Reprezentatywność wypukła do liczb całkowitych o mieszanych	Lubin, Vielma i Zadik	Tylko dla relaksacji wypukłej.

Optymalizacja niepewna

Optymalizacja stochastyczna

Cover utworu	Tytuł	Autor	Komentarze
	Wykłady z programowania stochastycznego: modelowanie i teoria	Shapiro, Dentcheva i Ruszczyński
	Wprowadzenie do programowania stochastycznego	Birge i Louveaux	Unicorn@: Bardziej teoretyczne wprowadzenie do tematu. Nie polecam go tak bardzo jak wykładów o programowaniu stochastycznym.

Sprawdź opinie

Opinia	Autor
Optymalizacja warunkowej wartości zagrożonej	Rockafellar i Uryasev

Skuteczna optymalizacja

Cover utworu	Tytuł	Autor	Komentarze
	Skuteczna optymalizacja	Ben-Tal, El Ghaoui i Niemirowski	PDF. Unicorn@: przydatne informacje, jeśli poniższe opinie nie są wystarczająco szczegółowe. Znaczna część jest poświęcona problemom nieliniowym (zwykle nie omawianych w opiniach). Podoba mi się artykuł 1.1.2, ponieważ pokazuje on, że niewielkie odchylenia współczynnika mogą prowadzić do znacznej niewykonalności.
	Niezawodna i adaptacyjna optymalizacja	Bertsimas i Dick Den Hertog	PDF. Unicorn@: doskonałe materiały na temat skutecznej optymalizacji. Jest dość szczegółowa, ale może mieć większe zastosowanie przy algorytmach. Dokładniejsza weryfikacja w języku francuskim.

Sprawdź opinie

Opinia	Autor
Praktyczny przewodnik po skutecznej optymalizacji	Gorissen, Yanıkoğlu i den Hertog
Teoria i zastosowania solidnej optymalizacji	Bertsimas, Brown i Caramanis

Artykuły na temat badań

Artykuł	Autor
Dogłębna analiza stochastyczna w wysokich wymiarach z wykorzystaniem zaawansowanej optymalizacji (PDF)	Bandi i Bertsimas

StackExchange

Jakie książki stanowią dobry początek do badań operacyjnych?

Polecane książki i materiały do praktycznych zastosowań badań operacyjnych w branży