Pyomo Objective 构建时间太长
Pyomo Objective takes too long to construct
我有一个 Pyomo objective 函数，它包含 2 个嵌套循环（总共 1,000,000 个循环），Pyomo 在我的计算机上构建它需要大约 40 秒。
m.obj = Objective(
expr=sum(
costs[int(w)][int(t)] * m.Assign[w, t] * (int(w) + int(t))
for w in workers # len 1000
for t in tasks # len 1000
)
)
有什么方法可以加快objective函数的创建速度吗？例如使用多处理，或者我们自己手动构造 objective 表达式而不是将其传递给 Pyomo 而不是让 Pyomo 执行构造？
我的示例 Pyomo 代码：
from pyomo.environ import *
import numpy as np
SIZE = 1000
costs = np.random.randint(1, 15, (SIZE, SIZE))
m = ConcreteModel()
m.W = Set(initialize=[str(i) for i in range(1, SIZE)])
m.T = Set(initialize=[str(i) for i in range(1, SIZE)])
m.Assign = Var(m.W, m.T, domain=Binary)
m.obj = Objective(
expr=sum(
costs[int(w)][int(t)] * m.Assign[w, t] * (int(w) + int(t))
for w in m.W
for t in m.T
)
)
def c1_rule(m, t):
return sum(m.Assign[w, t] for w in m.W) == 1
def c2_rule(m, w):
return sum(m.Assign[w, t] for t in m.T) == 1
m.c1 = Constraint(m.T, rule=c1_rule)
m.c2 = Constraint(m.W, rule=c2_rule)
solver = SolverFactory("glpk")
results = solver.solve(m)
答：不是真的。您不能并行化模型的构造。也就是说，如果您真的有 1M 个二元变量并且求解时间将使任何模型构建时间相形见绌——如果它甚至易于处理的话，这将是一个巨大的模型。
您提出的示例很容易通过 numpy 矩阵运算求解，并不真正适合 LP。也许您的实际情况有所不同，不需要 1M 个离散变量，这在银河系中也是巨大的。
首先，请注意您的示例中有一个轻微的 off-by-one 错误（W 和 T 的大小与 SIZE 不匹配，因为 Python的range(1, SIZE)在第二个参数之前停止1。
您在使用 NumPy 时遇到了已知的性能“怪癖”。当所有操作都可以留在“C”（编译）端时，NumPy 非常快。但是，按照您编写 objective 的方式，costs 数组的每个元素在击中 Pyomo 运算符之前从“C”端返回到 Python float超载。
以你的例子为例：
from pyomo.common.timing import tic, toc
from pyomo.environ import *
import numpy as np
SIZE = 1000
tic(None)
m = ConcreteModel()
m.W = Set(initialize=[str(i) for i in range(1, SIZE+1)])
m.T = Set(initialize=[str(i) for i in range(1, SIZE+1)])
m.Assign = Var(m.W, m.T, domain=Binary)
toc("Constructed Var")
costs = np.random.randint(1, 15, (SIZE, SIZE))
toc("numpy generated random numbers")
@m.Objective()
def obj(m):
return sum(
costs[int(w)-1][int(t)-1] * m.Assign[w, t] * (int(w) + int(t))
for w in m.W
for t in m.T
)
toc("Constructed Objective")
明白了
[+ 1.45] Constructed Var
[+ 0.01] numpy generated random numbers
[+ 10.63] Constructed Objective
如果我们完全避免使用 numpy，我们可以节省一些时间：
import random
m = ConcreteModel()
m.W = Set(initialize=[str(i) for i in range(1, SIZE+1)])
m.T = Set(initialize=[str(i) for i in range(1, SIZE+1)])
m.Assign = Var(m.W, m.T, domain=Binary)
toc("Constructed Var")
tic(None)
costs = {(w, t): random.randint(1, 15) for w in m.W for t in m.T}
toc("python generated random numbers")
@m.Objective()
def obj(m):
return sum(
costs[w,t] * m.Assign[w, t] * (int(w) + int(t))
for w in m.W
for t in m.T
)
toc("Constructed Objective")
给予
[+ 1.45] Constructed Var
[+ 0.79] python generated random numbers
[+ 5.59] Constructed Objective
节省时间完全是因为不必跨越循环内的 Python / C 边界。如果我们知道 Pyomo 的运算符重载如何工作并重组表达式以直接组合 float 项而不依赖 Pyomo 表达式系统来简化事情，我们可以节省更多时间。此示例还切换到使用基于 0 的 int 索引以避免将内容从 / 转换为字符串（主要是为了方便 - 转换时间不多 - 仅约 0.2 秒）：
m = ConcreteModel()
m.W = Set(initialize=range(SIZE))
m.T = Set(initialize=range(SIZE))
m.Assign = Var(m.W, m.T, domain=Binary)
toc("Constructed Var")
costs = {(w, t): random.randint(1, 15) for w in m.W for t in m.T}
toc("python generated random numbers")
@m.Objective()
def obj(m):
return sum(
costs[w, t] * (2 + w + t) * m.Assign[w, t]
for w in m.W
for t in m.T
)
toc("Constructed Objective")
给我们另一个适度的性能提升：
[+ 1.43] Constructed Var
[+ 0.79] python generated random numbers
[+ 4.06] Constructed Objective
最后，最近的 Pyomo 版本支持与 NumPy 的更好（尽管不完美）集成。特别是支持一些矢量化操作：
m = ConcreteModel()
m.W = Set(initialize=range(SIZE))
m.T = Set(initialize=range(SIZE))
m.Assign = Var(m.W, m.T, domain=Binary)
toc("Constructed Var")
costs = np.random.randint(1, 15, (SIZE, SIZE))
factor = np.array(range(SIZE)).repeat(SIZE).reshape(SIZE, SIZE)
factor = 2 + factor + factor.transpose()
toc("numpy generated random numbers")
@m.Objective()
def obj(m):
return sum(sum(costs * factor * m.Assign))
toc("Constructed Objective")
给出比原始模型快近 3 倍的解决方案：
[+ 1.44] Constructed Var
[+ 0.01] numpy generated random numbers
[+ 3.62] Constructed Objective
我有一个 Pyomo objective 函数，它包含 2 个嵌套循环（总共 1,000,000 个循环），Pyomo 在我的计算机上构建它需要大约 40 秒。
m.obj = Objective(
expr=sum(
costs[int(w)][int(t)] * m.Assign[w, t] * (int(w) + int(t))
for w in workers # len 1000
for t in tasks # len 1000
)
)
有什么方法可以加快objective函数的创建速度吗？例如使用多处理，或者我们自己手动构造 objective 表达式而不是将其传递给 Pyomo 而不是让 Pyomo 执行构造？
我的示例 Pyomo 代码：
from pyomo.environ import *
import numpy as np
SIZE = 1000
costs = np.random.randint(1, 15, (SIZE, SIZE))
m = ConcreteModel()
m.W = Set(initialize=[str(i) for i in range(1, SIZE)])
m.T = Set(initialize=[str(i) for i in range(1, SIZE)])
m.Assign = Var(m.W, m.T, domain=Binary)
m.obj = Objective(
expr=sum(
costs[int(w)][int(t)] * m.Assign[w, t] * (int(w) + int(t))
for w in m.W
for t in m.T
)
)
def c1_rule(m, t):
return sum(m.Assign[w, t] for w in m.W) == 1
def c2_rule(m, w):
return sum(m.Assign[w, t] for t in m.T) == 1
m.c1 = Constraint(m.T, rule=c1_rule)
m.c2 = Constraint(m.W, rule=c2_rule)
solver = SolverFactory("glpk")
results = solver.solve(m)
答：不是真的。您不能并行化模型的构造。也就是说，如果您真的有 1M 个二元变量并且求解时间将使任何模型构建时间相形见绌——如果它甚至易于处理的话，这将是一个巨大的模型。
您提出的示例很容易通过 numpy 矩阵运算求解，并不真正适合 LP。也许您的实际情况有所不同，不需要 1M 个离散变量，这在银河系中也是巨大的。
首先，请注意您的示例中有一个轻微的 off-by-one 错误（W 和 T 的大小与 SIZE 不匹配，因为 Python的range(1, SIZE)在第二个参数之前停止1。
您在使用 NumPy 时遇到了已知的性能“怪癖”。当所有操作都可以留在“C”（编译）端时，NumPy 非常快。但是，按照您编写 objective 的方式，costs 数组的每个元素在击中 Pyomo 运算符之前从“C”端返回到 Python float超载。
以你的例子为例：
from pyomo.common.timing import tic, toc
from pyomo.environ import *
import numpy as np
SIZE = 1000
tic(None)
m = ConcreteModel()
m.W = Set(initialize=[str(i) for i in range(1, SIZE+1)])
m.T = Set(initialize=[str(i) for i in range(1, SIZE+1)])
m.Assign = Var(m.W, m.T, domain=Binary)
toc("Constructed Var")
costs = np.random.randint(1, 15, (SIZE, SIZE))
toc("numpy generated random numbers")
@m.Objective()
def obj(m):
return sum(
costs[int(w)-1][int(t)-1] * m.Assign[w, t] * (int(w) + int(t))
for w in m.W
for t in m.T
)
toc("Constructed Objective")
明白了
[+ 1.45] Constructed Var
[+ 0.01] numpy generated random numbers
[+ 10.63] Constructed Objective
如果我们完全避免使用 numpy，我们可以节省一些时间：
import random
m = ConcreteModel()
m.W = Set(initialize=[str(i) for i in range(1, SIZE+1)])
m.T = Set(initialize=[str(i) for i in range(1, SIZE+1)])
m.Assign = Var(m.W, m.T, domain=Binary)
toc("Constructed Var")
tic(None)
costs = {(w, t): random.randint(1, 15) for w in m.W for t in m.T}
toc("python generated random numbers")
@m.Objective()
def obj(m):
return sum(
costs[w,t] * m.Assign[w, t] * (int(w) + int(t))
for w in m.W
for t in m.T
)
toc("Constructed Objective")
给予
[+ 1.45] Constructed Var
[+ 0.79] python generated random numbers
[+ 5.59] Constructed Objective
节省时间完全是因为不必跨越循环内的 Python / C 边界。如果我们知道 Pyomo 的运算符重载如何工作并重组表达式以直接组合 float 项而不依赖 Pyomo 表达式系统来简化事情，我们可以节省更多时间。此示例还切换到使用基于 0 的 int 索引以避免将内容从 / 转换为字符串（主要是为了方便 - 转换时间不多 - 仅约 0.2 秒）：
m = ConcreteModel()
m.W = Set(initialize=range(SIZE))
m.T = Set(initialize=range(SIZE))
m.Assign = Var(m.W, m.T, domain=Binary)
toc("Constructed Var")
costs = {(w, t): random.randint(1, 15) for w in m.W for t in m.T}
toc("python generated random numbers")
@m.Objective()
def obj(m):
return sum(
costs[w, t] * (2 + w + t) * m.Assign[w, t]
for w in m.W
for t in m.T
)
toc("Constructed Objective")
给我们另一个适度的性能提升：
[+ 1.43] Constructed Var
[+ 0.79] python generated random numbers
[+ 4.06] Constructed Objective
最后，最近的 Pyomo 版本支持与 NumPy 的更好（尽管不完美）集成。特别是支持一些矢量化操作：
m = ConcreteModel()
m.W = Set(initialize=range(SIZE))
m.T = Set(initialize=range(SIZE))
m.Assign = Var(m.W, m.T, domain=Binary)
toc("Constructed Var")
costs = np.random.randint(1, 15, (SIZE, SIZE))
factor = np.array(range(SIZE)).repeat(SIZE).reshape(SIZE, SIZE)
factor = 2 + factor + factor.transpose()
toc("numpy generated random numbers")
@m.Objective()
def obj(m):
return sum(sum(costs * factor * m.Assign))
toc("Constructed Objective")
给出比原始模型快近 3 倍的解决方案：
[+ 1.44] Constructed Var
[+ 0.01] numpy generated random numbers
[+ 3.62] Constructed Objective