Why ILP Solver Switching to Branch-and-Bound?

6 次查看（过去 30 天）
Maria
Maria 2024-8-20
评论： Maria 2024-8-21
Hello everyone,
I'm working on an integer linear programming (ILP) problem in MATLAB. When I solve the problem with a small number of variables, the solver quickly finds an optimal solution. However, when I increase the number of variables, the solver uses the branch-and-bound algorithm, which takes a long time. I would like to know if the ILP will display an optimal solution after the iterations of the branch-and-bound algorithm?
Any insights or tips on why the solver switches to branch-and-bound would be greatly appreciated!
Thank you!

请先登录，再回答此问题。

采纳的回答

Matt J
Matt J 2024-8-21
编辑：Matt J 2024-8-21
Assuming you are using intlinprog, it will always uses the branch-and-bound algorithm at some stage of the processing (not sure why you think it "switches"). And yes, the computational expense of branch-and-bound is exponential in the number of integer-constrained variables. It can therefore take an impractically long time for large numbers of variables, but in theory, it should always reach an optimal solution if you are willing to wait.

更多回答（0 个）

类别

在 Help Center 和 File Exchange 中查找有关 Get Started with Optimization Toolbox 的更多信息

标签

产品

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!

Translated by