Minimalne maksymalne rozwiązania LP

Programowanie liniowe jest oczywiście obecnie bardzo dobrze rozumiane. Mamy dużo pracy, która charakteryzuje strukturę wykonalnych rozwiązań i strukturę rozwiązań optymalnych. Mamy silną dualność, algorytmy wielogodzinne itp.

Ale co wiadomo na temat minimalnych maksymalnych rozwiązań LP? Lub równoważnie maksymalne minimalne rozwiązania?

(To nie jest tak naprawdę pytanie badawcze, ale może możemy mieć coś mniej technicznego na święta. Po prostu jestem ciekawy, a po jakimś googlowaniu mam wrażenie, że brakuje mi odpowiednich słów kluczowych. To wydaje się oczywiste problem do studiowania, ale znalazłem tylko niektóre sporadyczne artykuły, które wspominają o tym problemie)

Dla uproszczenia skupmy się na pakowaniu i pokrywaniu płyt LP . W LP pakowania daje nam nieujemną macierzy . Wektor jest wykonalny, jeśli i . Mówimy, że jest maksymalne, jeśli jest wykonalne i nie możemy łapczywie zwiększać żadnego składnika. Oznacza to, że jeśli i , to nie jest wykonalne. I wreszcie jest minimalnym maksymalnym rozwiązaniem, jeśli minimalizuje funkcję celu $A$ $x$ $x \ge 0$ $Ax \le 1$ $x$ $y \ge 0$ $y \ne 0$ $x + y$ $x$ $\sum_i x_i$ spośród wszystkich maksymalnych rozwiązań.

(Możesz zdefiniować maksymalne minimalne rozwiązanie pokrywającego LP w analogiczny sposób.)

Jak wygląda przestrzeń minimalnych maksymalnych rozwiązań? Jak możemy znaleźć takie rozwiązania? Jak trudno jest znaleźć takie rozwiązania? Jak możemy zbliżyć takie rozwiązania? Kto studiuje takie rzeczy i jaki jest na to właściwy termin?

Te pytania były pierwotnie motywowane zestawami dominującymi na krawędzi i minimalnymi maksymalnymi dopasowaniami . Dobrze wiadomo (i dość łatwo zauważyć), że minimalne maksymalne dopasowanie jest zestawem dominującym minimalnej krawędzi; i odwrotnie, biorąc pod uwagę zestaw dominujący minimalnej krawędzi, łatwo jest stworzyć minimalne dopasowanie maksymalne.

Są więc w istocie tym samym problemem. Oba problemy są trudne dla NP i trudne dla APX. Istnieje prosty algorytm z 2 przybliżeniami: dowolne maksymalne dopasowanie.

Jednak ich „naturalne” relaksacje LP wyglądają zupełnie inaczej. Jeśli weźmiesz dominujący problem z zestawem i utworzysz naturalny relaks LP, dostaniesz cover LP. Jeśli jednak podejmiesz problem znalezienia minimalnego maksymalnego dopasowania i spróbujesz wymyślić relaksację LP, to co otrzymasz? Cóż, oczywiście dopasowania ułamkowe są wykonalnymi rozwiązaniami pakującego LP; wówczas maksymalne dopasowania ułamkowe są maksymalnymi rozwiązaniami takich LP, a zatem minimalne maksymalne dopasowania ułamkowe są minimalnymi maksymalnymi rozwiązaniami takich LP. :)

cc.complexity-theory ds.algorithms reference-request linear-programming optimization Jukka Suomela
źródło

Twoja definicja maksimum jako „nie możemy łapczywie zwiększyć żadnego elementu” brzmi bardzo podobnie do Nash Equilibrium. Czy jest tu ukryty związek z teorią gier?

Derrick Stolee,

Czy nie jest tak, że dla każdego maksymalnego rozwiązania w pakowaniu przykładu LP, ? Zatem zasadniczo szukamy minimalnego (w -norm) rozwiązania układu równań liniowych.

x^{'}

$x'$

A x^{'} = 1

$Ax'=1$

L_{\infty}

$L_{\infty}$

Imran Rauf,

@Imran: Nie, nie sądzę, żeby to było poprawne. Zawsze istnieje maksymalne rozwiązanie (i maksymalne), nawet jeśli nie mamy rozwiązania .

A x = 1

$Ax = 1$

Jukka Suomela

Czy znasz programy liniowe z wąskim gardłem , w których aspekt minimax jest funkcją funkcji celu?

Mike Spivey,

Odpowiedzi:

Maksymalność i minimalność: są rodzajem optymalności Pareto.
Złożoność: Myślę, że znalezienie minimalnego maksymalnego rozwiązania jest trudne NP. Zmniejszyłbym problem dominacji niezależności (zwany również problemem minimalnego maksymalnego zestawu niezależnego) na grafach dwustronnych. Ten problem (a dokładniej jego wersja decyzyjna) jest znany jako NP-zupełny (DG Corneil i Y. Perl, Gromadzenie i dominacja w doskonałych grafach. Discrete Applied Mathematics 9 (1984) 27-39). Ponieważ wykres dwustronny jest idealny, jego niezależny zbiór polytopów jest określony przez nierówności kliki, a liczba klików na wykresie dwudzielnym jest wielomianowa. Dlatego możemy jawnie zapisać układ nierówności liniowych Ax <= 1, x> = 0 dla niezależnego zestawu polytopów. Ekstremalne rozwiązania odpowiadają niezależnym zestawom, a ekstremalne maksymalne rozwiązania odpowiadają maksymalnym niezależnym zestawom.

Yoshio Okamoto
źródło

Przydatne może okazać się przyjrzenie się blokującym i blokującym parom wielościanów. Powiedz, że masz problem z pakowaniem. Wówczas możliwe regionu to wielościan rogu w nieujemną orthant, a jego anty-bloker (również wielościan róg) jest w zasadzie zbiorem nierówności określających . $P$ $A(P)$ $P$

Na przykład, jeśli weźmiesz stabilny zbiór polytopów dla niektórych wykresów (tj. Wypukły kadłub wektorów częstości występowania zestawów stabilnych), jego środkiem przeciwblokującym jest ułamkowa kliki , tj. (tj. zestaw nieujemnych wag, tak że żaden stabilny zestaw nie ma masy całkowitej ). $STAB(G)$ $G$ $G$ $QSTAB(\bar G)$ $> 1$

Jeśli spojrzysz na „Metodę elipsoidy i jej konsekwencje w optymalizacji kombinatorycznej” Grötschela, Lovásza i Schrijvera, przekonasz się, że optymalizacja nad jest w sensie obliczeniowym równoważna optymalizacji z . Jest to jeden ze sposobów udowodnienia, że obliczanie ułamkowej liczby chromatycznej jest trudne dla NP, ponieważ podwójny region LP jest przeciwblokerem stabilnego zestawu politytów! $P$ $A(P)$

Niestety trudno mi było znaleźć przejrzyste wyjaśnienie tego, ale nie jestem ekspertem od wielościanów. Mamy nadzieję, że okaże się, że ma to związek z danym problemem.

Andrew D. King
źródło