optimization - 是否可以同时使用启发式和数学编程来解决 NP-hard p‌r‌o‌b‌l‌e‌m？

Question

我有一个并行机器调度问题的遗传算法和混合整数编程模型。但是数学模型需要太多时间来解决问题，而遗传算法不太可能需要更少的时间但没有显示出最优解。所以我很好奇是否不可能从遗传算法中获取解决方案并将它们作为数学编程的起点。事实上有可能吗？

Answer 1

假设您使用经典的分支定界 MIP 求解器，如果您提供启发式解决方案（例如通过相应的回调），它将在一定程度上帮助求解器。不仅是一个，您还可以为解决方案池提供更多。

1. 问题是，在大多数情况下，MIP-Solvers 试图证明最优性。即使找到了最佳解决方案，他们也会运行数小时和数天来证明他们找到了最佳解决方案。因此，也许您可​​以为目标值设置更大的差距，这是为了获得最优性而接受的。通常这有很大帮助。
2. 调度问题通常是高度对称的，并且通常用简单的公式执行相当糟糕。尝试为您的日程安排问题查找科学文献。也许在一些关于堆栈交换的数学论坛中。
3. 如果这些问题被直接制定，LP 松弛通常不是超级紧的。在许多情况下，您将需要一些额外的削减，以至少可以接受。这也对二元性差距产生了影响。

因此，请尝试为目标值提供第一个允许的较大差距。然后尝试通过相应的启发式回调将几个好的（和不同的解决方案）传递给 MIP-Solver。如果仍然无法接受，请尝试为您的问题查找一些文献。但我认为，MathOverflow-Forum 更适合那些模型主题（并且可能你会发现这个主题的专业意见比这里更多）。