binäre lineare Programmierung Solver in Python

Question

Ich habe ein Python-Skript, in dem ich ein lineares Programmierproblem lösen muss. Der Haken ist, dass die Lösung binär sein muss. Mit anderen Worten, ich brauche ein Äquivalent von MATLABs bintprog Funktion. NumPy und SciPy scheinen keine solche Prozedur zu haben. Hat jemand Vorschläge, wie ich eines dieser drei Dinge tun könnte:

Finden Sie eine Python-Bibliothek, die eine solche Funktion enthält.

Beschränken Sie das Problem so, dass es von einem allgemeineren linearen Programmierlöser gelöst werden kann.

Schnittstelle Python mit MATLAB, um so direkt bintprog zu verwenden.

Answer 1

Dies ist eine Halbantwort, aber Sie können Python verwenden, um mit GLPK zu interagieren (über Python-glpk). GLPK unterstützt ganzzahlige lineare Programme. (Binärprogramme sind nur eine Teilmenge von Ganzzahlprogrammen).

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

Oder Sie könnten einfach Ihr Problem in Python schreiben und eine MPS-Datei erzeugen (die meisten Standard-LP/MILP (CPLEX, Gurobi, GLPK) Solver akzeptieren). Dies kann ein guter Weg sein, da, soweit ich weiß, es keine hochwertigen MILP-Löser gibt, die nativ für Python sind (und das wird es auch nie geben). Dies ermöglicht Ihnen auch, verschiedene Löser auszuprobieren.

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

Wie für Python mit MATLAB Schnittstelle, würde ich nur meine eigene Lösung rollen. Sie könnten eine .m-Datei erzeugen und dann von der Kommandozeile

% matlab -nojava myopt.m 

Hinweise laufen:

1. Wenn Sie einen akademischen Benutzer sind, können Sie eine kostenlose Lizenz zu Gurobi bekommen, eine Hochleistungs-LP/MILP-Löser. Es hat eine Python-Schnittstelle. http://www.gurobi.com/
2. OpenOpt ist eine Python-Optimierungssuite, die mit verschiedenen Solvern verbunden ist. http://en.wikipedia.org/wiki/OpenOpt

Answer 2

nur streng zu sein, wenn das Problem ein binäres Programmierproblem ist, dann ist es kein lineares Programm.

Sie können versuchen CVXOPT. Es hat eine ganzzahlige Programmierfunktion (siehe this). Um Ihr Problem ein binäres Programm zu machen, müssen Sie die constrain hinzufügen 0 < = x < = 1.

bearbeiten: Sie können tatsächlich Ihre Variable als binäre erklären, so dass Sie nicht hinzufügen müssen, um die constrain 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