linear-programming - 使用分支定界查找混合整数线性程序的所有答案？

Question

我正在尝试解决可能有多个答案的 MILP（所有答案都为目标函数提供相同的值）。基于分支定界的算法是否能够找到所有解决方案？

是否可以使用 MATLAB（例如使用 intlinprog）找到此类 MILP 的所有解决方案。

谢谢你。

Answer 1

如果节点的 LP 松弛的目标值大于或等于当前最佳上限（假设最小化问题），则标准分支定界算法会计算节点。从理论上讲，您可以更改此设置，以便仅在 LP 值严格大于当前 UB 时才能了解节点。然后，您可以保留与当前 UB 相关的所有解决方案的列表。当你找到一个新的更好的 UB 时，清除列表并开始构建一个新的。

显然，这会减慢搜索速度，特别是如果，正如 TimChippingtonDerrick 所说，有很多最优值。

这需要自定义 B&B 代码。我敢肯定，除非您编写自己的分支定界代码，然后从中调用 MATLAB 的 LP 求解器，否则您无法在 MATLAB 中执行此操作。您可能可以在 CPLEX 的 API 或其他一些求解器中完成。在任何情况下，您可能都不得不编写自己的 B&B 代码。