相互依存変数による組み合わせ最適化

Question

これは、これらのフォーラムでの最初の投稿です。すべての回答があらかじめありがとうございます。

私は「組み合わせ最適化問題」と呼ばれると思われるものに遭遇したJavaアプリケーションを開発しています。私は基本的な数学スキルしか持っていないので、そのような問題の設定を調べようとすることはこれまで実りありませんでした。

基本的には、変数v1、v2、v3などを使って、より大きな集合Nの最適サブセットnを見つける最も効率的な方法をプログラムすることです。変数にはすべて、さらに明確な値/スコアがありますサブセットに含まれていてもいなくてもよい他の特定の変数に依存する値/スコアに変換する。

私は最大合計値/スコアを与えるサブセットの選択に興味があります。

したがって、例えば、フルセットのNは、次の変数で構成され、以下の確定値ならびに関係他の変数に有する：一個の以上の他の選択された変数に関係を持つ

v1 8 { v2 ; v8 } 
v2 6 { v1 ; v4 } 
v3 9 { } 
v4 7 { v2 ; v5 ; v8 } 
v5 6 { v4 ; v10 } 
v6 8 { v7 } 
v7 5 { v6 } 
v8 9 { v1 ; v4 } 
v9 6 { } 
v10 7 { v5 } 

を合計値がある種の「離陸」を持つことを意味します。この例のために、各関係ごとに1つを挙げましょう。サブセットは30の合計値を与えるよう は、したがって、最初の5つの変数を選択：

v1 8 { v2 ; v8 }  = 8 - 1 = 7 
v2 6 { v1 ; v4 }  = 6 - 2 = 4 
v3 9 { }    = 9 - 0 = 9 
v4 7 { v2 ; v5 ; v8 } = 7 - 2 = 5 
v5 6 { v4 ; v10 }  = 6 - 1 = 5 

これは当然のことながら、このような小さなセットのための問題ではありませんが、私は現在、100Kと10Kのサブセットのセットに直面しています - 現在のアルゴリズムでは、私のコンピュータは3日で解決策を計算しました！

私は必ずしもこれを解決するためのコードを必要としませんが、それを行うための最適な数学的方法（もしあれば！）は必要です。しかし、私は基本レベルより上の数学的表記法を理解するのが苦労しています。

もう一度、すべての回答に感謝します！

Answer 1

残念ながら、この問題は最適解を見つけるのにNP困難です。

この問題を効率的に解決できれば、NP-hard maximum independent set problemを各頂点の値を1に設定し、各エッジに対して非常に大きなペナルティを設定することで解決できます。

代わりに、おおよその解決策を探す必要があります。シミュレートされたアニーリングアルゴリズムや遺伝的アルゴリズムを使って合理的な答えを得ることができます。線形計画ソルバに

Answer 2

あなたのセットはグラフとして見ることができます。各vXはそれぞれの値を持つノード/頂点です。例v1は値8のノード/頂点であり、値v2のノード/頂点は値6などです。そして、それらの間に辺があります。例v1には2つのエッジがあります.1つはv2、もう1つはv8です。各辺には値を指定することもできます（-1の場合）。

グラフを使用し、v1からv5を選択すると、8 + 6 + 9 + 7 + 6（頂点値）-1 -1 -1 -1 -1（エッジ値）になります。

http://jgrapht.org/あなたに役立つかどうか試してみてください。

Graph Teory：http://www.people.vcu.edu/~gasmerom/MAT131/graphs.htmlも参照してください。最長/最短パスアルゴリズムを観察する（例：http://www.maxburstein.com/blog/introduction-to-graph-theory-finding-shortest-path/）

Answer 3

、

v1 8 { v2 ; v8 } 
v2 6 { v1 ; v4 } 
v3 9 { } 
v4 7 { v2 ; v5 ; v8 } 
v5 6 { v4 ; v10 } 
v6 8 { v7 } 
v7 5 { v6 } 
v8 9 { v1 ; v4 } 
v9 6 { } 
v10 7 { v5 } 

のような入力を取り、

maximize 8*v1 - v1v2 - v1v8 
     + 6*v2 - v2v1 - v2v4 
     + 9*v3 
     + 7*v4 - v4v2 - v4v5 - v4v8 
     + 6*v5 - v5v4 - v5v10 
     + 8*v6 - v6v7 
     + 5*v7 - v7v6 
     + 9*v8 - v8v1 - v8v4 
     + 6*v9 
     + 7*v10 - v10v5 

subject to 
v1 + v2 - v1v2 <= 1 
v1 + v8 - v1v8 <= 1 
v2 + v1 - v2v1 <= 1 
v2 + v4 - v2v4 <= 1 
v4 + v2 - v4v2 <= 1 
v4 + v5 - v4v5 <= 1 
v4 + v8 - v4v8 <= 1 
v5 + v4 - v5v4 <= 1 
v5 + v10 - v5v10 <= 1 
v6 + v7 - v6v7 <= 1 
v7 + v6 - v7v6 <= 1 
v8 + v1 - v8v1 <= 1 
v8 + v4 - v8v4 <= 1 
v10 + v5 - v10v5 <= 1 

binary v1, v1v2, v1v8, 
     v2, v2v1, v2v4, 
     v3, 
     v4, v4v2, v4v5, v4v8, 
     v5, v5v4, v5v10, 
     v6, v6v7, 
     v7, v7v6, 
     v8, v8v1, v8v4, 
     v9, 
     v10, v10v5 

あなたのインスタンスのサイズが最適解のためにあまりにも多くの可能性が高いですが、1のような整数プログラムに変換決して知らない...