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

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

15 голосов
/ 24 июля 2010

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

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

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

  • Интерфейс Python с MATLAB для непосредственного использования bintprog .

Ответы [ 2 ]

8 голосов
/ 25 июля 2010

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

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

Edit : вы можете объявить вашу переменную как двоичную, так что вы не будетенужно добавить ограничение 0 <= x <= 1. </p> 

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
4 голосов
/ 24 июля 2010

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