DOCPLEX MIP暖机启动

Question

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

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

m.add_mip_start解决方案（m，seed_sol）

使用上面的代码，我可以开始更大的跑步。然而，当我查看输出日志时，我意识到解决方案很少有改进，而且差距非常小（我知道实际的最佳解决方案要高得多）。我怀疑“add_mip_start”函数会强制将解决方案值添加到我的初始种子解决方案中，并尝试仅通过调整新添加的二进制变量来改进解决方案。

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

使用：

• Python 3.6。8
• cplex 12.10。0.0
• docplex 2.19。202

Answer 1

MIP开始用作起点，但其开始值可能会在搜索中更改，而不是固定开始，其中固定值被视为硬约束。顺便说一句，还可以实现具有约束的固定启动，这有助于添加或删除这些固定启动。

然而，MIP start的兴趣在于初始解决方案的质量。在您的情况下，初始解决方案似乎比大问题小得多，因此可能没有多大帮助。

要评估MIP性能问题，您是否可以指出问题的大小（由Model.print_information（））打印）以及CPLEX日志（至少是CPLEX暂停的部分）

Answer 2

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

例如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)