tree - 整数线性规划的条件约束

Question

我正在解决关于 Trees 的问题。我正在尝试编写 ILP 公式。我有一棵树 T=(V,E) V 是顶点 E 是边。我的限制之一是关于连通性，我想制定我的陈述：如果 X[i,j] =1; 然后 X[parent_i,i] = 1。X 是二进制变量，表示我们在解决方案中选择该节点，如果它在解决方案 1 中，否则为 0。i，j 是 V 的元素我如何制定这个？

提前致谢。

Answer 1

对于 {0, 1} 中的 A、B，[A = 1 ⇒ B = 1] ⇔ [A ≤ B]。

Answer 2

我提供了一个解决方案，我使用了与节点的父关系。解决方案是：X(parent[parent[i]],parent[i])-X(Parent[i],i)>=0。假设我们有 k-->i-->j 层次结构，有 3 种可能性：首先 k,i 和 i,j 都可能为 0，其次都可能为 1；最后 k,i 可能为 1 并且 i,j 可能为 0。但是当 i,j 为 1 时 k,i 不能为 0。所以 (k,i) - (i,j) 必须大于等于0。