Równoważność kontroli wykonalności i optymalizacji dla systemów liniowych

Jednym ze sposobów wykazania, że sprawdzenie wykonalności liniowego układu nierówności jest tak trudne, jak programowanie liniowe, jest zmniejszenie za pomocą metody elipsoidalnej. Jeszcze łatwiejszym sposobem jest odgadnięcie optymalnego rozwiązania i wprowadzenie go jako ograniczenia poprzez wyszukiwanie binarne.

Obie te redukcje są wielomianowe, ale nie silnie wielomianowe (tzn. Zależą od liczby bitów we współczynnikach nierówności).

Czy istnieje silnie wielomianowa redukcja z optymalizacji LP do wykonalności LP?

ds.algorithms linear-programming

— Suresh Venkat
źródło

właściwie nie. Tak jak mówisz. Zdaję sobie sprawę, że optymalizacja LP rozwiązuje wykonalność LP. Proszę o odwrotną redukcję.

— Suresh Venkat

Cóż, dane wyjściowe do optymalizacji mogą mieć tyle bitów, co „liczba bitów we współczynnikach”, a wykonalność to tak / nie. Tak więc, jeśli przez redukcję rozumiesz coś „czarnego pudełka”, to odpowiedź musi być przecząca.

— Noam

Ale jeśli kontrola wykonalności nie tylko daje odpowiedź tak / nie, jak omówiono powyżej przez Noama, ale raczej w przypadku wykonalności zapewnia wykonalne rozwiązanie, wówczas odpowiedź brzmi tak, przez dualność LP.

— Kristoffer Arnsfelt Hansen

@SureshVenkat: Załóżmy, że pierwotny to program maksymalizacyjny w zmiennych

, a dual to program minimalizacyjny w zmiennych

. Następnie utwórz system nierówności w zmiennych

, biorąc ograniczenia zarówno pierwotne, jak i podwójne, wraz z nierównością stwierdzającą, że wartość pierwotnego rozwiązania jest co najmniej wartością podwójnego rozwiązania. Przypadki niewykonalnego i nieograniczonego LP można również rozwiązać.

x

$x$

y

$y$

x, y

$x,y$

— Kristoffer Arnsfelt Hansen

Co z polytopami / wielościanami zdefiniowanymi przez domniemane ograniczenia?

— Chandra Chekuri

Odpowiedź brzmi „tak” i faktycznie można nawet zredukować do problemu decyzyjnego wykonalność nierówności liniowych!

Jesteśmy jako dane wejściowe, biorąc pod uwagę instancję LP P: . $\max c^Tx\ \text{s.t.}\ Ax \leq b\ ;\ x\geq 0$

Ponadto mamy dostęp do wyroczni, która biorąc pod uwagę system nierówności zwraca tak / nie, czy system jest wykonalny. $S=\{Bz \leq d\}$

Redukcja przebiega teraz w następujący sposób:

$S_1=\{Ax \leq b\ ;\ x \geq 0\}$
$\min b^Ty\ \text{s.t.}\ A^Ty \geq c\ ;\ y \geq 0$
$S_2=\{Ax \leq b\ ;\ x\geq 0\ ;\ A^Ty\geq c\ ;\ y\geq0 \ ;\ b^Ty \leq c^Tx\}$
$S_1$ $S_2$ $S_2$ $S_3$ $S_3$
$S_3$ $x$

— Kristoffer Arnsfelt Hansen
źródło

S_{2}

$S_2$

P

$P$

@hengxin. W pierwszym wierszu mojej odpowiedzi piszę, że odpowiedź brzmi „tak”, nawet jeśli rozważa się ograniczenie problemu decyzyjnego. Poniżej oczywiście zakładam to założenie, dlatego wymagane są kroki 4 i 5.

— Kristoffer Arnsfelt Hansen