0

問題：

各頂点のブール状態が、接続された頂点の状態が与えられた論理関係によって制約されるグラフがあります。エッジは反応を表し、各反応には一連のアクティベーター (それを促進する)、リプレッサー (反応を阻害する)、および生成物 (反応が発生したときにオンにすることができます) があります。いくつかの頂点については、それらがどの状態にあるべきかの既知のブール割り当てがあります。私の目標は、グラフの論理的制約に従いながら、既知の割り当てとの一致を最大化するグラフ内のすべてのブール値の割り当てを見つけることです。

編集: ILP の目的と、使用することを提案している制約は次のとおりです。http://i.imgur.com/kSUoVdt.jpg

基本的に、私の目的は、データから知られている「真の」状態の割り当て (M) と最もよく一致する、グラフ内のすべての種への状態の割り当てを見つけることです。グラフ内のすべての種に既知の状態があるわけではありません。

最初の制約は、すべての活性化種が TRUE で、阻害種がどれも TRUE でない場合にのみ反応が発生することを指定します。

2 番目の制約は、種を生成する反応の 1 つが TRUE である場合、または入力ノードとして指定されている場合に、種が TRUE になる可能性があることを示しています。

これまで読んだことから、この問題は B&B アプローチの良い候補です。しかし、B&B とブルート フォース検索の時間の複雑さを見積もるのに苦労しています。私の推測では、ブルート フォース検索は 2^n (n = 頂点の数) になると思います。これは、最悪の場合に B&B ツリーによって生成されるノードの総数だからです。しかし、評価する必要がある制約の数も、B&B とブルート フォースの複雑さを考慮に入れる必要があるようですが、その方法はわかりません。

4

1 に答える 1

0

この問題を ILP ソルバーに入力する場合、これが最初に試す定式化です。(通常、このアクティビティにはかなりの量の試行錯誤が含まれるため、firstを強調します。)

min   sum_{species i measured true} x_i
    - sum_{species i measured false} x_i
subject to
  for each species i inhibiting reaction j:
    x_i + y_j <= 1
  for each species i activating reaction j:
    x_i - y_j >= 0
  for each non-input species i:
    x_i - sum_{reaction j producing species i} y_j <= 0
(binary)
  for each species i:
    x_i in {0, 1}
  for each reaction j:
    y_j in {0, 1}

制約 (1) を分割します。これは、変数に対するバイナリ制約で必要なことが行われるとは思わないためです。リラクゼーションの質がどのようなものになるかについて、私は多くの直感を持っていません (それが悪い場合は、y_js の合計が原因であると思います)。もう 1 つの可能性は、制約ソルバーを使用することです。私はそれらの経験がはるかに少ないです。

組み合わせ最適化の研究者は、理論的な漸近的な時間範囲よりも実験的な評価を好む傾向があります。最悪の場合、分岐と境界は有用な境界を取得せず、コストは各ノードを評価するコスト (おそらく多項式) のブルート フォース倍になります。

于 2014-05-10T06:51:05.087 に答える