是否可以同时使用启发式和数学规划来解决 NP-hard problem？
Is it possible to solve a NP-hard problem using both heuristic and mathematical programming?
我有一个并行机调度问题的遗传算法和混合整数规划模型。但是数学模型需要太多时间来解决问题，而遗传算法不太可能花费更少的时间但没有显示出最优解。所以我很好奇是否不可能从遗传算法中获取解决方案并将它们设置为数学编程的起点。事实上可能吗？
假设您使用经典的 Branch and Bound MIP-Solver，如果您提供启发式解决方案（例如通过相应的回调），它将在一定程度上帮助求解器。不仅是一个，你还可以提供更多的解决方案。
- 问题是，在大多数情况下，MIP 求解器试图证明最优性。即使找到了最优解，他们也要 运行 小时和天来证明，他们找到了最优解。因此，也许您可以为 objective 值设置更大的差距，这是最优的。通常这很有帮助。
- 调度问题通常是高度对称的，并且通常使用简单的公式表现得相当糟糕。尝试为您的日程安排问题查找科学文献。也许在一些关于堆栈交换的数学论坛上。
- 如果直接提出这些问题，则 LP 松弛通常不会非常紧。在许多情况下，您将需要一些额外的削减，以达到至少可以接受的效果。这也对二元性差距产生了影响。
因此尝试为 objective 值给出第一个允许的大差距。然后尝试通过相应的启发式回调将几个好的（和不同的解决方案）传递给 MIP-Solver。如果仍然无法接受，请尝试为您的问题查找一些文献。但我认为，MathOverflow-Forum 更适合那些模型主题（并且可能，您会发现比这里有更多关于该主题的专业意见）。
我有一个并行机调度问题的遗传算法和混合整数规划模型。但是数学模型需要太多时间来解决问题，而遗传算法不太可能花费更少的时间但没有显示出最优解。所以我很好奇是否不可能从遗传算法中获取解决方案并将它们设置为数学编程的起点。事实上可能吗？
假设您使用经典的 Branch and Bound MIP-Solver，如果您提供启发式解决方案（例如通过相应的回调），它将在一定程度上帮助求解器。不仅是一个，你还可以提供更多的解决方案。
- 问题是，在大多数情况下，MIP 求解器试图证明最优性。即使找到了最优解，他们也要 运行 小时和天来证明，他们找到了最优解。因此，也许您可以为 objective 值设置更大的差距，这是最优的。通常这很有帮助。
- 调度问题通常是高度对称的，并且通常使用简单的公式表现得相当糟糕。尝试为您的日程安排问题查找科学文献。也许在一些关于堆栈交换的数学论坛上。
- 如果直接提出这些问题，则 LP 松弛通常不会非常紧。在许多情况下，您将需要一些额外的削减，以达到至少可以接受的效果。这也对二元性差距产生了影响。
因此尝试为 objective 值给出第一个允许的大差距。然后尝试通过相应的启发式回调将几个好的（和不同的解决方案）传递给 MIP-Solver。如果仍然无法接受，请尝试为您的问题查找一些文献。但我认为，MathOverflow-Forum 更适合那些模型主题（并且可能，您会发现比这里有更多关于该主题的专业意见）。