Python中的二元線性規劃求解器

我有一個Python腳本，我需要解決一個線性規劃問題。問題在於解決方案必須是二元的。換句話說，我需要一個相當於MATLAB的bintprog函數。 NumPy和SciPy似乎沒有這樣的程序。有沒有人有如何我可以做這三件事之一的建議：Python中的二元線性規劃求解器

找到一個Python庫，其中包括這樣的功能。
限制問題，使其可以通過更一般的線性規劃求解器來解決。
接口與MATLAB的Python，以便直接使用bintprog。

來源

2010-07-24 tlayton

這是一個半答案，但您可以使用Python與GLPK（通過python-glpk）接口。 GLPK支持整數線性程序。（二進制程序只是整數程序的一個子集）。

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

或者你可以簡單地用Python語言編寫你的問題，並生成一個MPS文件（其中大部分標準LP/MILP（CPLEX，Gurobi，GLPK）求解接受）。這可能是一條很好的路線，因爲據我所知，沒有任何原生Python的高質量MILP求解器（並且可能永遠不會）。這也可以讓你嘗試不同的求解器。

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

至於與MATLAB接口的Python，我只想推出自己的解決方案。你可以生成一個.m文件，然後在命令行

% matlab -nojava myopt.m

注意運行：

如果你是一個學術的用戶，你可以得到一個免費的許可Gurobi，一高性能LP/MILP解算器。它有一個Python界面。 http://www.gurobi.com/
OpenOpt是一個Python優化套件，可以與不同的求解器進行交互。 http://en.wikipedia.org/wiki/OpenOpt

來源

2010-07-24 17:43:22 Gilead

只是要嚴謹，如果問題是一個二進制編程問題，那麼它是不是一個線性規劃。您可以嘗試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

來源

2010-07-24 20:25:31 Alejandro

添加約束'0 <= x <= 1'不會生成二進制程序。它只是二進制程序的LP放鬆，可以用作二進制程序解決方案的一部分。 – Peter 2010-07-24 20:40:25

我的意思是將Integer程序中的約束0 <= x <= 1添加到整數程序中（您可以使用CVXOPT解決上述問題），將整數程序轉換爲二進制程序。 – Alejandro 2010-07-25 01:06:44

好吧，是的，沒有。僅具有二進制/整數變量的線性程序被稱爲ILP（整數線性程序）。具有二進制/整數變量和連續變量的線性程序稱爲MILP（混合整數線性程序）。術語「整數」和「二進制」在這種情況下可互換使用，因爲可以使用多個二進制變量（即SOS類型1）來表示任何整數變量。但是，如果將x聲明爲一般整數變量，則應該強制0 <= x <= 1，這是正確的。但是，在大多數情況下，x可以直接聲明爲二元變量。 – Gilead 2010-07-26 05:31:20

Python中的二元線性規劃求解器

回答

相關問題