矩阵中连通性的ILP约束

Question

我正在尝试使用 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

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