Zaawansowane rozwiązania LP

Pomimo dojrzałości technologii LP niektóre przypadki użycia wymagają bardziej zaawansowanych metod. Na przykład dostępnych jest wiele różnych algorytmów i implementacji LP, z których każdy ma swoje mocne i słabe strony. Poza tym niestabilność liczbowa może spowolnić działanie niektórych modeli lub sprawić, że nie będą one działać prawidłowo.

W tym przewodniku omawiamy pojęcia oraz przykłady, które pomagają uzyskać maksymalną skuteczność i niezawodność rozwiązań LP.

Pojęcia

W tej sekcji omawiamy kluczowe zagadnienia dotyczące zaawansowanego korzystania z rozwiązań do rozwiązywania problemów. Zakładamy, że czytelnicy znają koncepcję duowości w LP.

Rodziny algorytmów LP

Poniższe klasy algorytmów dla LP są dostępne za pośrednictwem narzędzi LUB.

  1. Pierwszym praktycznym algorytmem LP był algorytm Simplex, który pozostaje najpopularniejszy. Algorytm porusza się wzdłuż wierzchołków (punktów na rogach) możliwego regionu, iteracyjnie poprawiając wartość funkcji docelowej aż do znalezienia optymalnego rozwiązania. Istnieją 2 rodzaje algorytmów prostego użycia:

    1. Pierwotny pospolity wykonuje kroki wzdłuż wierzchołków pierwotnego wykonalnego regionu. Ten wariant jest szczególnie skuteczny w rozwiązywaniu problemów LP o różnych funkcjach, tj. w przypadku, gdy ustalany jest podstawowy region wykonalny.
    2. Podwójny jednorazowy wykonuje kroki wzdłuż wierzchołków podwójnego możliwego regionu. Ten wariant jest szczególnie skuteczny w rozwiązywaniu problemów LP, gdy podwójny możliwy region jest stały, np. gdy zmieniają się tylko granice zmiennych. Z tego powodu w rozwiązaniach MIP często używa się funkcji podwójnych jednorazowych.

  2. Metody barier i interior-point to druga praktyczna rodzina algorytmów do LP. Metody barierowe łączą teoretyczne gwarancje sprawnej zbieżności (czasu wielomianowego) z niezawodnością w praktyce. Uzupełniają algorytm jednostajny, jeśli jest nieskuteczny. Niektóre rozwiązania oferują na przykład jednoczesne uruchamianie algorytmu jednokierunkowego i barierowego, zwracając rozwiązanie z algorytmu, który kończy działanie jako pierwsze.

  3. Metody pierwszego rzędu to rodzina algorytmów, które używają wyłącznie informacji gradientowych (czyli pochodnych pierwszego rzędu) do kierowania iteracją. Dobrze znanym przykładem jest spadek gradientowy. Są one popularne w optymalizacji nieliniowej i systemach uczących się. W przypadku LP metody pierwszego rzędu mogą skalować się do większych problemów niż metody prostego i barierowego. Mogą też mieć znacznie mniejsze wymagania dotyczące pamięci. Poza tym są one bardziej wrażliwe na problemy liczbowe i mogą mieć trudności z opracowaniem bardzo dokładnych rozwiązań.

W tabeli poniżej znajdziesz listę rozwiązań problemów niestandardowych dostępnych w narzędziach LUB oraz wskazuje, które z 3 grup algorytmów są zaimplementowane w poszczególnych z nich.

Rozwiązania matematyczne Prosty Barierka Pierwsze zamówienie
Clp X X
CPLEXL X X
GlopG X
PKP X X
GurobiL X X
PDLPG X
XpressL X X

G oznacza, że rozwiązanie zostało opracowane przez Google. L oznacza, że narzędzie do rozwiązywania problemów wymaga licencji wydanej przez odpowiedniego dewelopera zewnętrznego.

W sekcji Rekomendacje znajdziesz sugestie dotyczące rozwiązań i algorytmów, których należy użyć.

Co tak naprawdę oznacza rozwiązywanie?

Aby w pełni wykorzystać potencjał rozwiązań LP, trzeba wiedzieć, co oznacza, że znalazł rozwiązanie danego zadania. Ta sekcja zawiera podstawowe informacje niezbędne do udzielenia odpowiedzi na to pytanie, w szczególności ze względu na niedokładność liczbową i niepowtarzalność rozwiązań.

Tolerancje

Rozwiązania tego typu prawie zawsze stosują arytmetyczną liczbę zmiennoprzecinkową, co powoduje, że ich rozwiązania podlegają niedokładności liczbowej. Aby to uwzględnić, a także poprawić skuteczność przez unikanie prac nad rozwiązaniami, które są już wystarczająco dobre, osoby te akceptują rozwiązania i twierdzą, że rozwiązały problem, gdy spełniają warunki do określonej tolerancji.

Przeanalizuj problem z programowaniem liniowym

$$ \begin{align*} \min\quad & -2x_1 - x_2 \\ \text{s.t.}\quad& x_1 + x_2 \le 1\\ & x_1, x_2 \ge 0 \end{align*} $$

i odpowiadający mu podwójny problem

$$ \begin{align*} \max\quad& y \\ \text{s.t.}\quad& -2 - y \ge 0\\ &-1 - y \ge 0 \\ &y \le 0 \end{align*} $$

Ta para zadań ma unikalne optymalne rozwiązanie wstępne o wartości 1 zł x_1 = 1, x_2 = 0 $, a rozwiązanie podwójne $ y = -2 $. Które rozwiązania można zaakceptować jako optymalne przez rozwiązanie? Aby odpowiedzieć na to pytanie, definiujemy następujące ilości:

  • Luka podwójnych celów to różnica między wartością pierwotnego celu a wartością podwójnego celu, w tym przypadku $ |(-2x_1 - x_2) - y| $.
  • Podstawowe niemożliwości to naruszenia podstawowych ograniczeń, w tym przypadku $ (\max\{ (x_1+x_2) - 1, 0 \}, \max\{-x_1, 0\}, \max\{-x_2, 0\}) $.
  • Podwójne niemożliwości to naruszenie podwójnych ograniczeń, w tym przypadku $ (\max\{ 2 + y, 0 \}, \max\{ 1 + y, 0 \}, \max\{ y, 0 \}) $.

Rozwiązanie określa rozwiązanie jako optymalne, jeśli luka dwukierunkowa, pierwotne niemożliwości i podwójne niemożliwości są mniejsze niż podana tolerancja1.

W szczególności zastosowanie tolerancji różni się w przypadku rozwiązań i algorytmów zarówno z przyczyn naturalnych, jak i idiosynchronicznych. Na przykład luka dwukierunkowa w algorytmie jednokrotnym jest zależna wyłącznie od niedokładności liczbowej, podczas gdy podstawowe i podwójne niedokładności występują nawet w arytmetycznych równaniach ścisłych. Niektóre metody bezpośrednio egzekwują ograniczenia granic $ x_1 \ge 0, x_2 \ge 0, $ oraz $ y \le 0 $ $, a inne traktują naruszenia ograniczeń granicznych inaczej niż $x_1 \ge 0 \le 1$. W przypadku niektórych rozwiązań, których rozwiązania są skuteczne, a metody x_2 \ge 0, $ i $ y \le 0 $, wszystkie traktują naruszenia ograniczeń granicznych inaczej od naruszeń ograniczeń liniowych, np. $x_1 + x_2 \le 1$. W przypadku niektórych rozwiązań argumenty „duży rozmiar” i „dużliwości” wartości są bezwzględne.

Przykładem efektu tolerancji jest bezwzględna tolerancja w wysokości $ \epsilon = \frac{1}{2} $ zastosowana do powyższej pary podwójnej pierwiastków. Rozwiązanie: $ x_1 = 1,5, x_2 = 0, y = -3 $ ma zerową lukę dwukierunkową i brak możliwości, które są mniejsze lub równe $ \epsilon $, dlatego rozwiązanie może określić to rozwiązanie jako „optymalne”. Jednak jej wartość docelowa (-3) różni się o 1 od rzeczywistej optymalnej wartości celu -2. Typowe wartości domyślne $ \epsilon $ mieszczą się w zakresie od 10^{-6}$ do 10^{-8}$, co sprawia, że takie skrajne przykłady są rzadkie, ale nie możliwe.

Typy rozwiązań

Rozwiązania problemów LPG mogą mieć więcej niż 1 optymalne rozwiązanie, tym bardziej przy uwzględnieniu tolerancji. Omówimy pokrótce właściwości rozwiązań zwracanych przez 3 różne rodziny algorytmów LP.

Algorytmy jednorazowe zawsze zwracają wierzchołki lub punkty narożne możliwego regionu. W niektórych sytuacjach preferowane są rozwiązania te, ponieważ są zwykle oszczędne.

Metody bariery i metody pierwszego rzędu zwykle nie zwracają wierzchołków. (Teoria zawiera dodatkowe cechy, które wykraczają poza zakres tego przewodnika).

Ze względów historycznych i ze względu na to, że rozwiązania wierzchołkowe mają atrakcyjne właściwości, rozwiązania do rozwiązywania problemów często domyślnie stosują procedurę crossover, aby przejść do optymalnego wierzchołka z rozwiązania wykrytego przez algorytm bariery. Crossovery nie są obecnie oferowane w przypadku rozwiązań znalezionych za pomocą metod pierwszego zamówienia.

Rekomendacje

Poniżej znajdziesz zalecenia dotyczące zaawansowanego korzystania z rozwiązań LP.

Skalowanie danych problematycznych

W przypadku mechanizmów rozwiązywania problemów może dojść do powolnej zbieżności lub awarii modeli z powodu problemów liczbowych. Powodów takich problemów może być wiele – podajemy tu jeden z przykładów.

W modelach LP często występują bardzo małe lub duże stałe liczbowe. Rozszerzając przykład z powyższego przykładu, \(x_1\) i \(x_2\) reprezentują oni odsetek klientów przypisanych do „dostawcy 1” lub „dostawcy 2”. Jeśli chcemy zmaksymalizować korzyści z obsługi tych klientów, możemy napisać tę funkcję celową:

$$ \min -c_1x_1 - c_2x_2 $$

gdzie:

  • $ c_1 $ to korzyść z przypisania klientów do usługodawcy 1
  • $ c_2 $ to korzyść z przypisania klientów do usługodawcy 2

Podwójne spełniające te ograniczenia są uznawane za możliwe z bezwzględną tolerancją $ \epsilon $:

  • $ y \le -c_1 + \epsilon $,
  • $ y \le -c_2 + \epsilon $.

Jeśli jednostki korzyści w wymiarach $ c_1 $ i $ c_2 $ są niewielkimi wartościami ułamkowymi, które występują w tej samej skali co $ \epsilon $, to podwójne warunki wykonalności stają się raczej słabe, więc tę najbardziej nieoptymalną można uznać za optymalny.

Jeśli natomiast jednostkami korzyści są „mikrodolary” (1 000 000 mikrodolarów = 1 dolar), wynikowe bardzo duże wartości bezwzględne wymagają bardzo dużej dokładności rozwiązania, która może być nieuzasadniona ze względu na ograniczenia liczb zmiennoprzecinkowych. Jeśli problem zostanie sformułowany w ten sposób, rozwiązania do rozwiązywania problemów mogą nie udać się osiągnąć rozwiązania. W ramach formułowania dobrze postawionego zadania twórcy modeli zaawansowanych powinni wziąć pod uwagę, czy dane problemu są skalowane w sposób zgodny z tolerancjami ich rozwiązań.

Aby uniknąć błędów liczbowych, można też dostosować tolerancje w celu uzyskania lepszej wydajności. Metody proste i barierowe nie są zbyt wrażliwe na tolerancję, ale czasami mogą mieć większą tolerancję, jeśli postępy w rozwiązywaniu problemu zatrzymują się na końcu. Z drugiej strony metody pierwszego rzędu są zwykle dużo bardziej czułe. Użytkownicy metod pierwszego rzędu mogą skorzystać na szybszych rozwiązaniach przez rozluźnienie tolerancji (w zależności od kontekstu).

Informacje o tolerancjach Glop znajdziesz tutaj: primal_feasibility_tolerance, dual_feasibility_tolerance i solution_feasibility_tolerance w artykule GlopParameters. Zwróć uwagę, że w algorytmie używane są primal_feasibility_tolerance i dual_feasibility_tolerance, a pole solution_feasibility_tolerance jest zaznaczone po rozwiązaniu do oznaczania problemów liczbowych. PDLP: eps_optimal_absolute i eps_optimal_relative.

Więcej informacji na temat tego typu problemów znajdziesz w opracowanym przez Gurobi wytycznych dotyczących problemów liczbowych. Chociaż wytyczne zostały opracowane z myślą o użytkownikach Gurobi, wiele z nich ma zastosowanie ogólnie.

Wybór rozwiązań i algorytmów

Najpierw pokazujemy, jaki wpływ może mieć wybór rozwiązań i algorytmów. Następnie przedstawiamy wskazówkę dotyczącą wyboru odpowiednich rozwiązań.

Zmienność w praktyce

Aby pokazać zmienność skuteczności algorytmów i rozwiązań LP, porównujemy czasy rozwiązania na wybranych instancjach używanych przez Hansa Mittelmanna do testów porównawczych rozwiązań LP. Instancje są bezpośrednio wybierane do pokazania ekstremalnych wartości względnej wydajności i nie muszą być reprezentatywne dla typowego zachowania.

Podstawowe i podwójne metody prostego Glop porównywane są z metodą barierową Gurobi (z crossoverem, która znajduje rozwiązanie wierzchołkowe), a metodą PDLP (pierwszego rzędu) z dużą i małą precyzją. W tabeli poniżej znajdziesz czasy rozwiązywania w sekundach z limitem 20 minut (1200 sekund).

Instancja Okrąg
Primal Simplex		 Glop
Dual Simplex		 Gurobi Barrier
ze zwrotem		 Bariera Gurobi
bez crossovera		 Wysoka dokładność
PDLP		 Mała dokładność
PDLP
ex10 >1200 >1200 79.7 63.5 8.2 2.7
nug08-3rd >1200 252.8 144,6 3.2 1.1 0,9
savsched1 >1200 >1200 156.0 22,6 46.4 32.4
wide15 >1200 20,8 >1200 >1200 916,4 56.3
energia budowania 178.4 267.5 12,8 12.3 >1200 157.2
S250R10 12.1 520.6 15.2 16.4 >1200 >1200
Wersja rozwiązania Solver OR-Narzędzia 9.3 OR-Narzędzia 9.3 Gurobi 9.0 Gurobi 9.0 OR-Narzędzia 9.3 OR-Narzędzia 9.3
solver_specific_parameters (wartości domyślne) use_dual_simplex: true Method 2, Threads 1 Method 2, Crossover 0, Threads 1 termination_criteria { eps_optimal_absolute: 1e-8 eps_optimal_relative: 1e-8 } termination_criteria { eps_optimal_absolute: 1e-4 eps_optimal_relative: 1e-4 }

Na podstawie tych wyników wyciągnęliśmy następujące wnioski.

  • Względna wydajność algorytmów i rozwiązań może w każdej instancji różnić się o porządek wielkości.
  • Żaden algorytm ani żadne rozwiązanie nie jest jednakowo lepsze od innych.
  • Crossover (domyślnie włączony) wydłuża czas rozwiązywania problemu, niekiedy nawet znacznie.
  • PDLP pomaga w rozwiązywaniu problemów z małą precyzją czasami 10 razy szybciej niż przy wysokiej dokładności.

Krótki przewodnik po rozwiązywaniu problemów docelowych

Ponieważ żaden algorytm LP nie sprawdza się najlepiej w Twoim przypadku, zalecamy wykonanie podanych niżej czynności. Zacznij od pierwszego kroku, a jeśli wydajność jest niewystarczająca, przejdź do następnego.

  1. Wypróbuj Glop. Uzasadnienie: Glop to własna implementacja Google metod podstawowych i podwójnych. Glop to oprogramowanie open source, którego można używać do przetwarzania zadań produkcyjnych Google.
    • Jeśli konfiguracja domyślna (pierwotna prosta konfiguracja) nie działa dobrze, spróbuj przełączyć się na podwójny jednorazowy za pomocą funkcji use_dual_simplex: true.
  2. Jeśli licencja jest dostępna, wypróbuj komercyjne rozwiązanie (CPLEX, Gurobi lub Xpress). Eksperymentuj z metodami jednokrotnymi i metodami barierowymi. Uzasadnienie: te rozwiązania są standardem branżowym i wysoce zoptymalizowane. Poza tym metody barierowe uzupełniają algorytmy jednorazowe oferowane przez Glop.
    • Jeśli używasz bariery, wyłącz tryb „crossover”, jeśli nie potrzebujesz rozwiązania wierzchołka.
  3. Wypróbuj PDLP. Dostrój tolerancje zbieżności do swojej aplikacji. Uzasadnienie: PDLP powstał z myślą o największych problemach, w których metody proste i barierowe prowadzą do przekroczenia limitów pamięci lub są zbyt wolne. PDLP działa najlepiej, gdy preferowane jest rozwiązanie przybliżone, ale szybkie niż rozwiązanie dokładne, ale powolne.
  4. Jeśli udało Ci się dotrzeć tak daleko, jesteś już zaawansowanym użytkownikiem LP! Aby uzyskać dalszą pomoc, zapoznaj się z opcjami pomocy w narzędziu LUB.

  1. Zwykle jest to bardziej złożone. Rozwiązania te zwykle sprawdzają te warunki w przekształconej/uproszczonej wersji zadania, która jest nazywana presolved. W niektórych przypadkach rozwiązanie rozwiązanego problemu może być daleko od rozwiązania problemu z danymi wejściowymi. Może to prowadzić do nietypowych stanów, takich jak OptimalInfeas CPLEX lub IMPRECISE Glop.↩