definition · term 3 of 25
branch and bound (B&B).
An algorithm for integer and combinatorial problems that splits the search into subproblems and discards those that cannot contain a better solution.
worked exampleone branch prunedBranch A can reach a cost of 100 at best. A plan with cost 96 is already known. Branch A is cut without exploring it, and the search continues where a better plan is still possible.
in plain language
Branch and bound divides a problem into smaller subproblems (branching) and computes a bound on the best result each one could reach. If that bound cannot beat the best solution found so far, the whole branch is pruned. The method avoids checking every combination and still proves optimality when it finishes.
branch and bound, on your own decision.
Bring one recurring decision. Your planners see the terms of this glossary applied to their own rules and data.
- Glossary
- all 25 terms, a to z
- Problem types
- the decisions kint solves
- Comparisons
- kint next to other approaches
- Contact
- hello@kint.pro