[解決済み] Python 混合整数型線形計画法

質問

Pythonの混合整数線形計画法(MILP)ソルバはありますか？

GLPK pythonは、MILP問題を解くことができますか？私はそれが混合整数問題を解くことができると読みました。

私は線形計画問題には非常に新しいです。だから私はむしろ混乱しており、混合整数プログラミングが混合整数線形計画法（MILP）と異なるかどうかを本当に区別することはできません。

どのように解決するのですか？

パルプ のようなソルバにフックアップする Python のモデリングインターフェイスです。 CBC (オープンソース)です。 CPLEX (商用)です。 グロビ (商用)です。 XPRESS-MP (商用) と ヤルミップ (オープンソース)です。

また ピヨモ を使って最適化問題をモデル化し、外部のソルバー、すなわちCPLEX、Gurobi GLPK、AMPLソルバーライブラリを呼び出します。

からGLPKを呼び出すこともできます。 GLPK/Python , PyGLPK または PyMathProg .

さらに別のモデリング言語として CMPL これは、MIPソルバー（線形計画のみ）のためのpythonインターフェースを持っています。

上記のすべてのソルバーは 混合整数 線形 プログラム を解くことができるものもあるが（CPLEX, GUROBI, XRESS-MPは間違いない）。 混合整数 二次関数 プログラム と 二次制約付き二次プログラム (そして、二次曲線プログラムもですが、これはおそらくこの質問の範囲を超えています)。

MIPとはMixed integer programsのことですが、一般的には線形計画だけを指すのに使われます。用語をより正確にするために、常にMILPまたはMINLP（混合整数非線形計画法）を参照する必要があります。

CPLEXとGUROBIは独自のPython APIを持っていますが、それら（とXPRESS-MP）は商用製品であり、学術研究用には無料であることに注意してください。 CyLP は上記のPulpに似ていますが、COIN-ORソルバーのCBCやCGL、CLPとのインタフェースがあります。

以下のことに注意してください。 商用ソルバーとフリーソルバーの性能には大きな差があります。 後者は前者に大きく遅れをとっています。 SCIP は おそらく最高の非商業的ソルバー (アップデートは下記参照)。そのパイソンインターフェースであるPySCIPOptは ここで .

また、以下をご覧ください。 このSOの質問 .

最後に、もしあなたが単純な制約ソルバー（最適化ではない）に興味があるのなら、次のサイトを見てください。 python-constraint .

お役に立てれば幸いです。

更新情報

私のレーダーに引っかかったソルバーと Python インターフェイスを追加しました。

更新：MIPCLのリンクが壊れているようです。 MIPCL は、非商用MIPソルバーとしては最速と思われますが、このソルバーは pythonインターフェース があり、これはかなり 良いドキュメント . しかし、Python API には、ネイティブの API に付属するような高度な機能は含まれていません。 MIPCLShell . 私が特に気に入っているのは MIPCL-PYマニュアル このマニュアルでは、オペレーションズ・マネジメントで使用されるさまざまなモデルを、小規模な実装の上に実証しています。どのソルバー/APIを利用したいかに関わらず、それ自体が非常に興味深い入門マニュアルです。

Google 最適化ツール のような多くの機能を含んでいます。

• 制約プログラミングソルバーと線形計画法 ( MIPではない )ソルバー
• MIPソルバーのインターフェース（CBC, CLP, GLOP, GLPK, Gurobi, CPLEX, SCIPをサポート）。
• グラフ、巡回セールスマン問題、車道問題、ビン詰め問題、ナップサック問題に特化したアルゴリズム

いくつかの伝統的なORの問題と簡単な実装に関する広範なドキュメントがあります。Python API の完全なドキュメントは見つかりませんでしたが、いくつかの例は存在します。 ここに . 他のソルバーがどのようにインターフェースにフックするのか、また、これらのソルバーのメソッドが利用可能なのか、私にはやや不明です。

CVXOPT 凸最適化のためのオープンソースパッケージで、GLPK（オープンソース）および MOSEK (商用)とのインターフェースです。多くの問題クラス（特に線形、2次、半正定値、凸非線形）に取り組むことができ、汎用性が高い。唯一の欠点は、複雑な問題のモデリングが面倒なことで、ユーザはデータを "Matlab-y" 方式で渡す必要があります（つまり、行列やrhsベクトルなどを指定するため）。しかし、これはモデリングインターフェースから呼び出すことができます。 PICOS と...

CVXPY は、凸最適化問題のためのpython組み込みの最適化言語で、以下のものを含みます。 CVXOPT をデフォルトのソルバーとして含みますが，このソルバーは 通常のMIPソルバー .

おかげさまで レッドパンダ が指摘した CVXOPT/CVXPY は MIP ソルバもサポートします。

パッケージやオブジェクト指向言語（Pythonに限らない）の最適化モデリング能力に関する非常に包括的な記事として、以下をご覧ください。 この記事 .