添加规模惩罚项后线性规划求解器违反D变量0-1整数约束问题

为什么会出现非0-1的D变量？ #

1. 绝对值约束的错误处理：整数线性规划不支持直接使用绝对值表达式|Sum(D[i][j])-3| ≤ SP1[j]。如果直接将这个约束加入模型，Pulp对其的线性转换逻辑不严谨，会导致求解器放松对D变量的整数性要求，最终返回松弛的非整数解。
2. 变量类型定义不严格：若D[i][j]被定义为LpInteger而非LpBinary，求解器可能允许它取0和1之外的整数值；另外如果SP1[j]未设置为非负整数，约束逻辑会失效，进一步干扰求解结果。
3. 求解器模式问题：部分求解器在处理混合整数规划（MIP）时，若未触发整数求解模式，会默认返回线性规划的松弛解（允许非整数）。

解决步骤 #

1. 正确线性化绝对值约束 #

把绝对值约束拆成两个等价的线性约束，这是线性规划处理绝对值的标准方法：
对每个项目j，替换原绝对值约束为：

• 当项目人数超过3时：sum(D[i][j] for i in people) - 3 ≤ SP1[j]
• 当项目人数不足3时：3 - sum(D[i][j] for i in people) ≤ SP1[j]
  这样能让求解器正确理解约束逻辑，避免出现松弛。

2. 严格定义变量类型 #

• 决策变量D必须是二进制变量（0或1），代码里明确指定：

  D = LpVariable.dicts("Assignment", (people_list, project_list), cat='Binary')
  

• 惩罚变量SP1[j]设为非负整数：

  SP1 = LpVariable.dicts("Size_Penalty", project_list, lowBound=0, cat='Integer')
  

3. 修复原有约束的写法 #

线性规划不支持!=约束，你原来的“项目人数不能为1”需要拆成两个约束：
对每个项目j：

# 项目人数要么为0，要么≥2
prob += lpSum(D[i][j] for i in people_list) <= 0, f"MinPeople_Project_{j}"
prob += lpSum(D[i][j] for i in people_list) >= 2, f"MaxPeople_Project_{j}"

4. 确认求解器与目标函数 #

• 确保使用支持MIP的求解器（比如Pulp默认的CBC，或者Gurobi），模型中存在整数变量时，求解器会自动切换到整数求解模式。
• 目标函数明确为最大化总偏好得分减去惩罚总和：

  total_preference = lpSum([preferences[i][j] * D[i][j] for i in people_list for j in project_list])
  total_penalty = lpSum(SP1[j] for j in project_list)
  prob += total_preference - total_penalty, "Total_Objective"
  prob.sense = LpMaximize
  

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