16

線形計画法の問題を解決する必要がある Python スクリプトがあります。問題は、ソリューションがバイナリでなければならないことです。つまり、MATLAB のbintprog関数に相当するものが必要です。NumPy と SciPy にはそのような手順はないようです。次の3つのことのいずれかを行う方法について、誰か提案がありますか?

  • そのような関数を含む Python ライブラリを見つけてください。

  • より一般的な線形計画法ソルバーで解けるように問題を制限します。

  • bintprogを直接使用できるように、Python と MATLAB をインターフェイスします。

4

3 に答える 3

7

厳密に言うと、問題がバイナリ プログラミングの問題である場合、それは線形プログラムではありません。

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
于 2010-07-24T20:25:31.000 に答える
5

これは半分の答えですが、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/

PythonとMATLABのインターフェースについては、私は自分のソリューションをロールバックするだけです。.mファイルを生成し、コマンドラインから実行することができます

% matlab -nojava myopt.m

注：

  1. アカデミックユーザーの場合は、高性能LP/MILPソルバーであるGurobiの無料ライセンスを取得できます。Pythonインターフェースを備えています。 http://www.gurobi.com/
  2. OpenOptは、さまざまなソルバーとインターフェイスするPython最適化スイートです。 http://en.wikipedia.org/wiki/OpenOpt
于 2010-07-24T17:43:22.727 に答える
1

pip install gekko私は、線形、二次、非線形、および混合整数計画法 (LP、QP、NLP、MILP、MINLP) を使用して大規模な問題を解決するgekko ( ) というパッケージを開発し、MIT ライセンスの下でリリースされています。バイナリ変数は、下限 0 と上限 1 を持つ整数変数型として宣言されb=m.Var(integer=True,lb=0,ub=1)ます。を使用して複数のバイナリ変数を定義する場合の、より完全な問題を次に示します。m.Array()

from gekko import GEKKO
m = GEKKO()
x,y = m.Array(m.Var,2,integer=True,lb=0,ub=1) 
m.Maximize(y)
m.Equations([-x+y<=1,
             3*x+2*y<=12,
             2*x+3*y<=12])
m.options.SOLVER = 1
m.solve()
print('Objective: ', -m.options.OBJFCNVAL)
print('x: ', x.value[0])
print('y: ', y.value[0])
于 2021-09-01T17:17:19.120 に答える