решатель бинарного линейного программирования в Python

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

  • Найдите библиотеку Python, в которой есть такая функция.

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

  • Интерфейс Python с MATLAB, чтобы напрямую использовать bintprog.


python matlab linear-programming
person tlayton    schedule 24.07.2010    source источник

Ответы (2)


arrow_upward
7
arrow_downward

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

Вы можете попробовать CVXOPT. Он имеет функцию целочисленного программирования (см. это). Чтобы сделать вашу задачу двоичной программой, вам нужно добавить ограничение 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
person Alejandro    schedule 24.07.2010
comment
добавление ограничения 0 <= x <= 1 не создает двоичную программу. это просто LP-релаксация бинарной программы, и ее можно использовать как часть метода решения бинарной программы. - person Peter; 25.07.2010
comment
Я имею в виду добавить ограничение 0 ‹= x ‹= 1 к целочисленной программе (которую вы можете решить с помощью CVXOPT, как указано выше), чтобы преобразовать целочисленную программу в двоичную программу. - person Alejandro; 25.07.2010
comment
Ну.... и да и нет. Линейная программа только с двоичными/целочисленными переменными называется ILP (целочисленная линейная программа). Линейная программа как с двоичными/целочисленными переменными, так и с непрерывными переменными называется MILP (смешанная целочисленная линейная программа). Термины «целое» и «двоичное» в этом контексте взаимозаменяемы, поскольку любая целочисленная переменная может быть представлена ​​с помощью нескольких двоичных переменных (т. е. SOS типа 1). Но вы правы, говоря, что нужно ввести 0 ‹= x ‹= 1, если x объявлен как общая целочисленная переменная. Однако в большинстве случаев x можно прямо объявить как двоичную переменную. - person Gilead; 26.07.2010

arrow_upward
4
arrow_downward

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

Примечания:

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