PuLP MILP 约束：至少有一个变量必须小于 0

Question

我正在尝试向 MILP 问题添加约束，目的是确保至少有一个决策变量小于 0。有办法做到这一点吗？

Answer 1

让 x_1, x_2,...,x_n 成为您的变量。
您希望至少一个 x 变量的值小于零。您可以通过以下方式实现。

先不介绍N个二元变量y_1, y_2,...,y_n，一个对应x个变量
您为 n 个变量中的每一个添加一个约束，如下所示。

x_1 ≤ M * (1 - y_1)
x_2 ≤ M * (1 - y_2)
...
x_n ≤ M * (1 - y_n)
y_1 + y_2 + ... + y_n ≥ 1

其中 M 是一个大常数。对于最后一个约束，您强加了至少一个 y_i 变量具有值 y_i = 1，这导致对应的 x_i.

的 x_i <= 0

纸浆示例如下。

import pulp 

N = 10
M = 1000

x = pulp.LpVariable.dicts("x", range(N), cat=pulp.LpInteger, upBound=10)    
y = pulp.LpVariable.dicts("y", range(N), cat=pulp.LpBinary)    

# Note the UB on the x variables in order not to make the problem unbounded
prob = pulp.LpProblem("example", pulp.LpMaximize)

prob += pulp.lpSum(x[i] for i in range(N))

for i in range(N):
   prob += x[i] <= M * (1 - y[i])

prob += pulp.lpSum(y[i] for i in range(N)) >= 1

prob.solve()

for i in range(N):
    print(x[i], x[i].varValue)

输出：

x_0 10.0
x_1 10.0
x_2 10.0
x_3 10.0
x_4 10.0
x_5 10.0
x_6 10.0
x_7 10.0
x_8 10.0
x_9 0.0

PuLP MILP 约束：至少有一个变量必须小于 0

PuLP MILP constraint: at least one variable must be below 0

linear-programming

pulp