Why ILP Solver Switching to Branch-and-Bound?

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!

Answer 1

[Matt J]

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.

[Maria]

Thank you very much! I waited and the problem was solved.