Dziwne, ale praktyczny pojemnik 2D optymalizacji pakowania

Question

Próbuję napisać aplikację, która generuje rysunek na przedziały Panelu.

Mam N kabin (2D prostokąty) (N < = 40). Dla każdej klatki minimalna wysokość (minHighight [i]) i minimalna szerokość (minWidth [i]) są powiązane. Sam panel ma ograniczenie MAXIMUM_HEIGHT.

Te kabiny N muszą być rozmieszczone w taki sposób, aby powyższe ograniczenia były spełnione dla każdej kabiny.

Ponadto, szerokość każdej kolumny jest określona przez maksymalną liczbę minimalną szerokości każdej klatki w tej kolumnie.

Wysokość każdej kolumny powinna być taka sama. To decyduje o wysokości panelu. Możemy dodać zapasowe szafy w pustej przestrzeni w dowolnej kolumnie lub możemy zwiększyć wysokość/szerokość jakiejkolwiek szafki poza określone minimum. Jednak nie możemy obrócić żadnej z kabin.

OBJECTIVE: TO MINIMIZE TOTAL PANEL WIDTH. 

Obecnie zaimplementowałem go po prostu ignorując szerokości kabin w mojej optymalizacji. Właśnie wybieram kabinę z największą minHeight i próbuję dopasować ją do mojego panelu. Nie gwarantuje jednak optymalnego rozwiązania.

Czy mogę uzyskać lepszy wynik?

EDIT 1: MAXIMUM_HEIGHT panelu = 2100 mm, zakres MinWidth (350mm do 800 mm), 225 mm (zakres minheight do 2100 mm)

Edycja 2. PROBLEM CEL: zminimalizowanie płyty szerokość (nie jest to obszar wieczka).

Answer 1

Preparat

Dane:

• dla każdej komórki i = 1, ..., M, The (min) szerokość W_i i (min) wysokość H_i
• maksymalną dopuszczalną wysokość stosu, T

Możemy sformułować mieszane integer program w następujący sposób:

minimize sum { CW_k | k = 1, ..., N } 
with respect to 

    C_i in { 1, ..., N },      i = 1, ..., M 

    CW_k >= 0,         k = 1, ..., N 

and subject to 

[1] sum { H_i | C_i = k } <= T,     k = 1, ..., N 

[2] CW_k = max { W_i | C_i = k },    k = 1, ..., N 
      (or 0 when set is empty) 

Można wybrać dowolny N być wystarczająco duża liczba całkowita (np N = M).

Algorytm

Wtyk program mieszany całkowitą do istniejącego programu całkowitą solver mieszane w celu określenia odwzorowania komórki do kolumny podanej przez optymalne wartości C_i, i = 1, ..., M.

Jest to część, której nie chcesz odkrywać na nowo. Użyj istniejącego solwera!

Uwaga

zależności od siłę wyrazu swojej całkowitej mieszany pakiet programu Solver, to może być lub nie być w stanie bezpośrednio zastosować preparat opisałem powyżej. Jeśli ograniczeń [1] i [2] nie można określić z powodu ich "opartego na zestawie" charakteru lub max, można ręcznie przekształcić formułę na mniej deklaratywną, ale bardziej kanoniczną, o wartości, która nie potrzebuje tej ekspresywnej mocy:

minimize sum { CW_k | k = 1, ..., N } 
with respect to 

    C_i_k in { 0, 1 },       i = 1, ..., M; k = 1, ..., N 

    CW_k >= 0,         k = 1, ..., N 

and subject to 

[1] sum { H_i * C_i_k | i = 1, ..., M } <= T, k = 1, ..., N 

[2] CW_k >= W_i * C_i_k,       i = 1, ..., M; k = 1, ..., N 

[3] sum { C_i_k | k = 1, ..., N } = 1,   i = 1, ..., M 

Tutaj C_i zmienne sprzed (przy wartości { 1, ..., N }) zastąpiono C_i_k zmienne (przy wartości { 0, 1 }) w stosunku C_i = sum { C_i_k | k = 1, ..., N }.

Końcowy mapowania komórek do słupa opisano w The C_i_k: komórki i należy w kolumnie k wtedy i tylko wtedy, gdy C_i_k = 1.

Answer 2

Jednym z rozwiązań jest podział szerokości rzędu kabin o minimalną szerokość. Daje to maksymalną liczbę szafek, które zmieszczą się w rzędzie.

Podziel pozostałą część pierwszego podziału na liczbę komór. Daje to dodatkową szerokość, aby dodać do minimalnej szerokości, aby wszystkie szerokości kabiny były równe.

Przykład: Masz rząd rzędu 63 metrów. Każda kabina ma minimalną szerokość 2 metry. Zakładam, że grubość jednej ze ścianek działowych jest wliczona w 2 metry. Zakładam też, że jedna klapa końcowa będzie przy ścianie.

Wykonując obliczenia matematyczne uzyskujemy 63/2 = 31,5 lub 31 pól.

Teraz dzielimy 0,5 metra po 31 pól i uzyskujemy 16 milimetrów. Szerokość kabin wynosi zatem 2,016 metra.

Answer 3

Możesz zajrzeć do pakowania w VM, a zwłaszcza poznać algorytm kolokacji maszyn wirtualnych: http://dl.acm.org/citation.cfm?id=1989554. Możesz przeczytać również o @http://en.m.wikipedia.org/wiki/Bin_packing_problem. Problem jest już trudny, ale kabina może dzielić szerokość lub wysokość. W ten sposób przestrzeń wyszukiwania staje się większa.