/usr/share/mozart/doc/cpitut/node22.html is in mozart-doc 1.4.0-8ubuntu1.
This file is owned by root:root, with mode 0o644.
The actual contents of the file can be viewed below.
1 2 | <!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
<HTML><HEAD><TITLE>3.2 The Finite Domain Model</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="node21.html#lp.tutorial.intro"><< Prev</A></TD><TD><A href="lp.html">- Up -</A></TD><TD><A href="node23.html#lp.tutorial.lp">Next >></A></TD></TR></TABLE><DIV id="lp.tutorial.fd"><H2><A name="lp.tutorial.fd">3.2 The Finite Domain Model</A></H2><P>The finite domain model is a one-to-one translation of the LP model. Every problem variable of <IMG alt="\mbox{\bf x}" src="latex113.png"> is represented by a finite domain variable. The inequalities are expressed by appropriate finite domain constraints. </P><BLOCKQUOTE class="linenumbers"><PRE><SPAN class="keyword">declare</SPAN> <BR><SPAN class="keyword">fun</SPAN><SPAN class="variablename"> </SPAN>{<SPAN class="functionname">KnapsackFD</SPAN> Problem}<BR> NumProducts = {Length Problem<SPAN class="keyword">.</SPAN>profit}<BR> Resources = Problem<SPAN class="keyword">.</SPAN>resources<BR><SPAN class="keyword">in</SPAN> <BR> <SPAN class="keyword">proc</SPAN><SPAN class="variablename"> </SPAN>{<SPAN class="functionname">$</SPAN> Sol}<BR> sol(maxprofit: MaxProfit = {FD<SPAN class="keyword">.</SPAN>decl}<BR> products: Products = {FD<SPAN class="keyword">.</SPAN>list NumProducts 0<SPAN class="keyword">#</SPAN>FD<SPAN class="keyword">.</SPAN>sup})<BR> = Sol<BR> <SPAN class="keyword">in</SPAN> <BR> MaxProfit = {FD<SPAN class="keyword">.</SPAN>sumC Problem<SPAN class="keyword">.</SPAN>profit Products <SPAN class="string">'=:'</SPAN>}<BR> <BR> {ForAll {Arity Resources}<BR> <SPAN class="keyword">proc</SPAN><SPAN class="variablename"> </SPAN>{<SPAN class="functionname">$</SPAN> ResourceName}<BR> Resource = Resources<SPAN class="keyword">.</SPAN>ResourceName<BR> <SPAN class="keyword">in</SPAN> <BR> {FD<SPAN class="keyword">.</SPAN>sumC Resource<SPAN class="keyword">.</SPAN>npp Products <SPAN class="string">'=<:'</SPAN> Resource<SPAN class="keyword">.</SPAN>ta}<BR> <SPAN class="keyword">end</SPAN>}<BR> <BR> {FD<SPAN class="keyword">.</SPAN>distribute naive Products}<BR> <SPAN class="keyword">end</SPAN> <BR><SPAN class="keyword">end</SPAN> <BR></PRE></BLOCKQUOTE><P> The function <CODE>KnapsackFD</CODE> returns a procedure abstracting the script. The solution variable <CODE>Sol</CODE> of the script is constrained to a record. The record provides access to the individual quantities of the individual products (under feature <CODE>products</CODE>) to obtain a maximum profit (under feature <CODE>maxprofit</CODE>). </P><P>The variable <CODE>Products</CODE> refers to a list of finite domain problem variables (corresponding to <IMG alt="\left[x_1,\ldots,x_n\right]^T" src="latex114.png"> in the LP model) and <CODE>MaxProfit</CODE> is constrained to be the scalar product of the <CODE>Product</CODE> variable and the profit vector for the problem specification (see <A href="node21.html#lp.tutorial.intro">Section 3.1</A>). </P><P>The <CODE>ForAll</CODE> iterator imposes the inequality constraints <IMG alt="a_{1,i} x_1 + \cdots + a_{n,i} x_n \le b_i" src="latex115.png"> to the problem variables. The distribution strategy is straightforwardly chosen to <CODE>naive</CODE>. Experimenting with first fail (<CODE>ff</CODE>) produced even worse results. </P><P>Solving the problem by calling </P><BLOCKQUOTE class="code"><CODE>{ExploreBest {KnapsackFD Problem}<BR> <SPAN class="keyword">proc</SPAN><SPAN class="variablename"> </SPAN>{<SPAN class="functionname">$</SPAN> O N} O<SPAN class="keyword">.</SPAN>maxprofit <SPAN class="keyword"><:</SPAN> N<SPAN class="keyword">.</SPAN>maxprofit <SPAN class="keyword">end</SPAN>}</CODE></BLOCKQUOTE><P> produces the following search tree. </P><DIV align="left"><IMG alt="" class="left" src="mks_fd_explorer.gif" id="mks_fd_explorer.pic"></DIV><P> </P></DIV><TABLE align="center" border="0" cellpadding="6" cellspacing="6" class="nav"><TR bgcolor="#DDDDDD"><TD><A href="node21.html#lp.tutorial.intro"><< Prev</A></TD><TD><A href="lp.html">- Up -</A></TD><TD><A href="node23.html#lp.tutorial.lp">Next >></A></TD></TR></TABLE><HR><ADDRESS><A href="http://www.ps.uni-sb.de/~tmueller/">Tobias Müller</A><BR><SPAN class="version">Version 1.4.0 (20110908185330)</SPAN></ADDRESS></BODY></HTML>
|