binarne programowanie liniowe w Pythonie

Question

Mam skrypt Python, w którym muszę rozwiązać problem programowania liniowego. Połów jest taki, że rozwiązanie musi być binarne. Innymi słowy, potrzebuję odpowiednika funkcji MATLABa bintprog. NumPy i SciPy nie wydają się mieć takiej procedury. Czy ktoś ma sugestie, w jaki sposób można wykonać jedną z tych trzech rzeczy:

• Znajdź bibliotekę Python, która zawiera taką funkcję.

• Ogranicz problem tak, aby można go było rozwiązać za pomocą bardziej ogólnego programu do programowania liniowego.

• Interfejs Python z MATLAB do bezpośredniego użycia z bintprog.

Answer 1

To jest połowa odpowiedzi, ale można użyć Pythona do połączenia z GLPK (przez python-glpk). GLPK obsługuje całkowite programy liniowe. (programy binarne są tylko podzbiorem programów całkowitych).

http://en.wikipedia.org/wiki/GNU_Linear_Programming_Kit

Albo można po prostu napisać swój problem w Pythonie i wygenerować plik MPS (których większość standardowych LP/MILP (CPLEX, Gurobi, glpk) rozwiązują zaakceptuje). To może być dobra droga do podjęcia, ponieważ o ile mi wiadomo, nie ma żadnych wysokiej jakości solverów MILP, które są rodzime dla Pythona (i może nigdy nie być). Pozwoli to również wypróbować różne rozwiązania.

http://code.google.com/p/pulp-or/

chodzi o łączenie Pythona z MATLAB, chciałbym po prostu toczyć własne rozwiązanie. Można wygenerować plik .m a następnie uruchomić go z linii poleceń

% matlab -nojava myopt.m 

Notatki:

1. Jeśli jesteś użytkownikiem akademickiego, można uzyskać bezpłatną licencję na Gurobi, A wydajny solver LP/MILP. Ma interfejs Pythona. http://www.gurobi.com/
2. OpenOpt to pakiet optymalizacyjny Pythona, który łączy się z różnymi rozwiązaniami. http://en.wikipedia.org/wiki/OpenOpt

Answer 2

Wystarczy być rygorystyczny, jeśli problem jest binarnym problemu programowania, to nie jest program liniowy.

Możesz spróbować CVXOPT. Ma funkcję programowania całkowitoliczbowego (patrz this). Aby dokonać problemu także program binarny, trzeba dodać Powiąż 0 < = x < = 1.

Edit: Rzeczywiście można zadeklarować zmienną jako binarne, więc nie trzeba dodać Powiąż 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