最高のオープンソース混合整数最適化ソルバー [終了]
質問
現在、大規模な最適化モデル (100,000 個を超える変数) を解決するために CPLEX を使用しています。オープンソースの代替手段が見つかるかどうかを確認したいと考えています。混合整数問題 (MILP) を解決しています。CPLEX はうまく機能しますが、コストが非常に高くなります。スケーリングしたいので、代替手段を見つけるか、独自のアドホック最適化ライブラリを書き始める必要があります (これは大変なことになります)
あらゆる提案/洞察をいただければ幸いです
解決
私が個人的に GLPK を良好(即ち速い)lp_solveはより発見しました。これは、さまざまなファイル形式をサポートしており、更なる利点は、アプリケーションとのスムーズな統合を可能にするそのライブラリインタフェースです。
他のヒント
COIN-OR のためのもう一つのお墨付き。私たちは、線形オプティマイザコンポーネント(CLP)が非常に強かった、および混合整数成分(CBC)は、いくつかの分析を非常によく調整することができることを発見しました。私たちは、LP-解決し、GLPKと比較します。
本当にタフな問題については、商用ソルバーが移動するための方法である。
SCIPソルバーを試してみてください。私は、優れた性能と300K以上の変数とのMILP問題のためにそれを使用しています。そのMILP性能はGLPKよりもはるかに優れています。 GurobiもMILP問題(と一般的にSCIP(2011年5月)よりも良い)のための優れた性能を持っていますが、あなたはアカデミックユーザーでない場合、それはコストがかかるかもしれません。 Gurobiソルバーをスピードアップするためにマルチコアを使用します。
やってみました lp_solve
?Java に関する次の質問には、他にもいくつかの提案がありました。
私があなただったら、Osi (C++) や PuLP (Python) などのマルチソルバー インターフェイスを使用して、一度コードを記述して、多くのソルバーでテストできるようにするでしょう。
解こうとしている整数プログラムが巨大な場合は、C++ ではなく Python をお勧めします。コードがすっきりして見え、時間の 99% がソルバーに費やされるからです。
逆に、問題が小さい場合は、問題を Python のメモリからソルバーに (前後に) コピーする時間は無視できなくなります。その場合は、コンパイル言語を使用して、顕著なパフォーマンスの向上を実験してみるとよいでしょう。
しかし、問題が圧倒的に大きい場合は、メモリ使用量がおよそ 2 で割られるため、コンパイル言語が再び勝つことになります (Python では問題のコピーがありません)。
私はCOINプロジェクトをチェックアウトをお勧めします。 コインなどの
ipOPTを含め、ここで多くの良いソルバー、 非線形問題とカップルのための 混合整数ソルバーも。
SCIP のは悪いことではありません!
これはあなたが聞きたいのですが、光年は、他方で商用ソルバーCPLEXとGurobiとオープンソースのソルバー間にあるかそうでないかもしれないですが。
それにもかかわらず、あなたは幸運であることができ、あなたのモデルがGLPK、コイン等で正常に動作しますが、一般的なオープンソース・ソリューションの商用ソルバーの背後にある方法です。それは異なっていた場合、誰がCPLEXライセンスの12.000 Gurobiライセンスの$とさらに多くを支払うことないだろう。
過去数年間で、私は、オープンソースのソルバーのためだけに困難にした多くの、多くのモデルを見てきました。
...私を信じてこれはそんなに大きさの、しかし、数字の難しさの問題ではありません。
100Kの変数に大きな問題です。オープンソースライブラリの多くは、その多くの変数でうまく機能しません。私が何を読んでからlp_solveははわずか約30Kの変数のためにテストされています。商用システムを使用することで、あなたの唯一の選択肢かもしれません。
私はNEOSサーバーを使用してDICOPTを使用していた(のhttp:/ /www.neos-server.org/neos/solvers/minco:DICOPT/GAMS.html の)大きな(約変数および1K制約1K)混合整数非線形プログラムを解決し、それが優れた見出さへ。
私の問題についてDICOPTはネオスサーバBARON / KNITRO / LINDO / SBBなどに記載されている他のMINLPソルバーよりもはるかに良いをやっています。
がありNEOSにジョブを提出する一定の制約があり、それは少し面倒ですが、より強力な商用ソルバーへの無料アクセスは、それを補っています。
私はすでに優秀な答えに、以下を追加します。
他の人が指摘したように、商用ソルバーはより速く、より有能な、それはあなたが受け入れることができる最適ギャップのどれだけを考慮することが重要だ自由の選択肢よりも、なくなり。あなたは1%またはさらに大きな最適ギャップを受け入れることができれば、多くの整数変数を持つ大規模な問題のためにあなたがはるかに高速に解く倍を得ることができます(デフォルト値は約0.01%以下とする傾向がある)。
もちろん、あなたは1%がこれを許容できない数百万ドルに換算問題解決されている場合 - 一流のソルバーのために、したがって、市場を。 (ここを無料ソルバーにGurobiのいくつかの比較が)
私はあなたが、他のソルバーを試すことができるよう(な* .mps、* .LPファイルなど)ソルバーに依存しない、問題のファイルを生成プラットフォームを使用することは価値があることを他の人と同意するだろう。私はパルプを使用していて、それを見つけています優れた、無料のCOIN_CBCソルバー、。多くの整数変数に問題のために制限されますが。
私は誰もが言及していないことを驚いてMIPCL(のhttp://www.mipcl- cpp.appspot.com/index.htmlする)。 ます。http://www.mipclこのソルバーはLGPLライセンス(ソースの下でオープンソースであることを主張します-cpp.appspot.com/licence.html に)、従ってまた、非オープンソースアプリケーションで使用するのに適しています。しかし、実際にオープンソースであることを欠けていることは、ソルバー自体のソースコードです。
ます。http:/非常に最近ハンスMittelmann(2017年9月10日)は、混合整数線形計画ベンチマークを行いました/plato.asu.edu/ftp/milpc.html
を(あなたはまた、概要ページ<のhref =「http://plato.asu.edu/bench.html」のrel =」を見に興味があるかもしれませんnoreferrer nofollowを "> http://plato.asu.edu/bench.html のか、彼の話のスライド:<のhref =" http://plato.asu.edu/talks/informs2017.pdf」のrel = "nofollowをnoreferrer"> http://plato.asu.edu/talks/informs2017.pdf の)ます。12件のスレッドと混合整数線形計画ベンチマーク、2時間の制限時間でMIPCL 79個のインスタンスを解決することができました。 CPLEX、GurobiとXPRESSは、与えられた制約(86のまたは87の場合、それぞれ)の下でより多くを解決するために管理します。
のみ商用ソルバーまた、選択されたパフォーマンスメトリックの観点MIPCLがベンチマークSCIP誘導体(FSCIPC、FSCIPS)とオープンソースソルバCBCよりも高速である(再び12個のスレッドを使用)。再び、唯一の商用ソルバーCPLEX、GurobiとXPRESSは、パフォーマンスの面で大幅にMIPCLを打ち勝つます。
オープンソースではないが、あなたは、マイクロソフトアカデミックアライアンスのライセンスを持っている場合は、マイクロソフトソルバー財団(MSF)は、エンタープライズ版が含まれています。 Gurobi にも学術目的のために無料ですが、私は私の論文の研究でそれを使用しました。