83

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

GLPK python は MILP 問題を解決できますか? 混合整数問題を解決できると読みました。
私は線形計画問題に非常に慣れていません。したがって、混合整数計画法が混合整数線形計画法(MILP)と異なる場合、私はかなり混乱しており、実際に区別することはできません。

4

2 に答える 2

148

Pulpは、 CBC (オープン ソース)、 CPLEX (商用)、 Gurobi (商用)、 XPRESS-MP (商用)、 YALMIP (オープン ソース) などのソルバーに接続する Python モデリング インターフェイスです。

Pyomoを使用して最適化問題をモデル化し、外部ソルバー、つまり CPLEX、Gurobi GLPK、AMPL ソルバー ライブラリを呼び出すこともできます。

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

さらに別のモデリング言語はCMPLで、これには MIP ソルバー用の Python インターフェイスがあります (線形プログラムのみ)。

上記のすべてのソルバーは混合整数線形計画法を解きますが、そのうちのいくつか (CPLEX、GUROBI、および XRESS-MP は確かです) は、混合整数二次計画法および二次制約付き二次計画法(および円錐計画法もありますが、これはおそらくこの範囲を超えています) を解決できます。質問）。

MIP は混合整数計画を指しますが、通常は線形計画のみを指すために使用されます。用語をより正確にするために、常に MILP または MINLP (混合整数非線形計画法) を参照する必要があります。

CPLEX と GUROBI にも独自の Python API がありますが、これら (および) XPRESS-MP は商用製品ですが、学術研究用には無料であることに注意してください。CyLPは上記の Pulp に似ていますが、COIN-OR ソルバーである CBC および CGL および CLP と連携します。

商用ソルバーと無料ソルバーのパフォーマンスには大きな違いがあることに注意してください。後者は前者に大きく遅れをとっています。SCIPはおそらく最高の非商用ソルバーです (最新情報については以下を参照してください)。その Python インターフェースである PySCIPOpt はこちらです。

また、この SO question もご覧ください。

最後に、(最適化ではなく) 単純な制約ソルバーに興味がある場合は、python-constraintをご覧ください。

これが役立つことを願っています！

アップデート

私のレーダーに落ちたより多くのソルバーと python インターフェイス:

更新: MIPCL リンクが壊れているようです。 最速の非商用 MIP ソルバーと思われるMIPCLには、非常に優れたドキュメントを備えたPython インターフェイスがあります。ただし、Python 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 ソルバーに接続できます。

MIP ソルバーもサポートしていることを指摘してくれたRedPandaに感謝します。CVXOPT/CVXPY

パッケージとオブジェクト指向言語 (Python に限定されない) の最適化モデリング機能に関する非常に包括的な記事については、この記事を確認してください。

于 2014-10-11T11:50:32.290 に答える