двоичный линейный решатель программирования в Python
У меня есть сценарий Python, в котором я должен решить линейную проблему программирования. Выгода - то, что решение должно быть двоичным. Другими словами, мне нужен эквивалент функции bintprog MATLAB. NumPy и SciPy, кажется, не имеют такую процедуру. Делает у любого есть предложения о том, как я мог сделать одну из этих трех вещей:
Найдите библиотеку Python, которая включает такую функцию.
Ограничьте проблему, таким образом, что она может быть решена более общим линейным решателем программирования.
Соедините интерфейсом с Python с MATLAB, чтобы сделать прямое использование bintprog.
2 ответа
Чтобы быть строгим, если проблема является проблемой двоичного программирования, то это не линейная программа.
Вы можете попробовать CVXOPT. В нем есть функция целочисленного программирования (см. this). Чтобы сделать вашу задачу бинарной программой, нужно добавить ограничение 0 <= x <= 1.
Edit: На самом деле вы можете объявить свою переменную как двоичную, поэтому вам не нужно добавлять ограничение 0 <= x <= 1.
cvxopt.glpk.ilp = ilp(...)
Solves a mixed integer linear program using GLPK.
(status, x) = ilp(c, G, h, A, b, I, B)
PURPOSE
Solves the mixed integer linear programming problem
minimize c'*x
subject to G*x <= h
A*x = b
x[I] are all integer
x[B] are all binary
Это полуответ, но вы можете использовать Python для взаимодействия с GLPK (через python-glpk). GLPK поддерживает целочисленные линейные программы. (Двоичные программы - это просто подмножество целочисленных программ).
http://en.wikipedia.org/wiki/GNU_Linear_Programming_Kit
Или вы можете просто написать свою задачу на Python и сгенерировать файл MPS (который будет принят большинством стандартных решателей LP/MILP (CPLEX, Gurobi, GLPK)). Это может быть хорошим вариантом, поскольку, насколько я знаю, не существует высококачественных MILP-решателей, которые были бы встроены в Python (и, возможно, никогда не появятся). Это также позволит вам опробовать различные решатели.
http://code.google.com/p/pulp-or/
Что касается сопряжения Python с MATLAB, я бы просто разработал собственное решение. Вы можете сгенерировать .m файл и затем запустить его из командной строки
% matlab -nojava myopt.m
Notes:
- Если вы являетесь академическим пользователем, вы можете получить бесплатную лицензию на Gurobi, высокопроизводительный решатель LP/MILP. У него есть интерфейс на языке Python. http://www.gurobi.com/
- OpenOpt - оптимизационный пакет на языке Python, который взаимодействует с различными решателями. http://en.wikipedia.org/wiki/OpenOpt