矩阵中连通性的ILP约束

问题描述 投票:0回答:0

我正在尝试使用 ILP 来解决以下问题: 提供了一系列连接的节点。对于下面的示例,a 仅连接到 b,b 连接到 a 和 c,c 连接到 b 和 d,d 仅连接到 c。我想将四个节点放在一个矩阵中,以在保持连接性的同时最小化所需的列。约束是矩阵的行号,在这个例子中,行号是 3.

下面有两种可能的解决方案,其中列数减少到 2:

下面是一个无效的解决方案,其中 a 无法连接到 d:

为了使用 ILP,我为每个节点分配了行值和列值。例如,a 是 (Xa,Ya)。 约束可以设置为:

Ya, Yb, Yc, Yd <= 3    Xb + Yb - Xa - Ya = 1 or -1    Xc + Yc - Xb - Yb = 1 or -1    Xd + Yd - Xc - Yc = 1 or -1

我有两个问题。

  1. 1 或 -1 约束对 ILP 求解器有效吗?
  2. 上述约束并没有避免非法连接,例如a和d之间的连接。一个潜在的解决方案是:

Xc + Yc - Xa - Ya > 1 or < -1    Xd + Yd - Xa - Ya > 1 or < -1    Xd + Yd - Xb - Yb > 1 or < -1

但是,此解决方案似乎无法扩展到输入变量大小。有没有更好的方法来对此建模? 谢谢。

dynamic-programming linear-programming
© www.soinside.com 2019 - 2024. All rights reserved.