Оптимальная двухмерная упаковка в контейнеры

Связано: stackoverflow.com/q/46630524/555045 (на этот раз без дыр, что мало что меняет)   -  person harold    schedule 25.05.2019

@гарольд Интересно! Пожалуйста, я не знаком с целочисленным программированием, поэтому у меня есть несколько вопросов. Он работает, записывая множество некоторых ограничений и запуская над ними решатель, который затем выводит позиции элементов относительно. баки, верно? Есть ли механический способ создания ограничений для упаковки 2D-контейнеров? Я имею в виду, что, вероятно, всегда должно быть ограничение, каждый элемент должен куда-то идти, известно ли, какие ограничения нужны для упаковки 2D-контейнеров? Что делать, если некоторые предметы не помещаются ни в одну корзину (все заполнены)? Что делать, если оптимальных упаковок несколько?   -  person Ecir Hana    schedule 28.05.2019

Этот ответ уже имеет механическую конструкцию, он немного высокоуровневый, но все это можно записать в виде кода, который добавляет линейные неравенства к модели ILP. Он не берет каждый элемент и пытается поместить его куда-то, внутренняя задача генерирует способы упаковать корзину, а внешняя задача оптимизирует общее количество таких способов, используемых при ограничении, что каждый элемент встречается как минимум столько раз, сколько мы хотели. Это. Таким образом, мусорные ведра не могут закончиться   -  person harold    schedule 28.05.2019

@harold И эта внешняя и внутренняя проблема выражается в одном и том же наборе ограничений и решается за один прогон? Или результаты внутреннего процесса каким-то образом итеративно передаются во внешний? И когда вы говорите [t] здесь разные модели, что вы имеете в виду быть моделью? Различные способы выражения ограничений, которые в конечном итоге приводят к одной и той же оптимальной упаковке?   -  person Ecir Hana    schedule 28.05.2019

Внешние и внутренние проблемы совершенно разные. Внутренней задаче примерно дан один бин, какой хороший способ его заполнить. Внешняя проблема грубо задана всеми этими возможными упаковками, что является хорошим их выбором. Они связаны путем предоставления двойных затрат внешней проблемы в качестве значений элемента для внутренней проблемы, так что внутренняя проблема пытается упаковать корзину сразу же полезным способом (улучшая состояние внешней проблемы).   -  person harold    schedule 28.05.2019

@harold Я имею в виду практически, как мне решить эти две проблемы? Я последовательно запускаю решатель два раза или внешний и внутренний взаимосвязаны, так что я запускаю решатель только один раз? Я никогда раньше не имел дела с ILP...   -  person Ecir Hana    schedule 28.05.2019

Таким образом, вы в конечном итоге запускаете решатели много раз: чтобы решить внутреннюю проблему сотни раз, и постепенно, чтобы внешняя проблема сделала шаг поворота с новым столбцом, заданным результатом внутренней проблемы.   -  person harold    schedule 28.05.2019

@harold Спасибо за объяснение!   -  person Ecir Hana    schedule 28.05.2019