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$

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.

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

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).j ∈ { 0 , 1 } k a i , j , k i j = 0 j = 1 k $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ć.f k $r$$f$$k$$64$

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.