我正在尝试使用 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
我有两个问题。
Xc + Yc - Xa - Ya > 1 or < -1 Xd + Yd - Xa - Ya > 1 or < -1 Xd + Yd - Xb - Yb > 1 or < -1
但是,此解决方案似乎无法扩展到输入变量大小。有没有更好的方法来对此建模? 谢谢。