Nowe podejście oparte na danych może prowadzić do lepszych rozwiązań trudnych problemów optymalizacyjnych, takich jak globalne trasowanie paczek lub operacje sieci energetycznych. Chociaż Święty Mikołaj ma magiczne sanie i dziewięć dzielnych reniferów, aby pomóc mu dostarczać prezenty, firmy takie jak FedEx często wykorzystują specjalistyczne oprogramowanie do znalezienia rozwiązania problemu optymalizacji efektywnego trasowania świątecznych paczek.
To oprogramowanie, znane jako rozwiązujące programowanie liniowe z ograniczeniami całkowitoliczbowymi (MILP), dzieli duży problem optymalizacyjny na mniejsze części i używa ogólnych algorytmów, aby spróbować znaleźć najlepsze rozwiązanie. Jednak rozwiązanie może zająć godziny, a nawet dni.
Proces jest tak uciążliwy, że firma często musi zatrzymać oprogramowanie w połowie drogi, akceptując rozwiązanie, które nie jest idealne, ale najlepsze, jakie mogło zostać wygenerowane w ustalonym czasie.
Badacze z MIT i ETH Zurich wykorzystali uczenie maszynowe, aby przyspieszyć ten proces.
Zidentyfikowali kluczowy środkowy krok w solverach MILP, który ma tak wiele potencjalnych rozwiązań, że rozwiązanie go zajmuje ogromną ilość czasu, co spowalnia cały proces. Naukowcy zastosowali technikę filtrowania, aby uproszczać ten krok, a następnie użyli uczenia maszynowego, aby znaleźć optymalne rozwiązanie dla konkretnego typu problemu.
Ich podejście oparte na danych umożliwia firmie dostosowanie ogólnego solvera MILP do konkretnego problemu, wykorzystując własne dane.
Ta nowa technika przyspieszyła działanie solverów MILP o 30 do 70 procent, bez żadnego spadku dokładności. Można wykorzystać tę metodę do szybszego uzyskania optymalnego rozwiązania lub, w przypadku szczególnie skomplikowanych problemów, lepszego rozwiązania w rozsądnym czasie.
To podejście może być stosowane wszędzie tam, gdzie wykorzystuje się solver MILP, na przykład przez usługi przewożenia osób, operatorów sieci elektrycznych, dystrybutorów szczepionek, czy każdą inną jednostkę stojącą przed trudnym problemem alokacji zasobów.
„Problemy MILP mają wykładniczą liczbę potencjalnych rozwiązań. Na przykład, jeśli podróżujący sprzedawca chce znaleźć najkrótszą ścieżkę do odwiedzenia kilku miast, a następnie powrócić do swojego miasta pochodzenia. Jeśli jest wiele miast, które można odwiedzić w dowolnej kolejności, liczba potencjalnych rozwiązań może być większa niż liczba atomów we wszechświecie.
Badacze z MIT i ETH Zurich planują zastosować to podejście do jeszcze bardziej skomplikowanych problemów MILP, gdzie zebranie oznakowanych danych do szkolenia modelu może być szczególnie trudne. Może uda się im wyszkolić model na mniejszym zestawie danych, a następnie dostosować go do znacznie większego problemu optymalizacyjnego. Są również zainteresowani interpretacją wyuczonego modelu, aby lepiej zrozumieć skuteczność różnych algorytmów separatorów.
Badania te są wspierane częściowo przez Mathworks, National Science Foundation (NSF), MIT Amazon Science Hub oraz Komitet Wsparcia Badań MIT.
