问用启发式和数学规划方法可以求解NP硬p‌r‌o‌b‌l‌e‌m吗？

EN

假设您使用经典分支和绑定MIP，如果您提供启发式解(例如，通过相应的回调)，它将帮助求解者达到一定的数量。不仅仅是一个，您还可以为解决方案池提供更多的服务。

1. 问题是，在大多数情况下，MIP试图证明最优性.即使找到了最优解，他们也要用几个小时和几天的时间来证明，他们找到了最优解。所以也许你可以为目标值设置一个更大的差距，这是最优性所接受的。通常这很有帮助。
2. 调度问题通常是高度对称的，对于直截了当的公式通常表现得相当糟糕。试着为你的日程安排问题找到科学的文献。也许在堆栈交换的数学论坛上。
3. 如果这些问题是直截了当的，LP-松弛通常不是超紧的.在许多情况下，您将需要一些exra削减，以执行至少可以接受。这对二元性差距也有影响。

所以试着给出第一个大的允许差距为目标值。然后尝试将几个好的(和不同的解决方案)传递给MIP，例如通过相应的启发式回调。如果它仍然不能被接受，试着为你的问题找到一些文献。但我认为，MathOverflow-Forum更适合这些模型主题(而且很可能，您会发现这个主题比这里更有技巧)。