<!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
<HTML><HEAD><TITLE>10 Branch and Bound</TITLE><LINK href="ozdoc.css" rel="stylesheet" type="text/css"></HEAD><BODY><TABLE align="center" border="0" cellpadding="6" cellspacing="6" class="nav"><TR bgcolor="#DDDDDD"><TD><A href="node40.html#chapter.user-defined"><< Prev</A></TD><TD><A href="index.html">- Up -</A></TD><TD><A href="node46.html#chapter.scheduling">Next >></A></TD></TR></TABLE><DIV id="chapter.bab"><H1><A name="chapter.bab">10 Branch and Bound</A></H1><P> 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 <A href="node37.html#section.reified.photo">Section 8.2</A> and <A href="node39.html#section.reified.bin">Section 8.4</A>, we have used a rather ad-hoc strategy there. This strategy lacks generality and does not provide either for a proof of optimality.</P><P></P><P class="margin">branch and bound</P><P> 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 <A name="label120"></A><EM>branch and bound</EM> and is available by procedures like <CODE>ExploreBest</CODE> (see <A href="../explorer/index.html">``Oz Explorer - Visual Constraint Programming Support''</A> and <A href="../system/node9.html#chapter.search">Chapter 4 of ``System Modules''</A> for more search engines). A typical application of <CODE>ExploreBest</CODE> for a script <CODE>Script</CODE> looks like </P><BLOCKQUOTE class="code"><CODE>{ExploreBest Script Order}</CODE></BLOCKQUOTE><P> The branch and bound schema works as follows. When a solution of <CODE>Script</CODE> is found, all the remaining alternatives in the search tree are constrained to be <A name="label121"></A><EM>better</EM> with respect to an order available through the procedure <CODE>Order</CODE>. Usually <CODE>Order</CODE> applies a cost function to its arguments and creates a propagator imposing the ordering. The first argument of <CODE>Order</CODE> is the previous solution, and the second argument is an alternative solution we are searching for. </P><HR><UL class="toc"><LI><A href="node44.html#section.bab.align">10.1 Example: Aligning for a Photo, Revisited</A></LI></UL><UL class="toc"><LI><A href="node45.html#section.bab.warehouses">10.2 Example: Locating Warehouses</A><UL class="toc"><LI><A href="node45.html#label122">Problem Specification</A></LI><LI><A href="node45.html#label123">Model</A></LI><LI><A href="node45.html#label124">Distribution Strategy</A></LI><LI><A href="node45.html#label126">Script</A></LI></UL></LI></UL></DIV><TABLE align="center" border="0" cellpadding="6" cellspacing="6" class="nav"><TR bgcolor="#DDDDDD"><TD><A href="node40.html#chapter.user-defined"><< Prev</A></TD><TD><A href="index.html">- Up -</A></TD><TD><A href="node46.html#chapter.scheduling">Next >></A></TD></TR></TABLE><HR><ADDRESS><A href="http://www.ps.uni-sb.de/~schulte/">Christian Schulte</A> and <A href="http://www.ps.uni-sb.de/~smolka/">Gert Smolka</A><BR><SPAN class="version">Version 1.4.0 (20090610)</SPAN></ADDRESS></BODY></HTML>
distrib
>
Mandriva
>
2010.0
>
i586
>
media
>
contrib-release
>
by-pkgid
>
bd5c3d824c3db63ffd9226c15941e6ad
>
files
>
1218
