使用分支定界找到混合整数线性程序的所有答案？
Find all answers to a Mixed-Integer-Linear-Program using branch and bound?
我正在尝试解决可能有多个答案的 MILP（所有答案都为 objective 函数提供相同的值）。基于分支定界的算法是否能够找到所有解决方案？
是否可以使用 MATLAB（例如使用 intlinprog）找到此类 MILP 的所有解决方案。
谢谢。
如果节点的 LP 松弛 objective 值大于 或等于 当前最佳上界（假设一个最小化问题）。理论上，您可以更改此设置，以便仅在 LP 值 strictly 大于当前 UB 时才了解节点。然后你可以保留一个列表，列出所有与当前 UB 相关的解决方案。当你找到一个新的更好的 UB 时，清除列表并开始构建一个新的。
显然，这会减慢搜索速度，特别是如果像 TimChippingtonDerrick 所说的那样，有很多最优值。
这需要自定义民宿代码。我敢肯定您 不会 在 MATLAB 中执行此操作，除非您编写自己的分支定界代码然后从中调用 MATLAB 的 LP 求解器。您或许能够在 CPLEX 的 API 或其他一些求解器中执行此操作。在任何情况下，您可能最终都必须编写自己的 B&B 代码。
我正在尝试解决可能有多个答案的 MILP（所有答案都为 objective 函数提供相同的值）。基于分支定界的算法是否能够找到所有解决方案？
是否可以使用 MATLAB（例如使用 intlinprog）找到此类 MILP 的所有解决方案。
谢谢。
如果节点的 LP 松弛 objective 值大于 或等于 当前最佳上界（假设一个最小化问题）。理论上，您可以更改此设置，以便仅在 LP 值 strictly 大于当前 UB 时才了解节点。然后你可以保留一个列表，列出所有与当前 UB 相关的解决方案。当你找到一个新的更好的 UB 时，清除列表并开始构建一个新的。
显然，这会减慢搜索速度，特别是如果像 TimChippingtonDerrick 所说的那样，有很多最优值。
这需要自定义民宿代码。我敢肯定您 不会 在 MATLAB 中执行此操作，除非您编写自己的分支定界代码然后从中调用 MATLAB 的 LP 求解器。您或许能够在 CPLEX 的 API 或其他一些求解器中执行此操作。在任何情况下，您可能最终都必须编写自己的 B&B 代码。