0-1 Programowanie liniowe: obliczanie optymalnej formuły

Rozważmy $n$ -wymiarowej przestrzeni $\{0,1\}^n$ , niech $c$ być liniowy ograniczenie formy , gdzie , $a_1x_1 + a_2x_2 + a_3x_3 +\ ...\ + a_{n-1}x_{n-1} + a_nx_n \geq k$ $a_i \in \mathbb{R}$ a . $x_i \in \{0,1\}$ $k \in \mathbb{R}$

Najwyraźniej powoduje podział na dwa podzbiory i . zawiera wszystkie i tylko punkty spełniające , podczas gdy zawiera wszystkie i tylko te punkty fałszujące . $c$ $\{0,1\}^n$ $S_c$ $S_{\lnot c}$ $S_c$ $c$ $S_{\lnot c}$ $c$

Załóżmy, że $|S_c| \geq n$ . Teraz niech $O$ będzie podzbiorem $S_c$ tak że wszystkie trzy następujące instrukcje będą zawierały:

$O$ zawiera dokładnie $n$ punktów.
Takie $n$ punktów jest liniowo niezależnych.
Takie punktów to punkty w minimalnej odległości od hiperpłaszczyzny reprezentowane przez . Dokładniej, niech będzie odległością punktu od hiperpłaszczyzny . Następnie, tak, że spełnia 1 i 2, jest tak, że $n$ $c$ $d( x, c )$ $x \in \{0,1\}^n$ $c$ $\forall B \subseteq S_c$ $B$ . Innymi słowy jest spośród wszystkich podzbiorów spełniające oba warunki 1 i 2, jeden, który minimalizuje sumę odległości punktami z hiperpłaszczyznę . $\sum_{x \in B} d(x, c) \geq \sum_{x \in O} d(x, c)$ $O$ $S_c$ $c$

pytania

Biorąc pod uwagę , czy możliwe jest wydajne obliczenie ? $c$ $O$

Jaki jest najbardziej znany algorytm do jego obliczania?

$\$

Przykład z $n = 3$

Przykład z n = 3

, . $S_{\lnot c} = \{ ( 1, 0, 1 ) \}$ $O = \{ ( 0, 0, 1 ), ( 1, 1, 1 ), ( 1, 0, 0 ) \}$

$\$

Aktualizacja 05.12.2012

Motywacja

Motywacja jest, że za pomocą powinno być możliwe do określenia optymalnego wiązania , a powinien on być określony przez hiperpłaszczyzna punktów . $O$ $c^*$ $n$ $O$

Optymalne ograniczenie to takie, które prowadzi do optymalnego polytopu . $c^*$ $P^*$

Optymalnym polytopem jest ten, którego wierzchołki są wszystkie i tylko wierzchołkami całkowitymi początkowego polytopu (wierzchołek całkowity jest wierzchołkiem, którego współrzędne są liczbami całkowitymi). $P^*$ $P$

Optymalne sformułowanie

Proces można iterować dla każdego ograniczenia instancji 0-1 , za każdym razem zastępując odpowiadającym mu ograniczeniem optymalnym . Na koniec, doprowadzi to do optymalnego Polytope z . Następnie, ponieważ wierzchołki są jedynymi wierzchołkami liczb całkowitych początkowego politopu z , można zastosować dowolny algorytm dla do obliczenia optymalnego rozwiązania liczby całkowitej. Wiem, że umiejętność skutecznego obliczenia oznaczałaby $c$ $LP$ $I$ $c$ $c^*$ $P^*$ $I$ $P^*$ $P$ $I$ $LP$ $P^*$ , jednak nadal pojawia się następujące dodatkowe pytanie: $P = NP$

Dodatkowe pytanie

Czy są jakieś wcześniejsze prace w tym zakresie? Czy ktoś badał już zadanie obliczeniowe, biorąc pod uwagę polytop , odpowiadający mu optymalny polytop ? Który algorytm jest najbardziej znany? $P$ $P^*$

— Giorgio Camerani
źródło

Wydaje się, że jest to trudne do zrobienia dokładnie przez redukcję sumy podzbioru. Biorąc pod uwagę binarne liczby całkowite

, aby sprawdzić, czy istnieje podzbiór sumujący się do

, możemy przetestować, czy istnieje punkt na hiperpłaszczyźnie

. Czy jesteś zainteresowany przybliżeniami?

v_{1}, \dots, v_{n}

$v_1,\dots,v_n$

s

$s$

v_{1} x_{1} + \dots + v_{1} x_{n} = s

$v_1x_1+\dots+v_1x_n= s$

— Colin McQuillan,

@ColinMcQuillan: Pytanie miało na celu dokładne rozwiązanie, jednak z pewnością interesują mnie również przybliżenia. Dlaczego nie zmienisz komentarza w odpowiedź?

— Giorgio Camerani,

@ColinMcQuillan: Również twoja hiperpłaszczyzna jest definiowana przy użyciu równości, podczas gdy moja jest definiowana przy użyciu nierówności. Czy jesteś pewien, że nie ma to różnicy pod względem twardości? Jeszcze tego nie sprawdziłem, więc tylko pytam.

— Giorgio Camerani,

Jestem trochę mylić o wszystkich ograniczeń

. Jeśli szukasz informacji o wypukłym kadłubie

w literaturze dotyczącej badań operacyjnych jest wiele wyników dotyczących plecaka 0-1. Pod względem przybliżonych preparatów zobaczyć .

O

$O$

S_{c}

$S_c$

— Austin Buchanan,

Odpowiedzi:

Wydaje się, że jest to trudne do zrobienia dokładnie przez redukcję sumy podzbioru. Załóżmy, że mieliśmy skuteczną procedurę, aby obliczyć . Biorąc pod uwagę dodatnie liczby całkowite zakodowane binarnie, chcemy przetestować, czy istnieje podzbiór sumujący do . Przetwarzaj wstępnie, wyrzucając liczby całkowite większe niż . $O$ $v_1,\dots,v_n$ $s$ $s$

Wywołaj procedurę, aby uzyskać mały zbiór punktów spełniających , spełniających twoje warunki minimalności (wstępne przetwarzanie zapewnia ). Ten zestaw z pewnością będzie zawierał punkt na hiperpłaszczyźnie jeśli taki istnieje. $O$ $v_1x_1+\dots+v_1x_n\leq s$ $|S_c|\geq n$ $v_1x_1+\dots+v_1x_n= s$

— Colin McQuillan
źródło

Może pomijam tutaj coś makroskopowego, ale mam 2 pytania: 1) Kiedy mówisz „Biorąc pod uwagę liczby całkowite binarne ”, co rozumiesz przez binarny ?

należą do

. Może masz na myśli kodowanie binarne? A może chciałeś powiedzieć pozytywnie? 2) Po co wyrzucać liczby całkowite większe niż

? Mogą przyczynić się do rozwiązania. Na przykład:

v_{1}, . . ., v_{n}

$v_1, ..., v_n$

R

$\mathbb{R}$

s

$s$

jeśli wyrzucisz

, tracisz jedyne rozwiązanie

v_{1} = - 3, v_{2} = 7, v_{3} = - 5, s = 2

$v_1 = -3, v_2 = 7, v_3 = -5, s = 2$

v_{2}

$v_2$

{v_{2}, v_{3}}

$\{v_2, v_3\}$

— Giorgio Camerani,

Myślę, że Colin ma na myśli to, że jeśli współczynniki ograniczenia

są liczbami wymiernymi, w ich zwykłej reprezentacji binarnej, wtedy twój problem wydaje się NP-trudny. (Mieszanie liczb rzeczywistych i twardości NP jest zawsze trudne.)

a_{i}

$a_i$

— Jeffε

@GiorgioCamerani: Musiałem powiedzieć pozytywnie - zaktualizowałem swoją odpowiedź.

— Colin McQuillan,

Wydaje mi się, że próbujesz dostać się do wypukłego kadłuba IP - w zasadzie to właśnie próbują osiągnąć algorytmy cięcia. Mimo, że te metody są atrakcyjne, w praktyce źle się sprawdzają.

Istnieje cała teoria na temat generowania ważnych nierówności. Dobrym punktem wyjścia będzie książkowa teoria programowania liczb całkowitych Shrijvera.

— AJ Student
źródło