3

今日、整数線形計画法を実装する必要があるかもしれませんが、それを実装する方法を説明する疑似コードまたは比較的痛みのない (よくコメントされた) ソースコードがあるかどうか疑問に思っていますか? 疑似コードを強く好む。

最適なパフォーマンスを得るためのすべての「微調整」を含む本格的な完全なプロジェクトを探しているわけではないことに注意してください。整数線形計画法がどのように機能するか、すべてのオプションを 1 つずつ試す方法を示す最も基本的なソルバーを探しています。

ありがとう。

4

1 に答える 1

8

この質問は大きな質問なので、段階的に試してみましょう。

Integer Linear Programと言うとき、線形制約と目的関数を持つ IP を意味すると思います。

1. シンプレックス アルゴリズムから始めます。 (ただし、線形プログラムに「完全性」プロパティがある「幸運な」場合を除いて、これは IP では機能しません。) しかし、シンプレックスは常に開始するのに適した場所です。あなたは第一原理アプローチに興味があるので

驚くべきことに、解決済みの例はたくさんありますが、PseudoCode を見つけるのはそれほど簡単ではありません。 シンプレックス アルゴリズムのステップの一例を次に示します。(疑似コードではありません)

セクション3.1.4 計算手順の要約には、疑似コードに近いものがあります。

このドキュメントには、実装可能なシンプレックス アルゴリズムの概要も含まれています。前のセクションの例に従った場合。

シンプレックスは、比較的理解しやすい (特にステップバイステップ) アルゴリズムの 1 つですが、実装が難しいことで有名です。これがなぜそうなのかについての本当に良い議論は、ここで見つけることができます。

2. 整数計画法 - 「最も単純な」ケース。多くの人は「ナップザック」問題 から始める傾向があります。

疑似コードと Java 実装の両方をここで見つけることができます。

3. IP の難易度/複雑さが増しています。

  • 資本予算の問題
  • 割り当ての問題
  • 交通機関の問題

4. 汎用 vs 特化 選択肢があります。

  • 4a. 「汎用」の IP ソルバーをビルドできます (ただし、実行には非常に時間がかかります)。
  • 4b. 特殊なタイプの問題用に専用の IP ソルバーを構築します。

4a の場合: 0/1 変数を想定して、分岐限定手法を示すことができます。ツリーの実装を見つけて、独自の目的に合わせて変更できます。(本質的に、徹底的な検索の巧妙な実装です。)

4b の場合: 1 つのケース、たとえば割り当て問題を取り上げることができます。ハンガリーのアルゴリズムは理解しやすく、学生のグループに一度に教えることができるため 、ハンガリーのアルゴリズムがよく使用されます。このトップコーダーのチュートリアルでは、数学、疑似、および実際のコードで非常に広範囲にカバーしています。

長い答えですが、これがあなたが望んでいることの線に沿っていることを願っています.

于 2012-10-10T00:14:46.700 に答える