Zminimalizuj maksymalny składnik sumy wektorów

Chciałbym dowiedzieć się czegoś o tym problemie optymalizacji: dla podanych nieujemnych liczb całkowitych znajdź funkcję minimalizującą wyrażenie $a_{i,j,k}$ $f$

max_{k} \sum_{i} a_{i, f (i), k}

$\max_k \sum_i a_{i,f(i),k}$

Przykład użycia innej formuły może być jaśniejszy: Otrzymałeś zestaw zestawów wektorów takich jak

{
    {(3, 0, 0, 0, 0), (1, 0, 2, 0, 0)},
    {(0, 1, 0, 0, 0), (0, 0, 0, 1, 0)},
    {(0, 0, 0, 2, 0), (0, 1, 0, 1, 0)}
}

Wybierz jeden wektor z każdego zestawu, aby maksymalny składnik ich sumy był minimalny. Na przykład możesz wybrać

(1, 0, 2, 0, 0) + (0, 1, 0, 0, 0) + (0, 1, 0, 1, 0) = (1, 1, 2, 1, 0)

z maksymalną składową równą 2, co jest tutaj wyraźnie optymalne.

Jestem ciekawy, czy jest to dobrze znany problem i jakie są dostępne przybliżone metody rozwiązania problemu. Powinien być szybki i łatwy do zaprogramowania (bez solvera ILP itp.). Nie jest potrzebne dokładne rozwiązanie, ponieważ jest to jedynie przybliżenie prawdziwego problemu.

Widzę, że powinienem dodać kilka szczegółów na temat problemów, którymi jestem zainteresowany:

$i \in \{0, 1, \ldots, 63\}$ , tzn. zawsze są 64 wiersze (przy zapisie jak w powyższym przykładzie).
$j \in \{0, 1\}$ , tzn. są tylko 2 wektory na wiersz.
$k \in \{0, 1, \ldots, N-1\}$ gdzie (długość wektora) wynosi od 10 do 1000. $N$

Ponadto w każdym wierszu suma elementów wszystkich wektorów jest taka sama, tj.

\forall i, j, j^{'} : \sum_{k} a_{i, j, k} = \sum_{k} a_{i, j^{'}, k}

$\forall i, j, j':\quad \sum_k a_{i,j,k} = \sum_k a_{i,j',k}$

a suma elementów wektora sumy jest mniejsza niż jego długość, tj.

\sum_{k} \sum_{i} a_{i, f (i), k} < N

$\sum_k \sum_i a_{i,f(i),k} < N$

algorithms optimization linear-programming maaartinus
źródło

Nie jest trudno zredukować problem z 3 partycjami do swojego problemu. Oznacza to, że twój problem jest NP-zupełny, nawet jeśli liczby są podane jednostronnie, a to wyklucza jedno z powszechnych podejść do algorytmu aproksymacji.

Tsuyoshi Ito,

Dzięki za poprawki i dzięki @Tsuyoshi Ito za wgląd. Jeśli dobrze to rozumiem, ograniczenie do dwóch wektorów na linię (o którym zapomniałem powiedzieć) unieważnia redukcję i może znacznie ułatwić problem.

maaartinus

Masz rację, redukcja problemu z 3 partycjami, o którym myślałem, nie działa, jeśli w wierszu są tylko dwa wektory.

Tsuyoshi Ito,

Czy istnieją kombinacje do porównania?

j^{i}

$j^i$

Jason Kleban

@ uosɐſ: Mówiąc dokładniej, istnieją możliwe kombinacje, gdzie to liczba możliwości dla a to liczba możliwości dla .

J^{I} = 2^{64}

$J^I=2^{64}$

J = 2

$J=2$

j

$j$

I = 64

$I=64$

i

$i$

maaartinus

Odpowiedzi:

Redukcji z 3SAT wersji dwóch wektora: podany wzór, pozwalają zmienne indeks, i klauzule indeks. Niech będzie liczbą razy, gdy zmienna pojawia się dodatnio (jeśli ) lub ujemnie (jeśli ) w klauzuli . OPT jest mniejsze niż jeśli formuła jest zadowalająca (bijection jest oczywisty). $i$ $j \in \{0,1\}$ $k$ $a_{i,j,k}$ $i$ $j = 0$ $j = 1$ $k$ $3$

Jak zaatakowałbym ten problem: poszukiwanie dużych dzielnic. Zacznij od dowolnego rozwiązania. Wybierz wierszy losowo. Użyj brutalnej siły, aby znaleźć najlepsze rozwiązanie, w którym może zmienić się tylko w tych rzędach - bardzo wykonalne nawet dla umiarkowanego biorąc pod uwagę, że rozmiar problemu wynosi rzędy. Powtarzać. $r$ $f$ $k$ $64$

cześć mody
źródło

To piękna redukcja. Nie jestem pewien, dlaczego nie ma żadnych głosów up. W każdym razie tutaj jest moja +1.

Tsuyoshi Ito

Myślę, że powinieneś rozwinąć odrobinę więcej na temat redukcji. W szczególności trzeba ukryte dobrze, może zbyt dobrze, a to sprawia, że bijection nieco trudno zobaczyć.

f

$f$

Raphael

Nie możemy omawiać złożoności problemu, gdy rozmiar problemu jest ustalony na stałą, ponieważ (większość) teoria złożoności dotyczy asymptotycznego zachowania złożoności problemu, gdy rozmiar problemu zmierza do nieskończoności. Tutaj uważam zarówno liczbę wierszy, jak i wymiary wektorów za zmienne.

Wtedy problem jest NP-zupełny, nawet jeśli liczby na wejściu są podane pojedynczo. To nie jest odpowiedź na twoje pytanie, ponieważ pytasz o przybliżenie, ale jest coś.

Dokładnie zdefiniuj problem:

Instancja : n par wektorów a _i , b _i ∈ ℕ ^m ( i ∈ {1,…, n }) i K ∈ ℕ, wszystkie w jednym.
Pytanie : Czy możemy wybrać albo _I lub b _I dla każdego i tak, że suma tych n wektorów ma co najwyżej K w każdym współrzędnych?

Poniżej przedstawiono znany problem NP-complete zwany 3-partycjami :

Wystąpienie z 3 partycjami : B ∈ ℕ i 3 k liczb całkowitych c ₁ ,…, c _{3 k} między B / 4 i B / 2, wyłączne, takie że ∑ _{i = 1}^{3 k} c _i = kB , wszystkie w jednym.
Pytanie : Czy multiset { c ₁ ,…, c _{3 k} } można podzielić na k multisetów S ₁ ,…, S _k tak, aby suma każdego S _j była równaB ?

Biorąc pod uwagę, przykładowo ( B , C, ₁ , ..., C _{3 K} ) o 3 Problem partycji konstrukt wystąpienie powyższego problemu w sposób następujący. Dla każdego i = 1,…, 3 k i j = 1,…, k skonstruujemy parę 4 k wektorów wymiarowych, reprezentujących wybór, czy c _i należy do S _j, czy nie:

Wektor reprezentujący wybór „ c _i ∈ S _j ” ma tylko jeden niezerowy wpis, którym jest ( k- 1) c _i na j- tej współrzędnej.
Wektor reprezentujący wybór „ c _i ∉ S _j ” ma również tylko jeden niezerowy wpis, którym jest B przy ( k + i ) -tej współrzędnej.

Nietrudno dostrzec, że wystąpienie ( B ; c ₁ ,…, c _{3 k} ) problemu 3-partycji ma rozwiązanie wtedy i tylko wtedy, gdy istnieje sposób wyboru wektora z każdego zbudowanego 3 k ² parami tak, że wszystkie współrzędne suma tych wektorów w najgorszym ( k -1) B . (W rzeczywistości, gdy tak się dzieje, wszystkie współrzędne sumy są równe ( k- 1) B ). Jest to więc redukcja problemu z 3-partycjami do powyższego problemu.

Do tej pory ignorowałem dwa dodatkowe ograniczenia podane na końcu pytania, ale oba są łatwe do wyegzekwowania poprzez nieznaczne zmodyfikowanie tej redukcji. Warunek, że suma elementów każdego wektora jest równa, może być wymuszony przez dodanie współrzędnych manekina, które zawierają tylko 0 lub 1. Warunek, że suma ta jest mniejsza niż wymiar, może zostać wymuszony przez dodanie współrzędnych manekina, które zawierają tylko 0.

Tsuyoshi Ito
źródło

Dobra odpowiedź, tylko kilka uwag: 1. Nie dbam o złożoność teoretyczną . 2. Liczba rzędów jest stała i może pozostać, ponieważ wystarcza zmianaTo powiedziawszy, wielkie dzięki.

N

$N$

maaartinus,