捕捉布尔变量列表中第一次出现“1”的情况 - 线性规划

Question

我是线性规划的新手。比如说，我有一个布尔变量列表

x[i]

、

i

，范围从 0 到 5。现在，我想确定 5 个布尔变量中的任何一个变为 1 的第一次出现。例如，发布解决，

x

解析为[0, 1, 0, 1, 0]，那么我想要另一个布尔变量

y[i]

，它将报告：[0, 1, 0, 0, 0]。

我尝试了一些方法，但遇到了问题，因为在解决问题之前我无法访问

x

的值。

Answer 1

您可以使用以下约束来维持

x

和

y

变量之间的所需关系：

sum(i, y[i]) <= 1 ; for 0 <= i <= 4
y_i <= x_i ; for 0 <= i <= 4
sum(i, y[i]) >= x_j ; for 0 <= j <= 4, i will range from 0 till j

抱歉，在 stackoverflow 中使用乳胶符号不太舒服

下面是 Google-OR-tool 线性求解器中的实现。

from ortools.linear_solver import pywraplp

s = pywraplp.Solver("", pywraplp.Solver.SCIP_MIXED_INTEGER_PROGRAMMING)

x = {i: s.BoolVar("") for i in range(5)}
y = {i: s.BoolVar("") for i in range(5)}

# forcing second and fourth variable to be 1
s.Add(x[1] + x[3] == 2)
# all remaining are forced to be zero
s.Add(sum(x[i] for i in range(5)) == 2)

# below are the 3 constraints that were listed above:
# 1.
s.Add(sum(y[i] for i in range(5)) <= 1)

# 2.
for i in range(5):
    s.Add(y[i] <= x[i])

# 3.
for j in range(5):
    s.Add(sum(y[i] for i in range(j + 1)) >= x[j])

s.Solve()
{i: x[i].SolutionValue() for i in range(5)}
#{0: 0.0, 1: 1.0, 2: 0.0, 3: 1.0, 4: 0.0}

{i: y[i].SolutionValue() for i in range(5)}
#{0: 0.0, 1: 1.0, 2: 0.0, 3: -0.0, 4: 0.0}