Naukowcy z arXiv zaproponowali metodę Graph Edge Sparsification (GES) - uczące się podejście do zmniejszania grafów w problemie komiwojażera. W przeciwieństwie do tradycyjnych metod sparsyfikacji, które opierają się na stałych heurystykach, GES adaptacyjnie dostosowuje się do struktury każdego konkretnego problemu, łącząc informacje geometryczne z technikami optymalizacji kombinatorycznej.
Problem komiwojażera (TSP) polega na znalezieniu najkrótszej ścieżki odwiedzającej wszystkie punkty i powracającej do startu - jego dokładne rozwiązanie dla dużych instancji jest obliczeniowo bardzo kosztowne. Tradycyjne metody zmniejszania rozmiary grafów nie w pełni wykorzystują strukturalnych cech poszczególnych instancji, co ogranicza ich efektywność. GES rozwiązuje ten problem ucząc się, które krawędzie są najmniej istotne dla rozwiązania.
Experymenty wykazują imponujące rezultaty: na zbiorze danych MATILDA metoda usunęła do 95% krawędzi przy zachowaniu błędu rozwiązania poniżej 1% od optimum, co znacznie przyspiesza obliczenia. Jeszcze bardziej zaskakujące są wyniki na benchmarku TSPLIB - dla niektórych dużych instancji wskaźnik przycięcia przekroczył 99%, a rozwiązanie wciąż pozostało w granicach 1% od optimum. Silna generalizacja metody na różnych benchmarkach sugeruje, że podejście może być praktycznie użyteczne dla rzeczywistych problemów optymalizacyjnych, gdzie szybkość jest krytyczna.