2

スパース線形計画法の問題を解決する必要があり、同じライブラリを探しています。

主な要件:
最も重要な要件は、非常に高速であることです。より高速な場合は、ランダム化された近似解を使用できます。

LP 仕様:
問題のサイズは 2 つのパラメーターの関数です: P と Q で、ほとんどの場合 P << Q です。
変数の数 ~ P + Q
制約の数 ~ 2Q
制約行列はまばらです - O(Q) 個のゼロ以外のエントリしかありません。

試した解決策
1) MATLAB : MATLAB のlinprog関数は、LP を解くのに非常に時間がかかるため、この設定では特に役に立ちません。
2) GLPK : glpk_simplexも期待したほど高速ではありません。P=15、Q=15,000 の問題の場合、最大 10 秒で回答を得る必要がありますが、glpk_simplexは 20 ～ 25 分かかります。上記サイズの問題でglpk_interiorがメモリ不足になります。

誰かが効率的なライブラリを提案できますか? 問題を正確に、またはおおよそ解決するために使用できる、無料のものと市販のものの両方を提案してください。

4

1 に答える 1

2

他のソルバー オプションについては、まだチェックアウトしていない場合に確認する必要がある 2 つの SO の質問を次に示します。

  1. SO 使用するソルバーに関する質問

  2. Java ソルバー オプション

しかし、私が投稿している理由は、ソルバーの速度ではなく、他にもいくつか提案があるからです。(あなたの問題では Q ~ 15K でうまくいくかもしれませんが、Q が大きくなると、さらに高速なソルバーを探す必要があります。)

試してみるべきその他の提案

  1. optionsMATLAB または GLPK でソルバーを試してみましたか? iteration limit、またはTimelimit（10000ミリ秒まで）を設定するなど、試すことができることはたくさんあります。

  2. 調合の分解と緩和を検討してください。通常、これらの大規模な LP には優れた基本構造がありますが、いくつかの密集した制約が台無しになり、ソルバーに問題を引き起こします。それらを特定できる場合は、それらを緩和し、乗数を使用して目的関数に投入することもできます。

    もう少し具体的にするために、「厄介な制約」に対するラグラン緩和を検討します。（私が言及していることへの1つの参照として、ここで問題12.3が 緩和された後に12.4になる方法を確認してください。問題の密集したいくつかの制約に対して同じことを行うことができます.

これがあなたの前進に役立つことを願っています。

于 2013-11-08T00:43:06.810 に答える