Pull to refresh

Comments 10

Вопрос по библиотеке в целом — не пробовали её использовать для целочисленных задач?
Если вы имеете ввиду mixed integer programming, то, насколько мне известно, в scipy нет солвера для такого типа задач. Посмотрите на cvxpy.
Согласно документации, на данный момент в scily.linprog поддерживается только simplex. Для ILP (integer linear programming) подходят pulp, cvxopt
А почему бы не использовать cvxopt? Это, пожалуй, самый мощный пакет для выпуклой оптимизации.
Вы правы, cvxopt более мощный пакет. Scipy был просто под рукой)
Статья интересная. Я даже и не знал что scipy можно использовать для решения задач линейного программирования.

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

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

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

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

Из любопытства сделал ту же задачу на 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)))

Screen Shot 2019-11-04 at 02 16 20
Sign up to leave a comment.

Articles