PuLP очень медленный при добавлении многих ограничений

Question

Я пытаюсь использовать PuLP, но для добавления 4000 ограничений требуется 67 секунд (с 67 переменными). Решение проблемы занимает доли секунды.

Мы хотим использовать PuLP для простого тестирования нескольких решателей на большом наборе проблем.

Стоит ли так долго принимать PuLP? Использование PyGLPK напрямую занимает всего лишь долю секунды, включая настройку и решение, поэтому я надеюсь, что нет. Что я могу сделать, чтобы повысить эффективность этого шага в PuLP?

---

Обновить

Моя матрица ограничений очень скудна, и я смог сократить время настройки до 4 или 5 секунд для этой конкретной задачи, включив только ненулевые коэффициенты. Я все еще могу написать свой собственный файл в формате.lp или.mps, решить проблему с помощью подпроцесса cbc или glpsol и проанализировать решение гораздо более эффективно, чем PuLP, просто потому, что я могу записать входной файл за несколько мс при PuLP занимает несколько секунд Я все еще не уверен, почему это будет.

Answer 1

У меня недостаточно повторений, чтобы комментировать.

Но вы смотрели на это:

https://groups.google.com/forum/

Вопрос задан:

"The problem is solved in less than 0.5 second.
However setting it up with PULP takes more than 10 seconds. "

Похоже, это то, что вы сообщаете. И решение состоит в том, чтобы не использовать операторы += или sum(...), а вместо этого, как объяснено в ссылке:

yeah using the += operator with pulp is really slow, as is using sum() 
instead of lpSum()

Так, может быть, вы добавляете ограничения по 1 к PuLP вместо того, чтобы сначала создавать список ограничений, а затем, в конце, добавить ограничения к PuLP?

Answer 2

У меня была аналогичная проблема с выражением с> 10000 переменных, которое я использовал для своей целевой функции. Основная причина была та же, что и на оригинальном плакате. С помощьюsum на массиве pulp.LpVariable действительно медленный по сравнению с pulp.LpAffineExpression. Основываясь на обсуждении групп Google в принятом ответе, я смог сделать свой код намного быстрее. Я знаю, что это старый вопрос, но он будет включать некоторый абстрактный код для нетерпеливых.

Первоначальная цель выглядела так:

sum([x * k for x in xs] + ys)

где xs это список pulp.LpVariable, k - константа с плавающей запятой, а ys это еще один список pulp.LpVariable.

Более быстрая версия:

pulp.LpAffineExpression([(x, k) for x in xs] + [(y, 1.0) for y in ys])

Я не рассчитал точное время ни для одной из версий. Чтобы дать представление о разнице во времени при запуске медленной версии, я смог поискать в Интернете, почему пульпа может быть такой медленной, найти этот вопрос Stackru, прочитать связанное обсуждение и обновить свой код до того, как выражение было завершено с оценкой. Вторая версия занимает несколько секунд.