Python中使用milp求解二进制/整数规划的Bounds参数报错问题

问题重现 #

运行整数规划求解代码时触发如下错误：

bounds.lb and bounds.ub must contain reals and be broadcastable to c.shape.

原代码如下：

from scipy.optimize import linprog
import numpy as np
from scipy.optimize import milp, LinearConstraint, Bounds 
c = [3, 5, 7, 9, 2, 8, 6, 4, 1]  # x1 to x9 (office setup cost multipliers)
c = c + [0]*36     

A = [
    [1700, 3600, 2100, 2500, 3100, 2700, 4100, 3400, 4100] + [24.3]*9 + [32.4]*9 + [28.9]*9+[26]*9,  # Setup and transfer costs
    [0, 0, 0, -1, 0, -1, 1, 0, 0] + [0]*36,  # x7 <= x4 + x6
    [1, 0, 0, 0, 0, 1, 0, 0, 0] + [0]*36,  # x1 + x6 <= 1
    [0]*9 + [1]*9 + [0]*27,  # Chicago
    [0]*18 + [1]*9 + [0]*18,  # Charlotte
    [0]*27 + [1]*9 + [0]*9,  # Pittsburgh
    [0]*36 + [1]*9   # Houston
]

b = [
    14000,  
    0,  
    1,  
    29, 
    22, 
    19,  
    27,  
]

# Define bounds for each variable (0 <= xi <= 1 for binary variables, 0 <= yij)
x_bounds = [(0, 1)] * 9  # Bounds for the x variables
y_bounds = [(0, None)] * 36  # Bounds for the y variables (unbounded upper limit)

# Combine bounds
bounds = x_bounds + y_bounds

integrality = ([1]) * 45

milp(c, integrality = integrality,
    bounds = Bounds(bounds),
     constraints = LinearConstraint(A, b))

错误原因 #

1. Bounds类参数使用错误：scipy.optimize.Bounds的构造函数需要分别传入下界数组（lb）和上界数组（ub），而非直接传入形如[(lb1, ub1), ...]的列表。原代码直接将组合后的列表传给Bounds，导致无法正确解析上下界维度。
2. 非实数类型的上界：y_bounds中使用None表示无界上界，但Bounds要求上下界必须是实数类型，None不符合要求，需替换为np.inf。

修正后的代码 #

from scipy.optimize import linprog
import numpy as np
from scipy.optimize import milp, LinearConstraint, Bounds 

c = [3, 5, 7, 9, 2, 8, 6, 4, 1] + [0]*36  # 合并目标系数

# 约束矩阵与右侧值
A = [
    [1700, 3600, 2100, 2500, 3100, 2700, 4100, 3400, 4100] + [24.3]*9 + [32.4]*9 + [28.9]*9+[26]*9,
    [0, 0, 0, -1, 0, -1, 1, 0, 0] + [0]*36,
    [1, 0, 0, 0, 0, 1, 0, 0, 0] + [0]*36,
    [0]*9 + [1]*9 + [0]*27,
    [0]*18 + [1]*9 + [0]*18,
    [0]*27 + [1]*9 + [0]*9,
    [0]*36 + [1]*9
]
b = [14000, 0, 1, 29, 22, 19, 27]

# 拆分上下界为单独数组，替换None为np.inf
lb = [0]*9 + [0]*36  # 所有变量下界为0
ub = [1]*9 + [np.inf]*36  # x变量上界1，y变量无界

# 正确初始化Bounds
bounds = Bounds(lb, ub)

# 整数约束：所有变量为整数（前9个是二进制，后36个是整数）
integrality = np.ones(45, dtype=int)

# 调用milp求解
result = milp(c, integrality=integrality, bounds=bounds, constraints=LinearConstraint(A, b))
print(result)

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