0

问题：

我有一个图，其中每个顶点的布尔状态受给定连接顶点状态的逻辑关系的约束。边缘描述了反应，其中每个反应都有一组激活剂（促进它）、阻遏剂（抑制反应）和产物（可以在反应发生时打开）。对于某些顶点，有一个已知的布尔赋值，它们应该处于哪个状态。我的目标是找到图中所有布尔值的赋值，在遵守图的逻辑约束的同时最大化与已知赋值的一致性。

编辑：这是 ILP 目标和我建议使用的约束：http://i.imgur.com/kSUoVdt.jpg

基本上，我的目标是找到图中所有物种的状态分配，该分配与从数据中已知的状态（M）的“真实”分配最接近。并非图中的所有物种都具有已知状态。

第一个约束规定只有当所有激活物质和抑制物质都不为真时才会发生反应。

第二个约束表示，如果产生物种的反应之一为真，或者如果它被指定为输入节点，则物种可以为真。

从我目前所读到的内容来看，这个问题是 B&B 方法的一个很好的候选者。但是，我无法估计 B&B 和蛮力搜索的时间复杂度。我的猜测是蛮力搜索将是 2^n，其中 n=顶点数，因为这是在最坏情况下由 B&B 树生成的节点总数。但似乎必须评估的约束数量也应该考虑到 B&B 和蛮力的复杂性，但我不确定如何。

4

1 回答 1

0

如果我要将这个问题提供给 ILP 求解器，那么这是我首先要尝试的公式。（强调第一个，因为这个活动通常涉及大量的试错。）

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 求和是罪魁祸首）。另一种可能性是使用约束求解器；我对这些的经验要少得多。

组合优化的研究人员倾向于支持实验评估而不是理论渐近时间界限，因为后者很难获得并且通常过于悲观。在最坏的情况下，分支定界不会获得任何有用的界限，并且成本将是蛮力乘以评估每个节点的成本（可能是多项式）。

于 2014-05-10T06:51:05.087 回答