Странная, но практичная оптимизация упаковки двурядного бина

Я пытаюсь написать приложение, которое создает чертеж для разделенной панели.

У меня есть N ячеек (2D прямоугольников) (N <= 40). Для каждой ячейки есть минимальная высота (minHeight [i]) и минимальная ширина (minWidth [i]). Сама панель также имеет ограничение MAXIMUM_HEIGHT.

Эти N ячеек должны быть расположены в столбчатой сетке таким образом, чтобы указанные ограничения удовлетворялись для каждой ячейки.

Кроме того, ширина каждого столбца определяется максимальным значением minWidths каждой ячейки в этом столбце.

Кроме того, высота каждого столбца должна быть одинаковой. Это определяет высоту панели

Мы можем добавить запасные ячейки в пустое пространство, оставшееся в любом столбце, или мы можем увеличить высоту/ширину любой ячейки за указанный минимум. Однако мы не можем повернуть любую из ячеек.

OBJECTIVE: TO MINIMIZE TOTAL PANEL WIDTH.

В настоящее время я реализовал это просто, игнорируя ширину ячеек в моей оптимизации. Я просто выбираю ячейку с наибольшим minHeight и стараюсь вставить ее в свою панель. Однако это не гарантирует оптимальное решение.

Могу ли я получить что-то лучше этого?

EDIT 1: MAXIMUM_HEIGHT панели = 2100 мм, диапазон минимальной ширины (от 350 мм до 800 мм), диапазон минимальной высоты (от 225 мм до 2100 мм)

РЕДАКТИРОВАТЬ 2: ЦЕЛЬ ПРОБЛЕМЫ: МИНИМИРОВАТЬ ШИРИНУ ПАНЕЛИ (не панель).

Ответ 1

Состав

Дано:

для каждой ячейки i = 1, ..., M, (min) width W_i и (min) height H_i
максимально допустимая высота любого стека, T

Мы можем сформулировать смешанную целочисленную программу следующим образом:

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)

Вы можете выбрать N как любое достаточно большое целое число (например, N = M).

Алгоритм

Подключите эту смешанную целочисленную программу к существующему программному решателю смешанных целых чисел, чтобы определить сопоставление между ячейками, заданное с помощью оптимальных значений C_i, i = 1, ..., M.

Это та часть, которую вы не хотите изобретать самостоятельно. Используйте существующий решатель!

Примечание

В зависимости от выразительной мощности вашего пакета решений для смешанных целочисленных программ вы можете или не сможете напрямую применять формулировку, описанную выше. Если ограничения [1] и [2] не могут быть указаны из-за их "основанного на наборе" характера или max, вы можете вручную преобразовать формулировку в эквивалентный менее декларативный, но более -канонический, который не нуждается в этой выразительной силе:

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

Здесь переменные C_i from before (принимающие значения в { 1, ..., N }) заменены на переменные C_i_k (принимая значения в { 0, 1 }) в соответствии с соотношением C_i = sum { C_i_k | k = 1, ..., N }.

Окончательное сопоставление между ячейками описывается C_i_k: cell i принадлежит в столбце k тогда и только тогда, когда C_i_k = 1.

Ответ 2

Одним из решений является разделение ширины строки ячейки на минимальную ширину. Это дает вам максимальное количество ячеек, которые могут вписываться в строку.

Разделите оставшуюся часть первого деления на количество ячеек. Это дает дополнительную ширину, чтобы добавить минимальную ширину, чтобы сделать все ширины ячейки даже.

Пример. У вас есть ячейка в 63 метра. Каждая ячейка имеет минимальную ширину 2 метра. Я предполагаю, что толщина одной из стенок кабины включена в 2 метра. Я также предполагаю, что один конец кабины будет против стены.

Выполняя математику, получаем 63/2 = 31,5 или 31 ячейку.

Теперь мы разделим 0,5 метра на 31 ячейку и получим 16 миллиметров. Таким образом, ширина ячейки составляет 2,016 м.

Ответ 3

Вы можете посмотреть в vm-упаковке, особенно знакомый алгоритм для коллокации виртуальных машин: http://dl.acm.org/citation.cfm?id=1989554. Вы также можете прочитать о @http://en.m.wikipedia.org/wiki/Bin_packing_problem. Проблема уже сложна, но ячейка может иметь ширину или высоту. Таким образом, пространство поиска увеличивается.