DOCPLEX MIP 热启动

Question

我正在尝试解决大型 MIP 调度问题。由于解题时间会很长，所以想运行同一个事件点较少的模型，求它的第n解。使用该解决方案作为更大（更多事件点）模型的初始 solution/seed 以找到其第 n 个解决方案并使用它来级联直到所需数量的事件点。

使用小问题的解决方案，我在mip start中使用它的二进制值，让新添加的事件点不被触及。我将这些值保存在字典名称 seed_sol 中，其中键是二进制变量（在创建变量时获取），值是上一个求解的 0/1。

m.add_mip_start(SolveSolution(m, seed_sol))

使用上面的代码，我热启动了较大的运行s。然而，当我查看输出日志时，我意识到解决方案很少改进并且差距非常小（我知道实际的最佳解决方案要高得多）。我怀疑 'add_mip_start' 函数将解决方案值强制为我的初始种子解决方案，并试图通过仅调整新添加的二进制变量来改进解决方案。

我该如何解决这个问题以获得预期的结果？

使用：

Python 3.6.8
复杂 12.10.0.0
docplex 2.19.202

Answer 1

warmstart 提供了一个起点但不会减少搜索space。

https://github.com/AlexFleischerParis/zoodocplex/blob/master/zoowarmstartapi.py 处的示例：

from docplex.mp.model import Model

mdl = Model(name='buses')
nbbus40 = mdl.integer_var(name='nbBus40')
nbbus30 = mdl.integer_var(name='nbBus30')
mdl.add_constraint(nbbus40*40 + nbbus30*30 >= 300, 'kids')
mdl.minimize(nbbus40*500 + nbbus30*400)

warmstart=mdl.new_solution()
warmstart.add_var_value(nbbus40,8)
warmstart.add_var_value(nbbus30,0)
mdl.add_mip_start(warmstart)


sol=mdl.solve(log_output=True)

for v in mdl.iter_integer_vars():
    print(v," = ",v.solution_value)

您可以尝试的是固定启动

示例来自 https://github.com/AlexFleischerParis/zoodocplex/blob/master/zoofixedstart.py

from docplex.mp.model import Model

mdl = Model(name='buses')
nbbus40 = mdl.integer_var(name='nbBus40')
nbbus30 = mdl.integer_var(name='nbBus30')
mdl.add_constraint(nbbus40*40 + nbbus30*30 >= 300, 'kids')
mdl.minimize(nbbus40*500 + nbbus30*400)

#Fixed start nbBus40 should be 5
nbbus40.lb=5
nbbus40.ub=5

mdl.solve()


for v in mdl.iter_integer_vars():
    print(v," = ",v.solution_value)

Answer 2

MIP 起点用作起点，但其起点值可能会在搜索中更改，这与固定起点相反，其中固定值被视为硬约束。顺便说一句，您还可以使用约束来实现固定启动，这有助于添加或删除这些固定启动。

但是，MIP 启动的兴趣在于初始解决方案的质量。在你的情况下，最初的解决方案似乎比大问题小得多，所以它可能没有多大帮助。

为了评估您的 MIP 性能问题，您能否指出问题的严重程度（如 Model.print_information()) 所打印）还有 CPLEX 日志（至少是 cplex 停止的部分。）

DOCPLEX MIP 热启动

DOCPLEX MIP warmstart

python

cplex

docplex