Chociaż programowanie liniowe z mieszanymi liczbami całkowitymi (MILP) jest rzeczywiście zakończone NP, istnieją możliwe do rozwiązania (nietrywialne) przypadki programowania liniowego z mieszanymi liczbami całkowitymi.
NP-complete oznacza, że programowanie liniowe o mieszanej liczbie całkowitej jest:
a) możliwe do rozwiązania w czasie wielomianowym za pomocą niedeterministycznej maszyny Turinga (część NP)
b) czas wielomianowy redukowany do 3-SAT (cała część; dla reszty dyskusji ta część naprawdę nie ma znaczenia)
W praktyce, ponieważ nie mamy niedeterministycznych maszyn Turinga i nie jesteśmy w stanie napisać algorytmów, które wykonują takie czynności: „ustaw nasze binarne zmienne decyzyjne na wszystkie możliwe kombinacje zera i jednego i rozwiąż powstałe programy liniowe (LP)” w czas wielomianowy, co oznacza, że w sensie asymptotycznym MILP to , gdzie jest liczbą zmiennych binarnych. To stwierdzenie oznacza, że ponieważ przypadki problemów stają się bardzo duże, będą one wymagały dużych mocy obliczeniowych do rozwiązania.nO(2n)n
To stwierdzenie nie oznacza, że „małe” wystąpienia są trudne do rozwiązania. Niestety nie mogę precyzyjnie określić, jakie małe znaczenie ma instancja MILP. Rutynowo rozwiązuję problemy z 3000 lub więcej binarnymi zmiennymi decyzyjnymi. W zależności od sformułowania problemu problemy mogą trwać krócej niż 0,01 sekundy (co ma miejsce w przypadku problemów o stosunkowo ograniczonym ograniczeniu) lub ponad godzinę (co ma miejsce w przypadku problemów, w których występuje wiele ograniczeń), ponieważ problemy wydają się mieć korzystną strukturę. Mogę powiedzieć, że najnowocześniejsze solwery LP mogą rozwiązywać LP przy pomocy kilku milionów zmiennych ciągłych decyzji i że bez specjalnej struktury jest bardzo mało prawdopodobne, że wystąpi problem z około 1000 do 10,
Jeśli uważasz, że masz możliwe do rozwiązania wystąpienie MILP, zechcesz użyć algorytmu odgałęzionego lub odgałęzionego. Najlepsze wdrożenia to CPLEX i Gurobi . Oba są produktami komercyjnymi, które mają bezpłatne licencje akademickie, jeśli będziesz wystarczająco kopać. Jeśli naprawdę potrzebujesz solvera typu open source, projekty w społeczności COIN-OR są bardziej odpowiednie, chociaż czasami pakiety źródłowe mogą być trudne. Najbardziej istotne projekty byłoby CBC branch-and-cut solver , solver SYMPHONY , solver BCP oddział-cut-cena i solver ABACUS branch-and-cut . Wszystkie te projekty będą wymagały wielu pakietów od COIN-OR, ze względu na jego modułową budowę.
Jeśli chcesz wypróbować wiele solverów, najlepiej postawić na interfejs Open Solver firmy COIN-OR . Należy pamiętać, że części tego interfejsu pozwalają jedynie ustawić podstawowe opcje solvera i że aby ustawić zaawansowane opcje solverów, należy zapoznać się z listami mailowymi COIN-OR w celu uzyskania dalszych szczegółów. Komercyjne solpery MILP są DUŻO (czasem o rząd wielkości lub więcej) szybsze niż solwery open source. Inną opcją prototypowania jest użycie algebraicznego języka modelowania, takiego jak GAMS lub AMPL . Oba pakiety oprogramowania są komercyjne, ale mają wersje próbne, które mogą być używane w przypadku małych problemów. W przypadku większych problemów możesz przesłać pliki GAMS lub AMPL doSerwer NEOS do rozwiązania; ten serwer jest dostępny publicznie.
Jeśli masz wystarczająco dużą instancję MILP, żaden z tych solverów nie będzie działał dobrze. Można rozluźnić zmienne całkowite na zmienne ciągłe, rozwiązać problem, a następnie zaokrąglić do najbliższej kolekcji zmiennych całkowitych, która jest wykonalnym rozwiązaniem wystąpienia problemu. Optymalne rozwiązanie relaksacji LP twojej MILP da ci dolną granicę optymalnej wartości funkcji celu MILP (oczywiście przy założeniu minimalizacji), a wykonalne rozwiązanie twojej MILP da ci górną granicę optymalnego celu wartość funkcji Twojej MILP.
Jeśli naprawdę masz szczęście, a macierz ograniczeń jest całkowicie niemodularna , możesz użyć solwera LP do generowania liczb całkowitych rozwiązań dla MILP i możesz skutecznie rozwiązać problem pomimo jego dużych rozmiarów. Inne klasy problemów mają szybkie algorytmy aproksymacyjne, takie jak problemy z plecakiem i problemy z zapasem . Specjalistyczne algorytmy dekompozycji MILP istnieją również dla problemów o specjalnej strukturze, chociaż nie znam szczegółów, ponieważ tematy te są nieco wyspecjalizowane i nie są objęte zakresem mojej pracy magisterskiej.
Nie jestem świadomy w pełni wielomianowego schematu aproksymacji czasu (FPTAS) specjalnie dla MILP, chociaż istnieje FPTAS klasy problemów, która obejmuje MILP (zobacz ten artykuł). Radziłbym zastosować jeden z powyższych solverów programowania liniowego o mieszanej liczbie całkowitej w połączeniu z ograniczeniem czasowym i odpowiednimi tolerancjami dla luk optymalizacyjnych. W ten sposób uzyskasz najlepsze możliwe rozwiązanie MILP w wyznaczonym terminie, a jeśli solver zakończy się pomyślnie przed upływem terminu, możliwe rozwiązanie będzie optymalne w granicach tolerancji luki optymalności, którą ustawisz. Taki sposób postępowania nadal dawałby ci ograniczenia w zakresie jakości rozwiązania, ponieważ twoje wykonalne rozwiązanie byłoby górną granicą, a solver mógłby dać ci odpowiednią dolną granicę. Nie można zagwarantować, że granica znajdzie się w zakresie optymalnego rozwiązania określonego czynnika, ale z drugiej strony każdy FPTAS stanie się droższy w miarę poprawy aproksymacji.
Najważniejszą rzeczą, jaką możesz zrobić, zanim zdecydujesz się na preparat MILP, jest wybranie najsilniejszego preparatu, jaki możesz znaleźć; porady dotyczące doboru silnych receptur można znaleźć we wstępie do optymalizacji liniowej autorstwa Bertsimasa i Tsitsiklisa. Główną ideą jest wybranie formuły, której ograniczenia definiują polytop, który jest jak najbliżej wypukłego kadłuba formuły, jak to możliwe (patrz także te uwagi do kursu ). Wybór silnego preparatu może mieć ogromną różnicę w czasie potrzebnym do rozwiązania problemu.