Pozwolenie na ułamki może zmienić trudny problem w łatwiejszy
W programowaniu liniowym zmienne mogą przyjmować wartości rzeczywiste, a ograniczenia i funkcja celu są liniowe. Wiemy, że takie problemy można rozwiązywać w czasie wielomianowym. Wystarczy jednak dodać wymóg, aby zmienne były całkowite — na przykład 0 lub 1, bo maszyny nie można kupić „w 0,37 sztuki” — a ogólne programowanie całkowitoliczbowe staje się NP-trudne. To zaskakujący kontrast: równania mogą wyglądać prawie tak samo, lecz dyskretność rozrywa ciągłą przestrzeń rozwiązań na ogromny zbiór kombinacji. Z tego powodu relaksacja LP jest często używana jako narzędzie pomagające rozwiązywać trudne ILP, ale zaokrąglenie wyniku nie zawsze daje poprawne ani dobre rozwiązanie.
Geometria programowania liniowego
Program liniowy można wyobrazić sobie jako wielowymiarowy obszar wycięty przez półprzestrzenie określone nierównościami liniowymi. Zmienne poruszają się ciągle. Przełom Khachiyana z 1979 roku wykazał, że liniowe programowanie ma algorytm wielomianowy; później rozwinięto również inne wielomianowe metody, w tym rodzinę metod punktu wewnętrznego. To stwierdzenie dotyczy złożoności teoretycznej LP, niezależnie od tego, że w praktyce różne algorytmy mają bardzo różne osiągi.
Dyskretność zmienia krajobraz
W ILP część lub wszystkie zmienne muszą być całkowite. Zamiast dowolnego punktu w wielościanie można wybierać tylko punkty siatki. To pozwala naturalnie kodować decyzje „tak/nie”: x=1 oznacza wybranie elementu, x=0 jego pominięcie. Dzięki temu w ILP da się wyrażać problemy takie jak wybór zbioru wierzchołków, harmonogramowanie czy przydziały. Ta ekspresywność ma cenę — ogólne ILP jest NP-trudne.
Dlaczego proste zaokrąglenie nie wystarcza
Rozwiązanie relaksacji LP, w której chwilowo ignorujemy całkowitość, daje często wartości ułamkowe. Kuszące jest zaokrąglić każdą z nich. Jednak ograniczenia mogą sprawić, że taki krok łamie wykonalność albo mocno pogarsza funkcję celu. Przykładowo kilka zmiennych ułamkowych może wspólnie spełniać delikatny limit, a ich niezależne zaokrąglenie już nie. Potrzebne są bardziej wyrafinowane metody, takie jak branch-and-bound, cięcia czy specjalna struktura problemu.
LP jako kompas dla problemu całkowitego
Mimo różnicy złożoności rozwiązania LP są bardzo użyteczne. Relaksacja może dać ograniczenie na najlepszy możliwy wynik ILP i pomóc odcinać całe gałęzie wyszukiwania. Współczesne solvery optymalizacyjne intensywnie wykorzystują tę relację. „Łatwy” ciągły problem staje się więc narzędziem wewnątrz algorytmu dla trudniejszego problemu dyskretnego.
Jedna linia specyfikacji ma ogromne znaczenie
W modelu biznesowym różnica między x≥0 a x∈Z może wyglądać jak szczegół domeny zmiennej. Dla teorii algorytmów jest to zmiana fundamentalna. Pokazuje, że granice obliczeń nie wynikają wyłącznie z liczby równań: często decyduje geometria przestrzeni dopuszczalnych rozwiązań i to, czy decyzje mogą zmieniać się płynnie, czy skaczą między dyskretnymi opcjami.
Dlaczego relaksacja LP jest tak użyteczna
Jeżeli z problemu całkowitoliczbowego usuniemy warunek x∈Z i pozwolimy zmiennym przyjmować wartości rzeczywiste, otrzymujemy relaksację liniową. Dla problemu maksymalizacyjnego jej optimum może być lepsze niż jakiekolwiek dopuszczalne rozwiązanie całkowite, bo przeszukujemy większy zbiór punktów. To daje użyteczne ograniczenie: wiemy, że prawdziwe optimum ILP nie może przekroczyć wartości relaksacji. Algorytmy branch-and-bound wykorzystują takie granice do odcinania części drzewa poszukiwań, które nie mogą już poprawić najlepszego znalezionego rozwiązania całkowitego. Dzięki temu problem NP-trudny często da się rozwiązać praktycznie, choć w najgorszym przypadku drzewo nadal może eksplodować. LP nie usuwa trudności ILP, ale staje się narzędziem do jej kontrolowania.