TL;DR 版本：有没有办法处理存在大量最优解（找到最佳目标值的解）的优化问题？也就是说，找到最佳解决方案非常快（但显然很大程度上取决于问题的大小），但存在许多这样的解决方案，因此求解器无休止地试图找到更好的解决方案（无休止地因为它确实找到了其他可行的解决方案，但目标值等于当前最佳值）。
不是 TL；DR 版本： 对于一个大学项目，我需要实现一个调度器，该调度器应该输出每个大学课程每年学习的时间表。我提供了一些数据，对于这个问题，我只会坚持一个一般但没有那么罕见的例子。
在许多部分中，您有必修课和选修课。有时，这些可选课程分为模块，学生需要选择其中一个模块。通常，他们必须选择两个模块，但某些组合比其他组合出现的频率更高。显然，如果您计算课程数量（必修课 + 选修课）而不考虑对模块的细分，那么您的课程恰好多于需要安排的时间段。我的模型很简单。我有一些限制，即每门课程都应安排在一个且只有一个时间段（2小时），并且教授不应同时开设两门课程。这些都是硬约束。问题是，在一个完美的世界里，我应该添加硬约束，说明一个学生不能同时学习两门课程。
这就是为什么我决定在优化问题中移动这些硬约束。我简单地定义我的目标函数，为每个学生最小化他/她同时安排的课程数量。
If I run this simple model with only one student (22 courses) and 20 time slots, I should have an objective value of 4 (since 2 time slots embed each 2 courses). But, using Gurobi, the relaxed objective is 0 (since you can have fraction of courses inside a time slot). Therefore, when the solver does reach a solution of cost 4, it cannot prove optimality directly. The real trouble, is that for this simple case, there exists a huge number of optimal solutions (22! maybe...). Therefore, to prove optimality, it will go through all other solutions (which share the same objective) desperately trying to find a solution with a smaller gap between the relaxed objective (0) and the current one (4). Obviously, such solution doesn't exist...
您对我如何解决这个问题有任何想法吗？我想分析现有的数据库并试图找出哪些模块组合很可能发生，这样我就可以放回硬约束，但它似乎很危险（也许我会选择一个导致冲突的组合，因此找不到任何解决方案或省略有效的组合）。我使用的当前解决方案是设置时间阈值来停止优化......