LP 求解器；为大量链接依赖变量设置模型约束很慢

Question

创建模型太慢。解决它不是这里的问题。

我之前看过一些类似的问题，但从我给出的尺寸来看，他们没有问题。

添加到模型非常慢的约束看起来像这样：

x out of {0, 1} (binary)
y_0 = 0
y_i = y_(i-1) + x_i; N > i > 0

换句话说，变量向量

x=[1, 0, 1, 1]

会给我

y_1 = 1
y_2 = 1
y_3 = 2

它实际上更复杂，但我在这里将其简化为这个最小的可重现示例。意思是：我不希望所有 i 的 y 值超过某个阈值。

我用的是纸浆。这是一个 Python 脚本示例：

from pulp import LpProblem, LpVariable, LpMaximize, LpBinary, PULP_CBC_CMD, lpSum

N = 5000
max_y_val = 5
model = LpProblem(sense=LpMaximize)

print("defining X")
x = [LpVariable(name=f"x_{i}", cat=LpBinary) for i in range(N)]

print("defining Y")
y = [x[0]]
for i in range(1, N):
    print(i)
    y.append(y[i-1] + x[i])

print("add y to model") 
for i in range(N):
    print(i)
    model += y[i] <= max_y_val

print("objective")
model += lpSum(x) # ...

print("start optimizer")
status = model.solve(PULP_CBC_CMD(msg=False, timeLimit=10))

print("score:", model.objective.value())
print("x:", *[x[i].value() for i in range(N)])
print()

有了

N=1000

，它仍然进展得很快。在

N=5000

将 y 添加到模型时变得非常慢。

我在 rust 中重写了相同的代码（使用 good_lp 库）来查看问题是否与 python 相关，但问题仍然存在。所以很可能问题是我写问题的方式。 因此，这不是一个特定于语言的问题。

我怀疑它可能使用矩阵

M * x = y

。

N

数量较多的矩阵的宽度将变为

N + 1

。可能看起来像一个三角矩阵，只有左下角有元素。

matrix      x   y

1 0 0 0 0   0   0
1 1 0 0 0   1   1
1 1 1 0 0 * 0 = 1
1 1 1 1 0   1   2
1 1 1 1 1   1   3

你知道我一般如何使用 LP 求解器来做到这一点吗？我觉得我在这里缺少一些知识。

Answer 1

另一篇文章给了我一个想法，所需的空间和时间可能非常大。

模型不会在矩阵中存储零值，但仍然需要存储所有约束。条目数为 ~(N+1)²/2。因此，对于多个规模

N=10000

，这很快就会变成 1 亿个条目。考虑到模型中存储的每个条目的 RAM 使用量有多大，这很容易变成 1 GB 内存。加上内存复制的开销以及可能将其写入文件的开销，供求解器使用。

我可能需要重新思考我的问题并优化。