Линейное программирование в python силами библиотеки scipy

[@lash05]

Вопрос по библиотеке в целом — не пробовали её использовать для целочисленных задач?

[@kxx]

Если вы имеете ввиду mixed integer programming, то, насколько мне известно, в scipy нет солвера для такого типа задач. Посмотрите на cvxpy.

[@paveltro]

Согласно документации, на данный момент в scily.linprog поддерживается только simplex. Для ILP (integer linear programming) подходят pulp, cvxopt

[@oleg-x2001]

А почему бы не использовать cvxopt? Это, пожалуй, самый мощный пакет для выпуклой оптимизации.

[@paveltro]

Вы правы, cvxopt более мощный пакет. Scipy был просто под рукой)

[@AC130]

Статья интересная. Я даже и не знал что scipy можно использовать для решения задач линейного программирования.

Пара непонятностей. Видится мне что ограничение 1 можно убрать (ибо оно выполняется автоматически при наличии ограничения 2). Ограничение 4 вовсе неясно, почему именно от нуля до одного? Может быть, просто больше нуля?

И почему ваша модель не учитывает возможность закрытия магазинов, коль такое упомянуто в задаче? Оно понятно что ILP всунуть не получится, но ведь можно решить ослабленную задачу и показать какой получается ответ. Ведь не факт что решение ILP даст те же выводы, что и ваше решение.

[@paveltro]

Ограничение 4 поправил.

Возможность закрытия не учел из-за отсутствия ILP, надо плотнее посмотреть на другие пакеты.

Спасибо за замечания

[@AC130]

А сколько времени требует один обсчёт решения? Если порядка секунды, то можно просто перебрать 2^13 вариантов. Займёт сутки примерно.

[@paveltro]

Порядка секунды как раз)

[@alex_blank]

Из любопытства сделал ту же задачу на mip с целочисленными (бинарными) constraints для условия закрытия магазинов. Параметры (расходы на магазин и выручку) изменил для меньшей тривиальности решения:

https://gist.github.com/xpl/f93af7ea2d2bd08fad2c45535433327d

Задание ограничений в mip сделано удобнее чем в scipy — через перегрузку операторов, так что не нужно мучаться с кодированием их в виде матриц:

for s in range (N_shops):
    m += xsum (supplies_s[s]) <= float (max_demand[s]) * is_open[s]

for f in range (N_facts):
    m += xsum (supplies_f[f]) == float (max_supply[f])

m.objective = (xsum (supplies[i] * c[i] for i in range (len (supplies))) -
               xsum (is_open[i] * shop_rent_cost for i in range (N_shops)))