Branch and Bound

In this chapter we focus on computing an optimal solution according to a given cost function. While we have searched for optimal solutions already in Section 9.2 and Section 9.4, we have used a rather ad-hoc strategy there. This strategy lacks generality and does not provide either for a proof of optimality.

In this chapter we introduce a general schema to compute an optimal solution according to an arbitrary cost function and show how it is available in Alice. This schema is called branch and bound and is available by procedures like ExploreBest. A typical application of ExploreBest for a script Script looks like

Explorer.exploreBest Script

The branch and bound schema works as follows. When a solution of Script is found, all the remaining alternatives in the search tree are constrained to be better with respect to an order available through the procedure Order. Usually Order applies a cost function to its arguments and creates a propagator imposing the ordering. The second argument of Order is the previous solution, and the first argument is an alternative solution we are searching for.