Czy ten kombinatoryczny problem optymalizacji jest podobny do jakiegokolwiek znanego problemu?

10

Problem jest następujący:

Mamy dwuwymiarową tablicę / siatkę liczb, z których każda reprezentuje pewną „korzyść” lub „zysk”. Także ma dwie nieruchome całkowite i (jako „szerokość” i „wysokość”). A stałej całkowitej . $w$ $h$ $n$

Teraz chcą nałożyć prostokątów o wymiarach na siatce, tak aby łączna suma wartości komórek w tych prostokątów jest zmaksymalizowane. $n$ $w \times h$

Poniższy rysunek przedstawia przykład dwuwymiarowej siatki z dwóch takich prostokątów overlayed na nim (obraz nie wykazuje rozwiązanie optymalne, tylko jedno możliwe nakładanie się, gdy i ) $w = h = 2$ $n = 2$

Przykład siatki

Prostokąty nie mogą się przecinać (w przeciwnym razie musielibyśmy po prostu znaleźć optymalną pozycję dla jednego prostokąta, a następnie umieścić wszystkie prostokąty w tej pozycji.)

W powyższym przykładzie całkowita suma wartości w komórkach wyniosłaby $-2 + 4.2 + 2.4 + 3.14 + 2.3 -1.4 + 1 - 3.1$

Czy jest to podobne do jakiegokolwiek znanego problemu optymalizacji kombinatorycznej? abym mógł zacząć czytać i spróbować znaleźć sposoby na rozwiązanie tego problemu.

Więcej informacji dla zainteresowanych:

Do tej pory jedynymi pomysłami, jakie miałem, był albo chciwy algorytm (który znalazłby najlepszą lokalizację dla pierwszego prostokąta, a następnie znalazłby nienakładające się położenie dla drugiego prostokąta itp.) Lub jakieś metaheurystyczne, takie jak algorytmy genetyczne.

W rzeczywistości chcę rozwiązać ten problem za pomocą siatki, która ma około miliona komórek i dziesiątki tysięcy (lub nawet setki tysięcy) prostokątów, chociaż nie jest konieczne rozwiązanie go w krótkim czasie (tzn. Byłoby to do przyjęcia algorytm zajmuje godziny, a nawet dni.) Nie oczekuję dokładnego rozwiązania, ale chcę uzyskać taki, który jest tak dobry, jak to możliwe, biorąc pod uwagę te ograniczenia.

Twoje zdrowie!

algorithms optimization combinatorics approximation pięćdziesiąt osiem
źródło

(przez telefon) wydaje się, że można to rozwiązać przy maksymalnym dopasowaniu przy transformacji i kilku dodatkowych ograniczeniach. Spróbuję napisać później.

Nicholas Mancuso

n

$n$

n - 1

$n-1$

s

$s$

L

$L$

s

$s$

L

$L$

\geq s

$\ge s$

2

Moje ostatnie sformułowanie miało fatalną wadę, która wymagałaby wykładniczej ilości węzłów „ograniczających”.

$r$ $w_r$ $r, r'$ $k=n$

Nicholas Mancuso
źródło

To kierunek, w którym obecnie się skłaniam, eksperymentuję z tym i akceptuję rozwiązanie, jeśli to ten, którego używam, na zdrowie.

pięćdziesiąt osiem

2

Możesz sformułować to jako gigantyczną instancję programowania liniowego liczb całkowitych (ILP), a następnie zastosować gotowy do użycia solver ILP (lp_solve, CPLEX itp.). Dadzą ci najlepsze rozwiązanie, jakie mogą znaleźć. Biorąc pod uwagę rozmiar wystąpienia problemu, nie wiem, czy będzie to wystarczająco wydajne, ale łatwo byłoby spróbować.

$x_r$ $r$ $x_r=1$ $r$ $x_r=0$ $\sum_r c_r x_r$ $c_r$ $r$ $\sum_r x_r = n$ $x_r + x_s \le 1$ $r,s$

DW
źródło

Czy uważasz, że ten problem jest trudny do NP? Nie jestem przekonany, że nie ma rozwiązania wieloczasowego, a solwery ILP raczej nie ukończą nawet instancji o średniej wielkości.

RB

1

@RB, nie mam pojęcia, czy jest to trudne NP. Zobacz mój komentarz pod pytaniem o programowaniu dynamicznym, aby po raz pierwszy zastanowić się, jak znaleźć algorytm czasu wielomianowego (ale nie wiem, czy wynikowy algorytm będzie miał wartość P, czy nie). Jeśli chodzi o to, co potrafią solwery ILP, jedynym sposobem na sprawdzenie tego jest próba - czasem ich wydajność może być zaskakująca.

DW

Czy ten kombinatoryczny problem optymalizacji jest podobny do jakiegokolwiek znanego problemu?

Odpowiedzi: