Jakie jest najszybsze oprogramowanie (open source) do rozwiązania problemu programowania mieszanych liczb całkowitych

Mam problem z programowaniem liczb całkowitych mieszanych. Obecnie używam GLPK jako mojego solwera. Odkryłem jednak, że GLPK jest dobry dla problemu programowania liniowego, ale dla programowania mieszanych liczb całkowitych wymaga dużo dłuższego czasu, dlatego nie spełnia naszych wymagań. Tak bardzo szukam innego oprogramowania. Czy istnieją inne dobre narzędzia typu open source do rozwiązywania problemów programowania mieszanych liczb całkowitych z dużą prędkością? Dzięki!

Jeśli chcesz czegoś open-source, prawdopodobnie chcesz wypróbować kod CBC COIN (mają również kilka innych solverów MILP, takich jak framework rozgałęzienia i ceny lub SYMPHONY).

Gurobi i CPLEX będą znacznie szybsze, a od spotkania INFORMS w 2011 lub 2012 r. Gurobi był szybszy niż CPLEX (choć wskaźniki wydajności są oczywiście zależne od problemu). W przypadku MILP rozwiązanych w mojej pracy Gurobi był około 15-100 razy szybszy niż CBC, a CPLEX był prawie tak szybki jak Gurobi, ale bardzo nieznacznie wolniejszy (jak 12-80 razy szybszy).

Chociaż najgorszy przypadek jest rzeczywiście wykładniczy, czas wykonania zależy w dużej mierze od struktury problemu. Jest mało prawdopodobne, że będziesz w stanie rozwiązać MILP z milionami zmiennych, chyba że wykorzystasz specjalną strukturę (może jeśli jest to program stochastyczny, który można rozłożyć na wiele znacznie mniejszych problemów), ale całkowicie możliwe jest rozwiązanie nietrywialnych MILP z tysiącami zmienne w mniej niż minutę. (Oczywiście rozwiązanie tych problemów może potrwać godzinę lub dłużej.)

Jak zauważa Brian Borchers, zarówno CPLEX, jak i Gurobi mają bezpłatne licencje dla niektórych badaczy, jeden z tych dwóch pakietów oprogramowania byłby naprawdę najlepszy do użycia jako uniwersalny solver MILP.

Problemy programowania liniowego o mieszanych liczbach całkowitych są znacznie trudniejsze do rozwiązania niż problemy programowania liniowego. Pod względem złożoności obliczeniowej LP można rozwiązać w czasie wielomianowym, podczas gdy rozwiązywanie MILP jest problemem trudnym dla NP. Znane algorytmy rozwiązywania MILP mają wykładniczą najgorszą złożoność.

Istnieją inne pakiety oprogramowania do programowania liniowego z mieszanymi liczbami całkowitymi, na które można spojrzeć, w tym SCIP (bezpłatny do użytku akademickiego), CPLEX (komercyjny, ale z opcją licencjonowania akademickiego) i GUROBI (również komercyjny z opcją licencjonowania akademickiego.) Jeden lub więcej z tych pakietów może być znacznie szybszy niż GLPK na twoich problemach, ale nie oczekuj, że którykolwiek z nich będzie tak samo szybki w rozwiązywaniu MILP, jak w rozwiązaniu LP o podobnych rozmiarach.

Jeśli chcesz wypróbować kilka różnych solverów, wypróbuj model JulMP JuMP . Pozwala napisać model jako model JuMP, a następnie zamienić solwery za pomocą jednego wiersza kodu. Na przykład w przypadku problemów z MILP możesz wybrać solwery Bonmin, Cbc, Couenne, CPLEX, GLPK, Gurobi i MOSEK. Z tego powodu, jeśli napiszesz go w JuMP, możesz po prostu wypróbować wszystkie solwery, o których wspomniał Geoff i zobaczyć, co działa bez konieczności pisania wiązki kodu. Twoje osobiste testy będą najlepszym źródłem wiedzy na temat najszybszych algorytmów dla twoich problemów.

Zgodnie z sugestiami innych użytkowników, wykorzystałem GAMS (komercyjny) do wielu projektów. To jest bardzo proste; wszystko co musisz zrobić, to matematyczne sformułowanie swojego problemu. Odbiera zmienne, ograniczenia, funkcje celu i wszystkie dane wejściowe. Następnie zapewnia szereg solverów (optymalizatorów) dla każdego przypadku. W zależności od przypadku dodajesz bardziej wyrafinowane rozwiązania.

Z pewnością EASY jest warte obejrzenia. Framework open source.

Termin „szybki” jest bardzo niejasny! Musisz być bardziej szczegółowy; Szybki pod względem liczby iteracji? liczba ocen? upłynął czas? kombinacja tych?

Jeśli jednak nie szukasz oprogramowania i chcesz po prostu rozwiązać problem, mógłbym zasugerować użycie globalnego optymalizatora NSGA-II, który jest optymalizatorem open source o bardzo wysokiej reputacji i wydajności.

Jeśli dostarczyłeś więcej informacji, mógłbym dokładnie poprowadzić.