/usr/share/mozart/doc/cpitut/node23.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 3 | <!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
<HTML><HEAD><TITLE>3.3 The Linear Programming 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="node22.html#lp.tutorial.fd"><< Prev</A></TD><TD><A href="lp.html">- Up -</A></TD><TD><A href="node24.html#lp.tutorial.fdlp">Next >></A></TD></TR></TABLE><DIV id="lp.tutorial.lp"><H2><A name="lp.tutorial.lp">3.3 The Linear Programming Model</A></H2><P>Tackling a multi-knapsack problem with a LP solver amounts to implementing a branch & bound solver to obtain integral solutions. The idea is to compute a continuous solution and to branch over the problem variables with continuous solutions. This is done until only integral problem variables are left. This is what the procedure <CODE>DistributeKnapSackLP</CODE> does. </P><BLOCKQUOTE class="linenumbers"><PRE><SPAN class="keyword">declare</SPAN> <BR><SPAN class="keyword">proc</SPAN><SPAN class="variablename"> </SPAN>{<SPAN class="functionname">DistributeKnapSackLP</SPAN> Vs ObjFn Constraints MaxProfit}<BR> <SPAN class="keyword">choice</SPAN> <BR> DupVs = {DuplicateRIs Vs}<BR> DupMaxProfit V DupV<BR> <SPAN class="keyword">in</SPAN> <BR> DupMaxProfit = {RI<SPAN class="keyword">.</SPAN>var<SPAN class="keyword">.</SPAN>bounds<BR> {RI<SPAN class="keyword">.</SPAN>getLowerBound MaxProfit}<BR> {RI<SPAN class="keyword">.</SPAN>getUpperBound MaxProfit}}<BR> <BR> {LP<SPAN class="keyword">.</SPAN>solve DupVs ObjFn Constraints DupMaxProfit optimal}<BR> <BR> V<SPAN class="keyword">#</SPAN>DupV = {SelectVar Vs<SPAN class="keyword">#</SPAN>DupVs}<BR> <BR> <SPAN class="keyword">case</SPAN> {IsDet V} <SPAN class="keyword">then</SPAN> <BR> DupMaxProfit = MaxProfit<BR> DupVs = Vs<BR> <SPAN class="keyword">else</SPAN> <BR> <SPAN class="keyword">choice</SPAN> <BR> {RI<SPAN class="keyword">.</SPAN>lessEq {Ceil DupV} V} <BR> <SPAN class="keyword">[]</SPAN> <BR> {RI<SPAN class="keyword">.</SPAN>lessEq V {Floor DupV}} <BR> <SPAN class="keyword">end</SPAN> <BR> {DistributeKnapSackLP Vs ObjFn Constraints MaxProfit}<BR> <SPAN class="keyword">end</SPAN> <BR> <SPAN class="keyword">end</SPAN> <BR><SPAN class="keyword">end</SPAN> <BR></PRE></BLOCKQUOTE><P> It first duplicates the problem variables (note this is possible due to stability) and invokes the LP solver on them to compute a (possibly continuous) solution. Then it selects the first duplicated continuous problem variable <CODE>DupV</CODE> by <CODE>SelectVar</CODE> (see below). If continuous variables are left (see the <CODE><SPAN class="keyword">else</SPAN></CODE> branch of the <CODE><SPAN class="keyword">case</SPAN></CODE> statement), it creates two choices on the corresponding original problem variable <CODE>V</CODE>: <IMG alt="\lceil DupV \rceil \le V \vee V \le
\lfloor DupV \rfloor" src="latex116.png"> and calls <CODE>DistributeKnapSackLP</CODE> recursively. In case no continuous variables are left, an integral solution is found and the original problem variables are unified with duplicated ones. </P><P>For completeness sake the auxiliary functions <CODE>SelectVar</CODE> and <CODE>DuplicateRIs</CODE> are presented here. </P><TABLE align="center" class="dyptic" id="table.mks.lp.a.b"><TR valign="top"><TD><P></P><BLOCKQUOTE class="linenumbers"><PRE><SPAN class="keyword">declare</SPAN> <BR><SPAN class="keyword">fun</SPAN><SPAN class="variablename"> </SPAN>{<SPAN class="functionname">SelectVar</SPAN> VsPair}<BR> <SPAN class="keyword">case</SPAN> VsPair<BR> <SPAN class="keyword">of</SPAN> nil<SPAN class="keyword">#</SPAN>nil <SPAN class="keyword">then</SPAN> <SPAN class="keyword">unit#unit</SPAN> <BR> <SPAN class="keyword">[]</SPAN> (VH<SPAN class="keyword">|</SPAN>VT)<SPAN class="keyword">#</SPAN>(RVH<SPAN class="keyword">|</SPAN>RVT) <SPAN class="keyword">then</SPAN> <BR> % <SPAN class="comment">check for integrality<BR></SPAN> <SPAN class="keyword">case</SPAN> RVH <SPAN class="keyword">==</SPAN> {Round RVH}<BR> <SPAN class="keyword">then</SPAN> {SelectVar VT<SPAN class="keyword">#</SPAN>RVT}<BR> <SPAN class="keyword">else</SPAN> VH<SPAN class="keyword">#</SPAN>RVH <SPAN class="keyword">end</SPAN> <BR> <SPAN class="keyword">else</SPAN> <SPAN class="keyword">unit</SPAN> <BR> <SPAN class="keyword">end</SPAN> <BR><SPAN class="keyword">end</SPAN> <BR></PRE></BLOCKQUOTE><P></P></TD><TD><P></P><BLOCKQUOTE class="linenumbers"><PRE><SPAN class="keyword">declare</SPAN> <BR><SPAN class="keyword">fun</SPAN><SPAN class="variablename"> </SPAN>{<SPAN class="functionname">DuplicateRIs</SPAN> Vs}<BR> {Map Vs<BR> <SPAN class="keyword">fun</SPAN><SPAN class="variablename"> </SPAN>{<SPAN class="functionname">$</SPAN> V}<BR> {RI<SPAN class="keyword">.</SPAN>var<SPAN class="keyword">.</SPAN>bounds<BR> {RI<SPAN class="keyword">.</SPAN>getLowerBound V}<BR> {RI<SPAN class="keyword">.</SPAN>getUpperBound V}}<BR> <SPAN class="keyword">end</SPAN>}<BR><SPAN class="keyword">end</SPAN> <BR></PRE></BLOCKQUOTE><P></P></TD></TR></TABLE><P> </P><P>The procedure <CODE>KnapsackLP</CODE> return the script which creates the appropriate parameters for the LP solver and eventually calls <CODE>DistributeKnapSackLP</CODE>. </P><BLOCKQUOTE class="linenumbers"><PRE><SPAN class="keyword">declare</SPAN> <BR><SPAN class="keyword">fun</SPAN><SPAN class="variablename"> </SPAN>{<SPAN class="functionname">KnapsackLP</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 = {RI<SPAN class="keyword">.</SPAN>var<SPAN class="keyword">.</SPAN>decl}<BR> products: Products = {MakeList NumProducts})<BR> = Sol<BR> <BR> ObjFn Constraints<BR> <SPAN class="keyword">in</SPAN> <BR> {ForAll Products <SPAN class="keyword">proc</SPAN><SPAN class="variablename"> </SPAN>{<SPAN class="functionname">$</SPAN> V}<BR> {RI<SPAN class="keyword">.</SPAN>var<SPAN class="keyword">.</SPAN>bounds 0<SPAN class="keyword">.</SPAN>0 RI<SPAN class="keyword">.</SPAN>sup V}<BR> <SPAN class="keyword">end</SPAN>}<BR> <BR> ObjFn = objfn(row: {Map Problem<SPAN class="keyword">.</SPAN>profit IntToFloat}<BR> opt: max)<BR> <BR> Constraints = <BR> {Map {Arity Resources}<BR> <SPAN class="keyword">fun</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> constr(row: {Map Resource<SPAN class="keyword">.</SPAN>npp IntToFloat}<BR> type: <SPAN class="string">'=<'</SPAN> <BR> rhs: {IntToFloat Resource<SPAN class="keyword">.</SPAN>ta})<BR> <SPAN class="keyword">end</SPAN>}<BR> <BR> {DistributeKnapSackLP Products ObjFn Constraints<BR> MaxProfit}<BR> <SPAN class="keyword">end</SPAN> <BR><SPAN class="keyword">end</SPAN> <BR></PRE></BLOCKQUOTE><P> </P><P>Feeding </P><BLOCKQUOTE class="code"><CODE>{ExploreBest {KnapsackLP Problem} <BR> <SPAN class="keyword">proc</SPAN><SPAN class="variablename"> </SPAN>{<SPAN class="functionname">$</SPAN> O N} <BR> {RI<SPAN class="keyword">.</SPAN>lessEq O<SPAN class="keyword">.</SPAN>maxprofit<SPAN class="keyword">+</SPAN>1<SPAN class="keyword">.</SPAN>0 N<SPAN class="keyword">.</SPAN>maxprofit} <BR> <SPAN class="keyword">end</SPAN>}</CODE></BLOCKQUOTE><P> produces the following search tree. </P><DIV align="center"><IMG alt="" src="mks_lp_explorer.gif" id="mks_lp_explorer.pic"></DIV><P> </P></DIV><TABLE align="center" border="0" cellpadding="6" cellspacing="6" class="nav"><TR bgcolor="#DDDDDD"><TD><A href="node22.html#lp.tutorial.fd"><< Prev</A></TD><TD><A href="lp.html">- Up -</A></TD><TD><A href="node24.html#lp.tutorial.fdlp">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>
|