4

私は1つの問題で髪を引っ張ってきました...全体的な問題は複雑です...しかし、本当に重要な部分を説明するために最善を尽くします...

各エッジが接続された2つのノード間の相関を表すグラフがあります。各ノードはタイムコース（TC）（つまり、400の時点）であり、イベントはさまざまな時点で発生します。2つのノード間の相関は、重複するイベントのパーセンテージとして定義されます。この例を簡単にするために、各ノードで発生するイベントの総数が$tn$と同じであると仮定します。また、2つのTC（ノード）に$ on $のオーバーラップイベント（つまり、まったく同じ時点で発生したイベント）がある場合。次に、相関は単純に$ on $ / $tn$として定義できます。

今、私は11ノードのネットワークを持っています。そして私は2つのノードごとの相関関係を知っています。相関制約を満たす11ノードすべてのTCを生成するにはどうすればよいですか？

2つのノード間の相関関係がわかっている場合、2つのノードに対してこれを行うのは簡単です。TC_1とTC_2の相関値が0.6であると想定します。これは、2つのTCで60％の重複イベントがあることを意味します。また、イベントの総数は、TC_1とTC_2の両方で$tn$と同じであると想定します。2つのTCにイベントを配置する簡単なアルゴリズムは、最初に0.6 * $ tn $の時点をランダムに選択し、それらを両方のTCで重複したイベントが発生したタイムスロットと見なします。次に、TC_1で（1-0.6）* $ tn $の時点をランダムに選択して、TC_1の残りのイベントを配置します。最後に、TC_2の対応する時点でイベントが発生しなかったTC_2の（1-0.6）* $tn$時点をランダムに選択します。

ただし、生成された3つのTCが3つの相関制約すべて（つまり、3つのエッジ）を満たす必要がある3ノードネットワークを考えると、難しくなり始めます...11ノードネットワークではこれを行うことはほとんど不可能です。 ..。。

これはあなたにとって意味がありますか？そうでない場合はお知らせください...

これは単なる計算機科学のプログラミングの問題だと思っていましたが、考えれば考えるほど線形計画問題のようですね。

誰かが合理的な解決策を持っていますか？私はこれをRで行っていますが、どのコードでも問題ありません...

4

3 に答える 3

1

単純な線形計画法のアプローチがあると思います。ソリューションをマトリックスとして表します。各列はノードであり、各行はイベントです。セルは0または1のいずれかであり、イベントが特定のノードに関連付けられているかどうかを示します。相関制約は、実際には事前に修正した、各列の1の数に対して、1組の列の11の数を固定する制約です。

このフレームワークでは、X_i回発生する可能性のある各行を特定のアイテムとして扱う場合、SUM_i X_i * P_ij = K_jの形式の制約があります。ここで、P_ijは0または1であり、可能な行iに11があるかどうかによって異なります。 jによってカウントされる列のペア。もちろん、これは多数のノードにとってはちょっとした惨事ですが、11のノードでは、2048の行が可能であり、完全に管理できないわけではありません。X_iは線形ではないかもしれませんが、合理的である必要があると思います。したがって、驚異的な数の行/イベントを使用する準備ができている場合は、問題ありません。

残念ながら、不等式が潜んでいるため、異なる合計列数を試す必要がある場合もあります。N行があり、2つの列にmとn 1が含まれている場合、その列のペアには少なくともm + n--N11が必要です。実際、各列の共通の1の数を解の変数として出力することもできます。これにより、Q_ijが0で、列の行iの列が1であるかどうかに応じて1となる新しい制約のセットが得られます。 j。

そこに潜んでいるより良い答えがあるかもしれません。特に、特定の相関に対して正規分布の確率変数を生成するのは簡単です（可能な場合）-http://en.wikipedia.org/wiki/Cholesky_decomposition#Monte_Carlo_simulationおよび（Google R mvrnormによる）。+/-1のエントリで満たされた2^N行と2^N-1列の行列を考えてみます。Nビットのすべての組み合わせで行にラベルを付け、Nビットのすべての非ゼロ列で列にラベルを付けます。各セルに-1^（行ラベルと列ラベルのパリティ）を入力します。各列には、+1と-1のエントリが同数あります。2つの列を要素ごとに複数持つと、+1と-1のエントリの数が等しい別の列が得られるため、相互に無相関になります。コレスキー分解で要素が[-1、1]の範囲にある行列が提供される場合は、それを使用して列を結合できます。列から、または否定された列からランダムに選択して、列を結合します。特定の確率。

これはまた、すべての可能性がある2 ^ 15の異なる行からではなく、同じパターンを持つ16の異なる行から選択することにより、たとえば15列の元の線形計画法アプローチでうまくいく可能性があることを示唆しています。上記のように2^4行と2^4-1列のマトリックス。

于 2011-07-16T05:54:28.377 に答える
0

これを混合整数プログラムとして表すことができます。

ノードがNあり、各ノードにT合計タイムスロットがあるとします。これらのタイムスロットへのイベントの割り当てを見つけたいとします。各ノードにはtn <= Tイベントがあります。Mグラフには 合計エッジがあります。iエッジを共有するノードのペア間jには、係数があります

c_ij = overlap_ij/tn

ここoverlap_ijで、重複するイベントの数です。

x[i,t]として定義されたバイナリ変数としましょう

 x[i,t] = { 1 if an event occurs at time t in node i
        = { 0 otherwise.

tn次に、ノードでイベントが発生するという制約は、次のiように記述できます。

sum_{t=1}^T  x[i,t] == tn

e[i,j,t]として定義されたバイナリ変数としましょう

 e[i,j,t] = { 1 if node i and node j share an event a time t
          = { 0 otherwise

ノードN(i)の隣接ノードを としますi。それから私たちは毎回それを持っていますt

  sum_{j in N(i)}  e[i,j,t] <= x[i,t]

これは、共有イベントがノードの隣人iで timeに発生した場合、ノードは timetに iイベントを持っている必要があることを示していtます。さらに、ノードiに 2 つのネイバーuとがある場合、すべてのネイバーの合計が より小さいため、v持つことはできません(2 つのイベントが同じタイム スロットを共有することを意味します) 。e[i,u,t] + e[i,v,t] > 1x[i,t] <= 1

また、 nodeと nodeoverlap_ij = tn*c_ijの間に重複するイベントが存在する必要があることもわかっています。これは、私たちが持っていることを意味しますij

  sum_{t=1}^T e[i,j,t] == overlap_ij

これをすべてまとめると、次の MIP が得られます

  minimize  0 
    e, x
  subject to     sum_{t=1}^T x[i,t] == tn, for all nodes i=1,...,N
                 sum_{j in N(i)} e[i,j,t] <= x[i,t],
                       for all nodes i=1,...,N and all time t=1,...,T
                 sum_{t=1}^T e[i,j,t] == overlap_ij for all edges (i,j) 
                                                      between nodes
                 x[i,t] binary for i=1,...,N and t=1,...,T
                 e[i,j,t] binary for all edges (i,j) and t=1,...,T

モデルは純粋な実現可能性の問題であるため、ここでは目的はゼロです。T*N + M*Tこのモデルには、変数とN + N*T + M制約の合計があります。

Gurobiのような MIP ソルバーは、上記の問題を解決したり、それが実行不可能であること (つまり、解が存在しないこと) を証明したりできます。Gurobi には R へのインターフェースがあります。

iソリューション ベクトル を見ることで、ノード thのイベントの最終的な時系列を抽出できますx[i,1], x[i,2], ..., x[i,T]。

于 2014-04-12T08:16:54.930 に答える
0

解が存在する場合 (解がない場合に問題が発生する可能性があります)、これを線形方程式系として表すことができます。

 x1/x2 = b => 
 x1 - b*x2 = 0
 or just
 a*x1 + b*x2 = 0

Ax=b の b は 0 であるため、これを一次方程式系またはより正確には同次一次方程式系に変換できるはずです。

問題は、n 個のノードと n*(n-1)/2 の関係 (方程式) があるため、多くの関係が必要であり、解決策がないことです。

この問題を次のように表すことができます。

x > 0 および xx == 一定の Ax を最小化します。

于 2011-07-16T06:19:48.723 に答える