Решение задач линейного программирования с использованием Python

[dvemnt]

Python 2.* и вырвиглазное форматирование — классика.

[Andy_U]

Python 3.x — print не оператор, а функция. Ну, пробел перед скобкой… Строчки «from __future__ import print_function» нет.

[chemtech]

Использовали IPython (Jupyter) Notebook или нет?

[hardtop]

Очень наглядно, с примерами. Спасибо ща статью!

[Dark_Daiver]

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

Я совершенно не специалист в оптимизациях, но все же я не уверен что корректно сравнивать scipy linprog и cvxopt.
Первый — просто вызов симплекс солвера по готовым матрицам.
https://docs.scipy.org/doc/scipy-0.15.1/reference/generated/scipy.optimize.linprog.html

cvxopt же — целый DSL (т.е. вам не нужно в ручную подготавливать данные для солвера) позволяющий решать намного больший класс задач.
Так же, в примере с cvxopt использовался солвер glpk (https://www.gnu.org/software/glpk/), который вроде как предназначен для работы с задачами большой размерности («The GLPK (GNU Linear Programming Kit) package is intended for solving large-scale linear programming (LP)»). Т.е. в статье сравнивается теплое с мягким.

[Dark_Daiver]

Если что — я открыт для дискуссии

[Scorobey]

Цель статьи не тестирование библиотек, а сравнение интерфейсных возможностей решателей для двух конкретных групп задач линейного программирования.Различные формы представления исходных данных с использованием матрицы для формирования функции цели и без влияет на аппаратное время выполнения программы.При усреднении времен такое сравнение корректно и оправдано.В статье не рассматривались возможности библиотек в целом, поэтому утверждение о том что cvxopt позволяет решать намного больший класс задач отношение к статье не имеет. Кроме того само утверждения голословно — какой класс, каких задач.
Спасибо за комментарий.

[Dark_Daiver]

Окей, давайте по порядку.

>Цель статьи не тестирование библиотек, а сравнение интерфейсных возможностей решателей для двух конкретных групп задач линейного программирования
В таком случае, на это стоило делать акцент.
К тому же, мне кажется что если мы сравниваем библиотеки по способу задания задачи, cvxopt/pulp явно предпочтительней. Почему? Потому что они позволяют писать значительно более читаемый и поддерживаемый код.
Ограничения добавляются/удаляются в cvxopt одной строчкой. Функционал так же очень легко модифицируется. Фактически вы просто пишете формулы описывающие ограничения и функционал.
Если же матрицы сформированы вручную, то это разумеется более эффективно, но читать и работать с таким кодом довольно неприятно. Как минимум вам придется писать комментарии

Собственно код из вашей статьи.
Это cvxopt. Если нормально назвать переменные (x1 — moneyForTVAd x2 — moneyForRadioAd) и ф-ии (z — negativeSalesIncr и т.д.), то понять какую именно задачу вы решаете, сможет даже человек не знакомый с предметной областью

x = variable(2, 'x')
z=-(30*x[0] +1*x[1])#Функция цели
mass1 = (90*x[0] + 5*x[1]  <= 10000) #"1"
mass2 = (3*x[0] -x[1] == 0) # "2"
x_non_negative = (x >= 0) #"3"   

Это та же самая задача, но решаемая при помощи linprog (если я не ошибаюсь, конечно).
Работать можно и с этим, но согласитесь, это значительно менее приятно чем работать с кодом выше.

c = [-30,-1] #Функция цели
A_ub = [[90,5]]  #'1'   
b_ub = [10000]#'1'   
A_eq = [[3,-1]] #'2'   
b_eq = [0] #'2'   

Идем дальше
>Различные формы представления исходных данных с использованием матрицы для формирования функции цели и без влияет на аппаратное время выполнения программы.
Да, это разумеется так.
>При усреднении времен такое сравнение корректно и оправдано.
И это тоже верно, вот только я не увидел чтобы вы решали запускали решение LP задач тысячу раз, чтобы говорить об усреднении. Но это не самое страшное. Проблема в том, что на задачах очень малой размерности на время выполнения начинает сильно влиять различный .Overhead. Overhead от вызова самих питоновских функций (если анализ задачи оптимизации в cvxopt выполняется на питоне, то он может занимать больше времени чем сама оптимизация), overhead от вызова C/C++ кода, и т.д.
Более того, как я и писал выше, linprog и cvxopt (в вашем случае) используют разные алгоритмы оптимизации заточенные под разные случаи. Симплекс-метод хорошо подходит для небольших задач (как ваши), GLPK же (если я правильно понял) использует итеративный алгоритм и заточен под большие задачи (т.е. сотни тысяч переменных/ограничений). Подозреваю, что у cvxopt есть и другие солверы, однако у вас вызывается именно этот. Собственно на этом можно остановиться, сравнение производительности в такой ситуации смысла не имеет.

>Кроме того само утверждения голословно — какой класс, каких задач.
Выпуклые оптимизации же =) CVXOPT — ConVeX OPTimization.