How does the Least Cost Branch and Bound algorithm decide which node to explore next?

Conditions

• Applicable when using the Least Cost strategy for Branch and Bound.
• A cost function is defined for the problem.

Reasoning, step by step

1. Calculate the cost for each available node using the problem-dependent cost function.
2. Compare the costs of the nodes in the current frontier.
3. Select the node with the minimum cost.
4. Expand the selected node to generate its children.

Example

The instructor explains, "The node with the minimum cost I should explore next. Least cost, that's what it is least cost branch and bound." In the example, Node $2 (C=12)$ is expanded, generating Node $6 (C=8)$ and Node $7 (C=7)$. Node 7 is then selected because it has the minimum cost.

Common misconceptions

• Assuming the algorithm explores nodes in the order they were generated (FIFO) or reverse order (LIFO).
• Believing that the cost is arbitrary rather than derived from a specific cost function.

Watch the explanation

Explore next

• Why is Least Cost Branch and Bound considered more efficient than FIFO or LIFO?
• What is the difference between FIFO, LIFO, and Least Cost strategies in tree traversal?
• How do you construct the total cost objective function for the three-machine production problem?