バイナリ整数プログラミングの構築ヒューリスティック

Question

私はこの質問に対する答えを見つけようとしていますが、包括的なものは何も見つかりません。私は、バイナリ整数計画問題、より具体的には、集合パッキング、集合パーティショニング、集合カバレッジ問題に対する初期実現可能解を構築するアルゴリズムまたはヒューリスティックを見つけることを検討している。 1は、以下のバイナリ整数計画問題

Minimize  ax_1 + bx_2 + cx_3 
Subject to x_1 + x_2 <= 2 
       3x_1 + 3x_2 >= 6 
       x_2 + 2x_3 = 2 

解表現と

[x_1, x_2, x_3] 

X_I = 0または1

を持っている場合

はその後、どのようにして構築しようとして行くだろうこの問題に対する初期の実現可能な解決策である。問題が何千もの変数と制約で構成されている場合、可能なすべての解決策を実行することは明らかに機能しません。

ここでの目標は、ローカルミニマムを取得するためにローカル検索を実行し、次にこれにメタヒューリスティックを適用できるように初期実現可能性を構築することです。

Answer 1

いくつかのバイナリ整数プログラミング問題の実現可能な解を見つける問題は、既にNP完了です。 Karpの21個のNP完全問題の1つ - >wiki：0-1整数プログラミング！

一般設定では、あまり次完全アプローチ負かす事になります（完全に：彼らは1が有限時間内に存在する場合に実現可能な解決策を見つけるか、何もありません証明します）：

• 整数計画ソルバーは、 （シンプレックス+ブランチとバウンド+カッティングプレーン）
  • Gurobi、CPLEX（市販）またはCBC/GLPK（オープンソース）
• 制約-プログラミングソルバー
  • 例えば例えばGecode（オープンソース）
• SATソルバ
  • MiniSat（オープンソース）

これらも（実際には、彼らがする必要があります。問題はNP完全であるため）、内部ヒューリスティックを使用しています。

一般的なアルゴリズム/ソフトウェアを使用しない場合は、いくつかの問題に対して特別にヒューリスティックをチューニングする必要があります。しかし、あなたが言及しているこれらの問題は少し異なり、異なる経験則が必要かもしれません。また、インスタンス内の特殊構造を分析することも重要です（ランダムインスタンスはほとんどの現実の問題とは非常に異なる動作をします）！これらの特別目的のヒューリスティックを設計する際には、の未完了のアプローチを実装して、あなたのケースでより効果的かもしれません。

あなたが直面している問題は、初期の実行可能な解決策を見つけることは、多くのメタヒューリスティクスでも非常に一般的です。

複雑なトピックです。