<< Prev | - Up - | Next >> |

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 8.2 and Section 8.4, we have used a rather ad-hoc strategy there. This strategy lacks generality and does not provide either for a proof of optimality.

branch and bound

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 Oz. This schema is called *branch and bound* and is available by procedures like `ExploreBest`

(see ``Oz Explorer - Visual Constraint Programming Support'' and Chapter 4 of ``System Modules'' for more search engines). A typical application of `ExploreBest`

for a script `Script`

looks like

`{ExploreBest Script Order}`

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 first argument of `Order`

is the previous solution, and the second argument is an alternative solution we are searching for.

<< Prev | - Up - | Next >> |

Christian Schulte and Gert Smolka

Version 1.4.0 (20080702)