Pulp构建0-1整数规划时列和约束设置问题求助

问题背景 #

构建元素仅为0或1的矩阵模型（列代表预约），需求如下：

• 统计列和大于0的列数，要求恰好为2
• 目标是最小化矩阵中所有变量的总和
• 使用Pulp创建以ROWS、COLS为键的0-1变量字典

初始代码（不可行） #

import pulp as Pulp
ROWS = range(1, 6)
COLS = range(1,5)

prob = Pulp.LpProblem("Fewestcolumns", Pulp.LpMinimize)
choices = Pulp.LpVariable.dicts("Choice", (ROWS, COLS), cat="Integer", lowBound=0, upBound=1)
prob += Pulp.lpSum([choices[row][col] for row in ROWS for col in COLS])
prob += Pulp.lpSum([1 if Pulp.lpSum([choices[row][col] for row in ROWS]) >= 1 else 0 for col in COLS]) == 2

prob.solve()

print("Status:", Pulp.LpStatus[prob.status])
for v in prob.variables():
    print(v.name, "=", v.varValue)

初始运行结果 #

C:\Users\xxxComputing\LinearProgramming\Scripts\python.exe C:/Users/xxx/Computing/LinearProgramming/LinearProgTest.py
Welcome to the CBC MILP Solver 
Version: 2.10.3 
Build Date: Dec 15 2019 

command line - C:\Users\xxxx\Computing\LinearProgramming\lib\site-packages\pulp\solverdir\cbc\win\64\cbc.exe C:\Users\simon\AppData\Local\Temp\4f8ff67726844bde8abe98316b6338c4-pulp.mps timeMode elapsed branch printingOptions all solution C:\Users\simon\AppData\Local\Temp\4f8ff67726844bde8abe98316b6338c4-pulp.sol (default strategy 1)
At line 2 NAME          MODEL
At line 3 ROWS
At line 6 COLUMNS
At line 67 RHS
At line 69 BOUNDS
At line 90 ENDATA
Problem MODEL has 1 rows, 20 columns and 0 elements
Coin0008I MODEL read with 0 errors
Option for timeMode changed from cpu to elapsed
Problem is infeasible - 0.00 seconds
Option for printingOptions changed from normal to all
Total time (CPU seconds):       0.01   (Wallclock seconds):       0.01

Status: Infeasible
Choice_1_1 = 0.0
Choice_1_2 = 0.0
Choice_1_3 = 0.0
Choice_1_4 = 0.0
Choice_2_1 = 0.0
Choice_2_2 = 0.0
Choice_2_3 = 0.0
Choice_2_4 = 0.0
Choice_3_1 = 0.0
Choice_3_2 = 0.0
Choice_3_3 = 0.0
Choice_3_4 = 0.0
Choice_4_1 = 0.0
Choice_4_2 = 0.0
Choice_4_3 = 0.0
Choice_4_4 = 0.0
Choice_5_1 = 0.0
Choice_5_2 = 0.0
Choice_5_3 = 0.0
Choice_5_4 = 0.0

Process finished with exit code 0

预期可行解示例 #

Status: Optimal
Choice_1_1 = 1.0
Choice_1_2 = 1.0
Choice_1_3 = 0.0
Choice_1_4 = 0.0
Choice_2_1 = 0.0
Choice_2_2 = 0.0
Choice_2_3 = 0.0
Choice_2_4 = 0.0
Choice_3_1 = 0.0
Choice_3_2 = 0.0
Choice_3_3 = 0.0
Choice_3_4 = 0.0
Choice_4_1 = 0.0
Choice_4_2 = 0.0
Choice_4_3 = 0.0
Choice_4_4 = 0.0
Choice_5_1 = 0.0
Choice_5_2 = 0.0
Choice_5_3 = 0.0
Choice_5_4 = 0.0

修改后代码及问题 #

尝试大M约束后的代码：

import pulp as Pulp
ROWS = range(1, 6)
COLS = range(1,5)

prob = Pulp.LpProblem("Fewestcolumns", Pulp.LpMaximize)
choices = Pulp.LpVariable.dicts("Choice", (ROWS, COLS), cat="Integer", lowBound=0, upBound=1)
used = Pulp.LpVariable.dicts("used", COLS, cat="Binary")
b = Pulp.LpVariable.dicts("b", COLS, cat="Binary")

prob += Pulp.lpSum([choices[row][col] for row in ROWS for col in COLS])
for rows, items in choices.items():
    prob += Pulp.lpSum(cols for cols in items.values()) == 1

M = 20
for col in COLS:
    prob += b[col] >= (Pulp.lpSum([choices[row][col] for row in ROWS]) - 1) / M
    prob += used[col] >= M * (b[col] - 1)

prob += Pulp.lpSum([used[col] for col in COLS]) == 2
prob.solve()

print("Status:", Pulp.LpStatus[prob.status])
for v in prob.variables():
    print(v.name, "=", v.varValue)

修改后运行结果 #

Result - Optimal solution found

Objective value:                5.00000000
Enumerated nodes:               0
Total iterations:               0
Time (CPU seconds):             0.00
Time (Wallclock seconds):       0.00

Option for printingOptions changed from normal to all
Total time (CPU seconds):       0.01   (Wallclock seconds):       0.02

Status: Optimal
Choice_1_1 = 0.0
Choice_1_2 = 0.0
Choice_1_3 = 0.0
Choice_1_4 = 1.0
Choice_2_1 = 0.0
Choice_2_2 = 0.0
Choice_2_3 = 0.0
Choice_2_4 = 1.0
Choice_3_1 = 0.0
Choice_3_2 = 0.0
Choice_3_3 = 0.0
Choice_3_4 = 1.0
Choice_4_1 = 0.0
Choice_4_2 = 0.0
Choice_4_3 = 0.0
Choice_4_4 = 1.0
Choice_5_1 = 0.0
Choice_5_2 = 0.0
Choice_5_3 = 0.0
Choice_5_4 = 1.0
b_1 = 1.0
b_2 = 1.0
b_3 = 1.0
b_4 = 1.0
used_1 = 1.0
used_2 = 1.0
used_3 = 0.0
used_4 = 0.0

Process finished with exit code 0

问题原因分析 #

1. 初始代码错误：
   约束中使用了1 if ... else 0的条件判断，这不是线性规划能识别的线性表达式，Pulp无法将其转化为有效的约束，导致模型不可行。

2. 修改后代码的核心问题：

   • 目标函数错误改为LpMaximize，原本需求是最小化变量总和，求解器会尽可能多选1，导致所有行集中选同一列。
   • 新增了每行必须恰好选一个列的约束，这和预期解（仅第一行选两个列，其他行全0）完全冲突，直接改变了问题的约束条件。
   • 大M约束逻辑混乱，b[col]和used[col]的关联约束完全错误，无法正确反映"列和>0则used=1"的逻辑。

修正后的代码 #

import pulp as Pulp
ROWS = range(1, 6)
COLS = range(1,5)

prob = Pulp.LpProblem("Fewestcolumns", Pulp.LpMinimize)
# 0-1变量矩阵
choices = Pulp.LpVariable.dicts("Choice", (ROWS, COLS), cat="Binary")
# 标记列是否被使用（列和>0则为1）
used = Pulp.LpVariable.dicts("Used", COLS, cat="Binary")

# 目标：最小化所有变量总和
prob += Pulp.lpSum([choices[row][col] for row in ROWS for col in COLS])

# 关联列和与used变量的约束
M = len(ROWS)  # 取行数作为大M，因为列和最大为行数
for col in COLS:
    col_sum = Pulp.lpSum([choices[row][col] for row in ROWS])
    # 如果used[col] = 0，列和必须为0；如果used[col] =1，列和可以是1~M
    prob += col_sum <= M * used[col]
    # 如果used[col] =1，列和至少为1；如果used[col]=0，列和<=0（即0）
    prob += col_sum >= used[col]

# 约束：恰好使用2列
prob += Pulp.lpSum(used[col] for col in COLS) == 2

prob.solve()

print("Status:", Pulp.LpStatus[prob.status])
for v in prob.variables():
    if v.name.startswith("Choice"):
        print(v.name, "=", v.varValue)
# 打印used变量验证
print("\nUsed columns:")
for col in COLS:
    print(f"Used_{col} = {used[col].varValue}")

修正后说明 #

• 恢复LpMinimize目标，符合初始需求
• 移除了错误的"每行必选一列"约束
• 用正确的大M约束关联used变量和列和：
  • col_sum <= M*used[col]：确保未使用的列（used=0）列和为0
  • col_sum >= used[col]：确保使用的列（used=1）列和至少为1
• 约束恰好2个列被使用，最终会得到类似预期的解（变量总和最小，仅用2列，且尽可能少的选1）

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