r - 为什么 lpSolveAPI 求解器在第二次运行时变慢？

Question

R 中的lpSolveAPI包允许您指定和求解线性程序。然而，调用solve()一个已经解决的 LP 比一开始就解决 LP 慢得多。为什么会发生这种情况，如何避免这个问题？

这是一个显示问题的最小示例：

set.seed(42)

library(lpSolveAPI)


#------------
# Set up LP
#------------

m <- 2 ** 15

lps.model <- make.lp(nrow = m, ncol = 3)

set.column(lps.model, 1, rep(1,m))
set.column(lps.model, 2, rep(1,m))
set.column(lps.model, 3, rep(-1,m))

set.rhs(lps.model, rnorm(m) + rep(5,m))

set.objfn(lps.model,c(1,0,0))

set.constr.type(lps.model, rep(">=",m))


#-----------------
# Solve it twice
#-----------------


system.time(solve(lps.model)) # 0.02 elapsed

system.time(solve(lps.model)) # 0.14 elapsed

为什么这有关系？

我正在做一些顺序统计测试；每个测试都涉及求解一个 LP，每个 LP 与最后一个的不同之处仅在于 O(log m) 约束。理论上，通过求解第一个 LP 并保存解决方案，稍微编辑约束，然后将解决方案用作下一个 LP 的热启动，应该可以非常快速地做到这一点。

上面的问题扩展到使用delete.constraint()/编辑 LP add.constraint()，这使得“有效”解决方案比解决每个 LP 冷的天真的方法慢得多。

标签： rlinear-programminglpsolve