线性规划中如何表达“不等于”关系？Python Pulp实现遇阻

我明白你遇到的问题了——你想给整数变量加全不同约束，但之前的写法直接导致了矛盾，让求解器认为系统不可行。咱们一步步拆解问题，找到正确的解法：

你的错误原因 #

你之前写的循环会给每一对i≠j都加上x_i - x_j >=1的约束，这相当于强制要求x_i > x_j对所有i≠j都成立，这显然是不可能的！比如你有x1、x2两个变量，既要求x1>x2，又要求x2>x1，这本身就是矛盾的，求解器自然会返回不可行。

正确的“全不同”约束建模方法 #

因为变量是整数型（取值在{0,1,...,N}），x_i != x_j等价于「x_i >= x_j +1 或者 x_j >= x_i +1」。但线性/整数规划不直接支持逻辑或，所以我们需要引入二进制辅助变量来实现这个逻辑。

具体步骤如下：

1. 确保你的变量定义为整数类型（LpInteger），因为Pulp默认是连续变量，必须显式声明。
2. 对每一对不重复的变量对（比如只处理i<j，避免重复添加约束），引入一个二进制变量y_ij（取值0或1）：
   • 当y_ij=1时，强制x_i >= x_j +1
   • 当y_ij=0时，强制x_j >= x_i +1
3. 选择一个足够大的常数M，比如M = N + 1（因为变量最大取值是N，所以x_i - x_j的最大可能差值是N，最小是-N，M取N+1就能覆盖所有情况）。
4. 添加两个约束来实现逻辑或：
   • x_i - x_j >= 1 - M*(1 - y_ij)
   • x_j - x_i >= 1 - M*y_ij

完整示例代码 #

假设我们有3个变量，取值范围是0到3，目标是最小化变量之和，同时满足全不同约束：

import pulp

# 初始化问题
prob = pulp.LpProblem("All_Unique_Variables", pulp.LpMinimize)

# 定义变量：整数，取值0-3
N = 3
variables = [pulp.LpVariable(f"x_{i}", lowBound=0, upBound=N, cat=pulp.LpInteger) for i in range(3)]

# 目标函数
prob += pulp.lpSum(variables), "Total_Sum"

# 添加全不同约束
M = N + 1  # 足够大的常数
for i in range(len(variables)):
    for j in range(i + 1, len(variables)):
        x_i = variables[i]
        x_j = variables[j]
        # 引入二进制辅助变量
        y = pulp.LpVariable(f"y_{i}_{j}", cat=pulp.LpBinary)
        # 约束1：如果y=1，x_i >= x_j +1
        prob += x_i - x_j >= 1 - M * (1 - y), f"Constraint_Greater_{i}_{j}"
        # 约束2：如果y=0，x_j >= x_i +1
        prob += x_j - x_i >= 1 - M * y, f"Constraint_Lesser_{i}_{j}"

# 求解
prob.solve(pulp.PULP_CBC_CMD(msg=0))

# 输出结果
print("Status:", pulp.LpStatus[prob.status])
for var in variables:
    print(f"{var.name} = {var.varValue}")

运行这段代码，你会得到一组互不相同的整数解，比如x_0=0, x_1=1, x_2=2。

额外提示 #

如果你的变量数量恰好等于域的大小（比如k个变量，取值0到k-1），那“全不同”其实就是排列约束，这时可以用更高效的建模方式（比如指派问题的约束），但上面的方法依然通用。

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