DOCPLEX MIP暖启动

Question

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

使用来自小问题的解决方案，我在mip启动中使用它的二进制值，并让新添加的事件点未被触及。我将这些值保存在字典名seed_sol中，其中键是二进制变量(在创建varible时获得)，并且值是前面解决方案中的0/1。

m.add_mip_start(SolveSolution(m, seed_sol))

使用上面的代码，我温暖地开始我的更大的运行。然而，当我查看输出日志时，我意识到解决方案很少改进，而且差距很小(我知道实际的最优解决方案要高得多)。我怀疑'add_mip_start‘函数强制将解值传递给我的初始种子解，并试图通过调整新添加的二进制变量来改进解决方案。

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

使用：

12.10.0.0

• docplex 2.19.202
• Python 3.6.8

Answer 1

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

在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 start被用作起点，但它的起始值可能在搜索中被更改，而不是固定的start，后者将固定值视为硬约束。顺便说一句，您还可以使用约束实现固定的启动，这有助于添加或删除这些固定的启动。

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

要评估您的MIP性能问题，可以指出问题的大小(如Model.print_information())打印的)和CPLEX日志(至少是cplex停止运行的部分)。