Skutecznie rozwiązać system ścisłych nierówności liniowych ze wszystkimi współczynnikami równymi 1 bez użycia ogólnego solwera LP?

Według tytułu, oprócz korzystania z solwera LP ogólnego przeznaczenia, istnieje podejście do rozwiązywania układów nierówności względem zmiennych $x_i, \ldots, x_k$ gdzie nierówności mają formę $\sum_{i \in I} x_i < \sum_{j \in J} x_j$ ? Co ze szczególnym przypadkiem nierówności, które tworzą całkowity porządek nad sumami członków zestawu potęg $\{x_i, \ldots, x_k\}$ ?

ds.algorithms linear-algebra linear-programming Jerry
źródło

@Ankur: nie ma znaczenia, czy są to liczby całkowite czy rzeczywiste. Jeśli są to ścisłe nierówności, możesz zaokrąglić je do racjonalnych, a następnie pomnożyć je przez najmniej powszechny mianownik, aby uzyskać rozwiązanie liczb całkowitych.

Peter Shor

Nie mam pojęcia, co możesz napisać w 30 minut (w jakim języku?). Jeśli to jest kryterium „proste”, czy w ogóle jest to pytanie w teoretycznej informatyce?

Tsuyoshi Ito,

Dobra uwaga Peter Shor. Jerry, cofam moje oświadczenie. Myślałem, że kombinatoryczny problem wypełnienia tych ścisłych nierówności i wypukły analityczny problem znalezienia wewnętrznego punktu stożka są jakościowo różne. Myliłem się.

Ankur

@Tsuyoshi: Nie musi to być trywialne, ale jestem ciekawy, czy można to zrobić z pierwszych zasad bez korzystania z całej dodatkowej mocy pełnego solvera LP, szczególnie w specjalnym przypadku, w którym mamy zamówienie wszystkich sum częściowych (zauważ w tym przypadku, że czas wielomianowy jest wykładniczy w liczbie zmiennych).

czerwiec

Następnie myślę, że „Czy ten problem można rozwiązać skutecznie bez użycia ogólnych algorytmów do programowania liniowego?” to dobry sposób na lepsze sformułowanie pytania.

Tsuyoshi Ito,

Odpowiedzi:

W przypadku pierwszego pytania bez całkowitego zamówienia odpowiedź na to pytanie jest taka, że jest on zasadniczo tak trudny jak programowanie liniowe. Oto zarys dowodu.

Najpierw ustalmy zmienną $x_1>0$ , które nazywamy $\epsilon$ . Teraz wybierzmy inną zmienną $x_i$ , które nazwiemy $1$ . Chcemy się tego upewnić

ϵ ≪ 1 .

$\epsilon \ll 1\, .$ Aby to zrobić, weź pod uwagę nierówności

x_{1} < x_{2},

$x_1 < x_2,$

x_{1} + x_{2} < x_{3},

$x_1 + x_2 < x_3,$

x_{2} + x_{3} < x_{4},

$x_2+x_3 < x_4,$ i tak dalej. Przy wystarczająco długim łańcuchu to nam to powie

N x_{1} < x_{i}

$Nx_1 < x_i$ lub

ϵ < 1 / N

$\epsilon < 1/N$ , dla niektórych bardzo dużych

N

$N$ (

N

$N$ jest liczbą Fibonacciego, a zatem rośnie wykładniczo w

i

$i$ ).

Możemy teraz wyprodukować program liniowy ze współczynnikami całkowitymi. Jeśli chcemy współczynnika 3 na $x_t$ , dodajemy nierówności

x_{t} < x_{t^{'}} < x_{t^{″}} < x_{t} + ϵ

$x_t < x_{t'} < x_{t''} < x_t + \epsilon$ i niech 3 . Jeśli chcesz mieć większe współczynniki, możesz je uzyskać, wyrażając współczynniki w notacji binarnej i wprowadzając nierówności, które gwarantują, że , i tak dalej. Aby uzyskać prawą stronę, robimy to samo ze zmienną . Ta technika pozwoli nam użyć programów liniowych w postaci PO, aby w przybliżeniu sprawdzić wykonalność dla dowolnych programów liniowych o współczynnikach całkowitych, co jest zadaniem tak samo trudnym jak programowanie liniowe.

x_{t} + x_{t^{'}} + x_{t^{″}}

$x_t + x_{t'} + x_{t''}$

x_{t}

$x_t$

x_{u} \approx 2 x_{t}

$x_u \approx 2x_t$

x_{v} \approx 2 x_{u}

$x_v \approx 2x_u$

x_{i} = 1

$x_i = 1$

Nie wiem, jak przeanalizować drugie pytanie, pytając o przypadek, w którym wszystkie podzbiory mają całkowitą kolejność.

Peter Shor
źródło