Линейное программирование - Ограничения

Question

Я пытаюсь кодировать это (небольшая часть проекта) для линейного программирования:

Для каждого пакета р мы знаем его длину (xDimp) и ширину (yDimp). Кроме того, у нас есть длина (xTruck) и ширина (yTruck) грузовика. Все числа являются целыми числами.

Из-за конструкции упаковок они не могут вращаться при установке в грузовик.

Грузовик представлен в виде матрицы двух измерений, только с координатами x и y. Мы игнорируем высоту.

Решение переменные:

- рху [р, х, у] = пакет р находится в ячейке с верхней правой координатами (х, у)

- PBL [р, х, у] = нижняя левая ячейка р имеет верхние правые координаты (х, у)

Как я пишу такие ограничения, чтобы установить PBL и Pxy переменных? Я полагаю, что я должен установить переменную pbl, чтобы убедиться, что пакет подходит для грузовика, а значение переменной pxy зависит от значения pbl.

Спасибо,

Answer 1

Это вариант задачи упаковки в контейнеры, двухмерная упаковка из нескольких прямоугольников различной ширины и высоты в ограждающей прямоугольника (2bp). Если их разрешено поворачивать на 90 °, мы получили проблему прямоугольной упаковки с ортогональной ориентацией, и в вашем случае у нас есть проблема с прямоугольной упаковкой без поворота. Его вычислительная сложность NP-жесткая, но это не является неосуществимым. Из вашего описания проблема уже дискретизирована, что ограничивает возможные места размещения в сетке, что означает, что оптимальный вариант непрерывной версии может быть недоступен.

Один Approch должен вычислить некоторый граф конфликтной заранее, которое представляет пространство поиска и хранит информацию о перекрытии прямоугольников:

где

Каждое ребро представляет конфликт, и каждый узел представляет возможное размещение внутри вашего грузовика. Два пакета р и д пересекаются тогда и только тогда

и парными.

Теперь проблема упаковки в сетке - это проблема с максимальной независимой установкой на графике конфликта (MIS), предполагая, что вы хотите увеличить количество пакетов на грузовике. ИСУ, в свою очередь, имеет следующий состав: ILP

Это целое число релаксация ИСУ, но до сих пор не хорошо для метода ветвей и границ решающего.Если С является клика в G то любое независимое множество может выбрать не более одного узел из C, поэтому использует следующее ограничение: количество

полученных в результате линейной программы переменного растет экспоненциально.

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

Во-вторых, использовать набор дизъюнктивных ограничений для предотвращения перекрытия:

С этой точки на, вы можете начать формулировать метапрограмму, как описано here

Я думаю, этого должно быть достаточно для start :-) Дополнительную информацию о комбинаторной оптимизации вы можете найти в литературе.

Источники:

http://www.staff.uni-mainz.de/schoemer/publications/ESA03.pdf

https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/2046