我必须最小化关于变量 u 的线性函数，变量 u 取值 [0,1]
变量数量可以超过10,000
有数千个线性不等式约束
我需要一个好的解决方案，但不必是最佳的。
是否有任何启发式方法可以做到这一点？
例如，我可以允许 0 <= u <= 1 然后使用 LP 求解器。然后我根据 LP 求解器的最佳值将 u 的值推到 0 或 1 来进行迭代。
我不知道该怎么做，但如果已经看过，那么我想知道。
我正在使用 CPLEX。
我必须解决一个大型二进制编程任务。我应该避免分支和绑定吗？
计算科学
优化
线性规划
约束优化
2021-12-17 22:04:42
1个回答
10,000 个变量对于整数规划问题来说已经很多了，但一切都取决于您特定问题的细节。有了所提供的信息，我们真的无法提前告诉您解决这个问题的难易程度。
我的建议是尝试使用 CPLEX 的整数规划求解器使用其默认设置解决此问题，并观察其行为方式。您可能会对被证明是最佳的快速解决方案感到惊喜。如果没有，您可能仍然能够获得一个解决方案，该解决方案在其与最优之间的目标值差距上具有良好的界限。
如果 CPLEX 运行多个小时而没有找到整数解，那么请当心 - 您会遇到一个问题，即使找到整数解也非常困难。如果 CPLEX 运行很长时间并在分支定界树中搜索许多节点，而没有显着减小最佳已知解与界限之间的差距，那么问题可能很难解决到最优。