Śledzimy badania nad optymalizacją i współtworzymy open source

Optymalizacja zaczęła się jako problem planowania w czasie wojny i stała się dziedziną. Metoda simpleks pojawiła się w 1947 roku, a kolejnych piętnaście lat dało większość maszynerii działającej do dziś: programowanie dynamiczne, płaszczyzny tnące, podział i ograniczenia, najkrótsze ścieżki oraz dekompozycje pozwalające rozwiązać jeden duży problem jako serię małych.

Potem, w 1972 roku, Karp pokazał, dlaczego ta praca nigdy się nie skończy. Cała rodzina zwykłych problemów planistycznych nie ma znanego wydajnego algorytmu dokładnego i do dziś żadnego nie znaleziono. Odpowiedzią nie był jeden lepszy algorytm, lecz wiele, zapożyczonych zewsząd: symulowane wyżarzanie z metalurgii, przeszukiwanie tabu z pomysłu krótkiej pamięci, algorytmy genetyczne i optymalizacja mrowiskowa z biologii, programowanie z ograniczeniami z logiki, a przeszukiwanie dużego sąsiedztwa ze spostrzeżenia, że dobry plan zwykle dzieli od lepszego jedna drobna zmiana.

Żadna nie wygrała i o to właśnie chodzi. Każda jest mocna na kształcie problemu, z którym pozostałe radzą sobie źle, więc dziedzina zachowała je wszystkie i nauczyła się je łączyć: przeszukiwanie dokładne sterowane heurystykami, propagacja ograniczeń wsparta uczeniem klauzul, a od niedawna decyzje o podziale wyuczone z danych. Ostatnie lata dołożyły metody pierwszego rzędu i GPU, które otwierają na nowo programy liniowe w rozmiarach, do jakich metoda simpleks nigdy nie była przeznaczona.

W Julii pisze się dużą część współczesnych badań nad optymalizacją. Działa z prędkością, jakiej potrzebują solvery, i czyta się blisko matematyki, więc artykuł i jego implementacja pozostają rozpoznawalnie tym samym.

JuMP leży na wierzchu. Opisz problem raz, w składni bliskiej matematyce, a potem przekaż go jednemu z ponad 30 solverów za jednym interfejsem. To de facto standard w społeczności Julii i kręgosłup badań nad optymalizacją na uczelniach europejskich, w tym na UCLouvain, gdzie kształciła się część naszego zespołu.

Pracujemy nad nim, a nie tylko z nim. Członkowie zespołu zgłaszają pull requesty do pakietów rdzeniowych, utrzymują interfejsy solverów i prezentują na warsztacie JuMP-dev.

Zbudowane na