0

我正在使用带有 CBC_MIXED_INTEGER_PROGRAMMING 求解器的 Google OR-Tools。

大多数情况下，求解器会在不到 20 秒的时间内找到最优解，但有时需要几分钟才能找到。它可以非常快速地猜测出对解决方案的良好估计，但找到最佳解决方案需要很长时间。

我的第一个想法是设置一个简单的时间限制，以返回 30 秒后找到的最佳解决方案：

solver = pywraplp.Solver('scheduling_solver', pywraplp.Solver.CBC_MIXED_INTEGER_PROGRAMMING)
solver.SetTimeLimit(30*1000) # 30 seconds time limit

不幸的是，此时找到的解决方案可能与最佳解决方案相差太远。

是否有可能：

  1. [00 - 30 秒] 如果在不到 30 秒内找到最佳解决方案，则返回该解决方案。
  2. [30 - 60 秒] 如果未找到最佳解决方案，则接受 5% 的 GAP 额外 30 秒（GAP LIMIT）
  3. [60+ 秒] 如果求解器在一分钟后仍在运行，则返回找到的最佳解决方案 (TIME LIMIT)

提前谢谢了，

罗曼

4

3 回答 3

1

这对于 CLP/CBC 是绝对不可能的。至少使用 OR-Tools 公开的 API，甚至很可能使用求解器直接 API。

于 2020-07-28T15:14:46.893 回答
1

对豪尔赫的回答稍作调整：

model = pywraplp.Solver('model', pywraplp.Solver.SCIP_MIXED_INTEGER_PROGRAMMING)

# set time limit in milliseconds, both two methods are OK
model.set_time_limit(5000)  
# model.SetTimeLimit(5000)

# set a stopping gap limit for MIP
gap = 0.05
solverParams = pywraplp.MPSolverParameters()
solverParams.SetDoubleParam(solverParams.RELATIVE_MIP_GAP, gap)
status = model.Solve(solverParams)

请注意，间隙限制参数仅适用于SCIP（可能还有其他商业求解器），不适用于 CBC 或 SAT。

于 2021-03-11T08:39:21.000 回答
0

你可以尝试这样的事情：

model = pywraplp.Solver('my_model', pywraplp.Solver.CBC_MIXED_INTEGER_PROGRAMMING)

# set a time limit to get a solution in milliseconds
model.set_time_limit(60*1000)

# set a minimum gap limit for the integer solution during branch and cut
gap = 0.05
solverParams = pywraplp.MPSolverParameters()
solverParams.SetDoubleParam(solverParams.RELATIVE_MIP_GAP, gap)

通过这种方式，求解器将尝试找到一个受间隙或时间限制的解决方案，以先到者为准。这里的问题是你得到的解决方案并不比间隙限制给出的更好，因为一旦达到这个限制，求解器就会停止。

于 2020-08-25T08:37:37.093 回答