基于ILP的固定行数矩阵节点布局连通性约束建模咨询

问题1：“等于1或-1”的约束对ILP求解器是否有效？ #

无效。ILP求解器仅支持线性等式/不等式约束，直接写Xb + Yb - Xa - Ya = 1 or -1这类离散“或”约束属于非线性逻辑，求解器无法直接解析。

要实现该逻辑，必须将其线性化，常用方法是引入0-1二进制变量：
对每条原图存在的边(u, v)，定义二进制变量z_uv ∈ {0,1}，然后添加约束：

Xv + Yv - Xu - Yu = 1 - 2*z_uv

当z_uv=0时，等式结果为1；当z_uv=1时，等式结果为-1，完美等价于原需求的“等于1或-1”，且符合ILP的线性约束要求。

问题2：避免非法连接的扩展性建模方案 #

你提出的手动添加非边约束的方式，会随着节点数量增加产生O(n²)级别的约束，扩展性极差。更优的建模思路是基于原图的边集，仅对存在的边施加相邻约束，对非边节点对通过通用线性约束禁止相邻：

核心定义 #

• 行变量：Y_i ∈ {1,2,3}（因行数固定为3，直接约束1 ≤ Y_i ≤ 3且为整数）
• 列变量：X_i ≥ 1（正整数，代表节点所在列）
• 目标函数：最小化最大列数，需线性化：引入变量C，添加约束X_i ≤ C对所有节点i，目标设为min C

1. 合法边的相邻约束 #

对原图中存在边的节点对(u, v)，强制它们在矩阵中相邻（曼哈顿距离为1），用线性约束实现：
引入两个二进制变量a_uv（同列相邻）、b_uv（同行相邻），添加：

# 二选一：要么同列相邻，要么同行相邻
a_uv + b_uv = 1

# 当a_uv=1时，同列且行差为1
X_u = X_v
Y_u - Y_v ≤ 1 + M*(1 - a_uv)
Y_v - Y_u ≤ 1 + M*(1 - a_uv)
Y_u - Y_v ≥ -1 - M*(1 - a_uv)
Y_v - Y_u ≥ -1 - M*(1 - a_uv)

# 当b_uv=1时，同行且列差为1
Y_u = Y_v
X_u - X_v ≤ 1 + M*(1 - b_uv)
X_v - X_u ≤ 1 + M*(1 - b_uv)
X_u - X_v ≥ -1 - M*(1 - b_uv)
X_v - X_u ≥ -1 - M*(1 - b_uv)

注：M为足够大的常数（如节点总数的2倍），用于激活/禁用对应约束。

2. 非边节点对的防相邻约束 #

对原图中不存在边的节点对(u, v)，禁止它们在矩阵中相邻（曼哈顿距离≥2），用大M法线性化：
引入5个二进制变量g1_uv, g2_uv, g3_uv, g4_uv, h_uv，添加：

# 至少满足以下一种情况（保证曼哈顿距离≥2）
g1_uv + g2_uv + g3_uv + g4_uv + h_uv ≥ 1

# g1_uv=1：u的列比v大至少2
X_u - X_v ≥ 2 - M*(1 - g1_uv)
# g2_uv=1：v的列比u大至少2
X_v - X_u ≥ 2 - M*(1 - g2_uv)
# g3_uv=1：u的行比v大至少2
Y_u - Y_v ≥ 2 - M*(1 - g3_uv)
# g4_uv=1：v的行比u大至少2
Y_v - Y_u ≥ 2 - M*(1 - g4_uv)
# h_uv=1：列差≥1且行差≥1（斜向相邻也禁止）
X_u - X_v ≥ 1 - M*(1 - h_uv)
X_v - X_u ≥ 1 - M*(1 - h_uv)
Y_u - Y_v ≥ 1 - M*(1 - h_uv)
Y_v - Y_u ≥ 1 - M*(1 - h_uv)

该方案可通过程序自动生成所有非边约束，无需手动编写，扩展性极强。

内容的提问来源于stack exchange，提问作者Amanli