Новая бин-упаковка?

Обычно при разработке алгоритмов для NP-сложных задач необходимо повторно использовать методы, а не целые алгоритмы. Здесь хорошо переносятся алгоритмы стандартной упаковки контейнеров, использующие метод ветвей и границ с генерацией столбцов.

Идея состоит в том, что мы формулируем огромный экземпляр обложки набора, где наборы — это наборы элементов, которые подходят в единый бункер. Целочисленное программирование — хороший метод для обычного покрытия наборов, но наборов так много, что нам нужно сделать что-то еще, т. е. генерация столбца. Между наборами и столбцами существует однозначное соответствие, поэтому мы вырываем часть решателя линейного программирования, которая использует грубую силу, чтобы найти хороший столбец для входа, и заменяем его решателем для того, что оказывается рюкзаком. аналог этой проблемы.

Эта модифицированная задача о рюкзаке состоит в том, чтобы, учитывая предметы с весами, прибылью и границами, найти наиболее выгодный набор предметов, общий вес которых меньше минимальной границы. Динамическая программа для решения задачи о рюкзаке с небольшими целыми весами легко переносится без потери эффективности. Просто отсортируйте элементы по убыванию; затем при формировании наборов, включающих самый последний элемент, ограничение веса ограничивается только этим элементом.

Следующее основано на ответе Anony-mouse. Я не эксперт по алгоритмам, поэтому расценивайте нижеследующее как «просто мои два цента», чего они стоят.

Я думаю, что Anony-mouse правильно начинает с самых маленьких предметов (по привязке). Это связано с тем, что емкость корзины имеет тенденцию становиться меньше по мере того, как вы добавляете в нее больше предметов; максимальная вместимость корзины определяется первым помещенным в нее предметом, после этого она никогда не может увеличиваться.

Таким образом, вместо того, чтобы начинать с большой корзины и постепенно уменьшать ее вместимость, а также беспокоиться о выносе слишком больших предметов, которые раньше помещались, давайте просто постараемся сохранить вместимость корзин как можно более постоянной. Если мы сможем поддерживать стабильную емкость бинов, мы сможем использовать «стандартные» алгоритмы, которые ничего не знают о «привязке».

Поэтому я бы предложил следующее:

1. Сгруппируйте все элементы по границам.

   Это позволит вам использовать стандартный алгоритм упаковки контейнеров на группу, потому что, если все элементы имеют одинаковую границу (т. е. граница постоянна), ее можно игнорировать. Теперь привязка означает, что вы заранее знаете итоговую вместимость контейнеров.

2. Начните с группы с наименьшей границей и выполните стандартную упаковку для ее элементов.

   Это приведет к тому, что 1 или несколько ячеек будут иметь вместимость, равную границе всех элементов в них.

3. Перейдите к группе элементов со следующей большей границей. Посмотрите, есть ли какие-либо предметы, которые все еще можно поместить в уже существующую корзину (т. е. корзину, созданную на предыдущих шагах).

   Обратите внимание, что привязку можно снова игнорировать; поскольку все ранее существовавшие ячейки уже имеют меньшую вместимость, чем ограничение этих дополнительных предметов, на вместимость ячеек нельзя повлиять; важен только вес, поэтому вы можете использовать «стандартные» алгоритмы.

   Я подозреваю, что этот шаг является примером проблемы (множественных) рюкзаков, поэтому обратите внимание на алгоритмы рюкзака, чтобы определить, как распределить эти предметы по уже существующим, частично заполненным корзинам.

4. Возможно, что группа товаров из предыдущей группы была обработана только частично, могут остаться товары. Они попадут в одну или несколько новых корзин: повторите шаг 3.

5. Повторяйте вышеуказанные шаги (начиная с 3), пока не останется предметов.

Его по-прежнему можно записать как экземпляр ILP, например:

Создайте двоичную переменную x_{i,j}, указывающую, попадает ли предмет j в корзину i, вспомогательные переменные y_i, которые указывают, используется ли ячейка i, вспомогательные переменные c_i, определяющие вместимость ячейки i, и константы s_j (размер предмета j) b_j (привязанный элемента j) и M (достаточно большая константа), теперь

minimize sum[j] y_j

subject to:
1:   for all j:
         (sum[i] x_{i,j}) = 1
2:   for all i,j:
         y_i ≥ x_{i,j}
3:   for all i:
         (sum[j] s_j * x_{i,j}) ≤ c_i
4:   for all i,j:
         c_i ≤ b_j + (M - M * x_{i,j})
5:   x_{i,j} ϵ {0,1}
6:   y_i ϵ {0,1}

Ограничения означают

1. любой предмет находится ровно в одной корзине
2. если элемент находится в корзине, то эта корзина используется
3. предметы в корзине не превышают вместимость этой корзины
4. вместимость корзины не больше, чем нижняя граница предметов, которые в ней находятся (предмет с большой буквой M предотвращает изменение вместимости предметов, которых нет в корзине, при условии, что вы выберете M не меньше, чем верхняя граница)
5. и 6., переменные являются бинарными.

Но разрыв целостности может быть чудовищным.

Во-первых, я могу ошибаться, и может существовать алгоритм, который даже лучше моего.

Упаковка контейнеров является сложной по NP и эффективно решается с помощью классических алгоритмов, таких как First Fit и т. д. Здесь также есть некоторые улучшения.алгоритм Корфа

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

1. Сортировка элементов по границам: сортировка элементов по границам поможет нам упорядочить корзины, поскольку ограничивающим условием является минимум границы.

2. Вставить наименьший элемент (по границе) в корзину

3. Проверить, может ли следующий элемент (отсортированный по границам) сосуществовать в этой корзине. Если он может, то этот элемент также может храниться в корзине. Если нет, попробуйте поместить его в другую корзину или создать для него другую корзину .
4. Повторяйте процедуру, пока все элементы не будут расположены. Процедура повторяется в порядке возрастания границ.

Я думаю, что это в значительной степени решает проблему. Пожалуйста, сообщите мне, если это не так. Я пытаюсь реализовать то же самое. И если есть какие-либо предложения или улучшения, сообщите мне об этом. :) Спасибо