Метод генерации столбцов для решения задач математической оптимизации большой размерности

[N-Cube]

patterns = [[0, 0, 0, 1],
[0, 0, 1, 0],
[1, 0, 1, 0],
[0, 1, 0, 0],
[0, 2, 0, 0],
[1, 1, 0, 0],
[1, 0, 0, 0],
[2, 0, 0, 0],
[3, 0, 0, 0]]

Вот это вот кошмар, не делайте так. Посчитайте, а не руками вбивайте с потенциальными ошибками.

RAWS_WIDTH = 10
order_sizes = [3, 5, 6, 9]

При таких условиях решение ищется тривиально - из рулона шириной 10 вырезается полоса шириной 9 и остаток при отсутствии заказа на полосу шириной 1 идет в расход, далее 6 и остаток используется для полосы шириной 3 и т.п.

[mkrasilnikov]

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

[Mausglov]

Сумма всех выполненных разрезов по паттернам должна быть больше, чем

Тем не менее, в формуле написано "не меньше,чем". Это разные вещи, вообще-то

[mkrasilnikov]

Спасибо большое за комментарий. Внес изменения по тексту, далее буду более щепетильно относиться к вычитке текста статьи.

[datacompboy]

Я понимаю, если цель стоит получить ровно рулонов на заказы. Но если стоит "не меньше", то зачем нужны бесполезные паттерны?

Ну просто паттерн "3" как и "3 3" не нужны же,например

[mkrasilnikov]

Например, у нас есть, один заказ размера 3. Тогда нам нет смысла разрезать по паттерну на части 3+3+3, так как нам хватит всего одного обрезка 3. То есть в общем случае задачи, такие ситуации могут появляться. Важно отметить, что это все-таки алгоритм, а не эвристика и должен работать при всех вариантах разнообразия входных данных.

Чуть добавлю про количество разбиений (речь идет не про разбиения исходных рулонов на части различных типов заказов, а будет идти о натуральных числах, но по аналогии можно понять связь между ними): Недавно посмотрел фильм про индийского математика Сриниваса Рамануджана, который изучал разбиения натуральных чисел. Фильм советую, масштаб количества разбиений можно оценить по ссылке.

[datacompboy]

Я к тому, что скорость решения зависит от числа паттернов. И все "бесполезные" паттерны только замедляют решение. Они нужны если задача минимизировать не только число болванок но и число резов -- но тогда надо стоимость каждому из паттернов назначить.

В приведенной задаче только 5 из 9 паттернов действительно нужны для поиска решения.

[mkrasilnikov]

Верно, в следующей части расскажу, как генерировать "полезные" паттерны динамически, что и составляет суть алгоритма column generation.