10

整数線形最適化問題があり、実行可能で優れたソリューションに興味があります。私の知る限り、たとえば、Gnu線形計画法キットは最適な解のみを返します（存在する場合）。これには無限の時間がかかり、私が探しているものとは異なります。最適なソリューションだけでなく、優れたソリューションにも満足しています。

したがって、たとえばしばらくして停止し、これまでに見つけた最良のソリューションを返すLPソルバーがその役割を果たします。

そのようなソフトウェアはありますか？そのソフトウェアがオープンソースであるか、少なくともビールのように無料であるなら、それは素晴らしいことです。

あるいは：通常整数LPの問題をスピードアップする他の方法はありますか？これは質問するのに適切な場所ですか？

4

5 に答える 5

8

多くのソルバーは時間制限パラメーターを提供します。制限時間パラメータを設定すると、制限時間に達すると停止します。整数の実行可能なソリューションが見つかった場合、その時点で見つかった最良の実行可能なソリューションが返されます。

ご存知かもしれませんが、整数計画法はNP困難であり、最適なソリューションと実行可能な優れたソリューションをすばやく見つけるための実際の技術があります。さまざまなソルバーを比較するには、HansMittelmann教授の最適化ソフトウェアのベンチマークを参照してください。MILPベンチマーク-特にMIPLIB2010と実現可能性ベンチマークが最も関連性が高いはずです。

優れたソルバーを選択することに加えて、ソルバーのパラメーターの調整やモデルの再定式化など、ソルバー時間を改善するために実行できることがたくさんあります。私を含む研究および業界の多くの人々は、一般的および特定のモデルの両方で、MIPモデルの解決時間の改善に私たちのキャリアを費やしています。

アカデミックユーザーの場合、CPLEXやGurobiなどの上位の商用システムは無料でアカデミックに使用できることに注意してください。詳細については、それぞれのWebサイトを参照してください。

最後に、オペレーションズリサーチの分野に焦点を当てたStackOverflowの姉妹サイトであるOR-Exchangeをご覧ください。

（免責事項：私は現在Gurobi Optimizationで働いており、以前はCPLEXを提供していたILOGで働いていました）。

于 2011-10-06T23:20:51.393 に答える
4

実現可能な整数解を高速で取得したい場合、および最適な解が必要ない場合は、次のことを試すことができます。

  1. 相対ギャップまたは絶対ギャップを増やします。通常、ソルバーには、相対ギャップに対して0.0001％などの小さなギャップがあります。これは、ソルバーがMIPソリューションが最適なソリューションから0.0001％以内に離れるまで、MIPソリューションの検索を継続することを意味します。このgabをたとえば1％に増やします。これで、適切なソリューションが得られますが、ソルバーは最適性の証明に長い時間を費やすことはありません。

  2. MIPヒューリスティックに関するソルバーパラメーターにさまざまな値を試してください。

  3. CPLEXとGUROBIには、制御するパラメーター、MIP強調があります。これは、ソルバーが実行可能なソリューションの検索または最適性の証明にさらに重点を置くことを意味します。実行可能なMIPソリューションに重点を置きます。

CPLEX、Gurobi、MOPS、GLPKなどのほとんどのソルバーには、ギャップとヒューリスティックの設定があります。MIPの強調は、私が知る限り、CPLEXとGurobiでのみ設定できます。

于 2013-02-04T09:26:48.687 に答える
1

私の知る限り、CPLEXはできます。検索で主要な実行可能なソリューションを含むソリューションプールを返すことができます。最適性ではなく実行可能性に検索の焦点を指定すると、より実行可能なソリューションを生成できます。最後に、プールをエクスポートするだけです。あなたはそれがあなた次第であるようにホットスタートをするためにプールを使うことができます。CPlexは、研究者として登録できるため、少なくとも私の国では無料です。

于 2012-08-03T01:59:52.323 に答える
1

ILPを解決するための通常のアプローチは、分枝限定法です。これは、多くのサブLP（Iなし）のソリューションを利用しました。最終的に最適な結果は、すべてのサブLPの中で最高です。少なくとも1つの解決策が見つかったので、いつでも停止でき、これまでで最高の解決策が得られます。

それを行うことができる1つのパッケージは、無料のlpsolveです。制限時間を与えるためにset_timeoutを見てください。それがILPの場合、solve関数はSUPOPTIMALでbest_so_far値を返すことができます。

于 2011-10-06T08:45:05.927 に答える
0

Microsoft Solver Foundationを考慮に入れていただけますか？唯一の制限は、好みのテクノロジスタックであり、ここでは、ご想像のとおり、Microsoftテクノロジ（C＃、vb.netなど）を使用する必要があります。Excelでの使用方法の例を次に示します。http：//channel9.msdn.com/投稿/Modeling-with-Solver-Foundation-30。

あなたの質問に関しては、効率を設定した場合（たとえば、85％または0.85）、完全に最適化されたソリューションがない可能性があります。結果として、そのような制限に対して考えられるすべての解決策を見ることができます。

于 2011-10-06T08:20:23.657 に答える