Python中的二进制和整数程序

Question

我有一个二进制/整数程序，想用Python中的milp来解决。下面是我目前的代码和一张图片。当我运行它时，出现了以下问题：

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

我以为在“bounds”这个变量里已经考虑了上下限，但显然没有。那么我缺少了什么呢？

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))

Answer 1

你的代码有两个问题。首先，如果想要禁用边界或者定义“无限边界”，应该使用 np.inf 或者 -np.inf，而不是 None。

其次，你现在给 scipy.optimize.Bounds 提供的是一个元组的列表，这样是不行的。你应该分别提供一个下边界的列表和一个上边界的列表。

为了解决这些问题，你可以把代码的最后部分改成：

# 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, np.inf)] * 36  # Bounds for the y variables (unbounded upper limit)

# Combine bounds
bounds = x_bounds + y_bounds

integrality = ([1]) * 45

l_bounds = [x for (x,y) in bounds]
u_bounds = [y for (x,y) in bounds]

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

除了用列表推导式，你也可以使用 zip 函数，这样会更简洁：

l_bounds, u_bounds = zip(*bounds)

或者直接这样写：

bounds = Bounds(*zip(*bounds))

我个人更喜欢使用列表推导式的解决方案，因为这样能让读者更清楚地理解发生了什么，而且对于这种长度的列表来说，性能其实不是问题。