Двоичный алгоритм линейного программирования в Python

У меня есть Python script, в котором мне нужно решить проблему линейного программирования. Улов заключается в том, что решение должно быть двоичным. Другими словами, мне нужен эквивалент функции MATLAB bintprog. У NumPy и SciPy нет такой процедуры. У кого-нибудь есть предложения о том, как я мог бы сделать одну из этих трех вещей:

Найдите библиотеку Python, которая включает такую функцию.
Задайте проблему таким образом, чтобы ее можно было решить с помощью более общего решения линейного программирования.
Интерфейс Python с MATLAB, чтобы напрямую использовать bintprog.

Ответ 1

Просто, чтобы быть строгим, если проблема является проблемой двоичного программирования, то это не линейная программа.

Вы можете попробовать CVXOPT. Он имеет целочисленную функцию программирования (см. this). Чтобы сделать вашу проблему двоичной программой, вам нужно добавить ограничение 0 <= x <= 1.

Изменить: вы можете объявить свою переменную как двоичную, поэтому вам не нужно добавлять ограничение 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

Ответ 2

Это полу-ответ, но вы можете использовать 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

Примечания

Если вы академический пользователь, вы можете получить бесплатную лицензию на Gurobi, высокопроизводительный решатель LP/MILP. Он имеет интерфейс Python. http://www.gurobi.com/
OpenOpt - это пакет оптимизации Python, который взаимодействует с различными решателями. http://en.wikipedia.org/wiki/OpenOpt