/usr/share/mozart/doc/fdt/node49.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>11.3 Strong Propagators for Capacity Constraints </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="node48.html#section.scheduling.bridge"><< Prev</A></TD><TD><A href="node46.html">- Up -</A></TD><TD><A href="node50.html#section.scheduling.strongser">Next >></A></TD></TR></TABLE><DIV id="section.scheduling.edgefinding"><H2><A name="section.scheduling.edgefinding">11.3 Strong Propagators for Capacity Constraints </A></H2><P>In this section we introduce the ideas for stronger propagation employed for capacity constraints in Oz. </P><P>First we show the weakness of the propagators we have introduced so far. We consider three tasks <IMG alt="A" src="latex98.png">, <IMG alt="B" src="latex39.png"> and <IMG alt="C" src="latex31.png">, each with duration 8 and with the domain <IMG alt="1\#10" src="latex294.png">. If we state for the pairs <IMG alt="(A,B)" src="latex295.png">, <IMG alt="(A,C)" src="latex296.png"> and <IMG alt="(B,C)" src="latex297.png"> that the contained tasks must not overlap in time by using reified constraints or by applying <CODE>Schedule<SPAN class="keyword">.</SPAN>serializedDisj</CODE>, no further propagation will take place. This is due to the local reasoning on task pairs. For each pair no value in the corresponding domains can be discarded. On the other hand, the tasks must be scheduled between time point 1 and 18 (the latest completion time of either <IMG alt="A" src="latex98.png">, <IMG alt="B" src="latex39.png"> or <IMG alt="C" src="latex31.png">). But because the overall duration is 24, this is impossible. </P><P>Hence, we will use stronger propagators reasoning simultaneously on the whole set of tasks on a resource. The principal ideas behind this reasoning are simple but very powerful. First, for an arbitrary set of tasks <IMG alt="S" src="latex7.png"> to be scheduled on the same resource, the available time must be sufficient (see the example above). Furthermore, we check whether a task <IMG alt="T" src="latex101.png"> in math/S/ must be scheduled as the first or last task of <IMG alt="S" src="latex7.png"> (and analogously if <IMG alt="T" src="latex101.png"> is not in <IMG alt="S" src="latex7.png">). </P><P>We introduce the following abbreviations for a task <IMG alt="T" src="latex101.png">. </P><TABLE align="center" class="dyptic"><TR valign="top"><TD><P><IMG alt="\Est{T}" src="latex298.png"></P></TD><TD><P>least possible start time for <IMG alt="T" src="latex101.png"></P></TD></TR><TR valign="top"><TD><P><IMG alt="\Lst{T}" src="latex299.png"> </P></TD><TD><P>largest possible start time for <IMG alt="T" src="latex101.png"></P></TD></TR><TR valign="top"><TD><P><IMG alt="\Ect{T}" src="latex300.png"> </P></TD><TD><P>earliest completion time for <IMG alt="T" src="latex101.png">, i. e. <IMG alt="\Ect{T} = \Est{T} + \Dur{T}" src="latex301.png"></P></TD></TR><TR valign="top"><TD><P><IMG alt="\Lct{T}" src="latex302.png"> </P></TD><TD><P>latest possible completion time for <IMG alt="T" src="latex101.png">, i. e., <IMG alt="\Lct{T} =\Lst{T} + \Dur{T}" src="latex303.png"></P></TD></TR></TABLE><P> </P><P>For a set <IMG alt="S" src="latex7.png"> of tasks we define </P><TABLE align="center" class="dyptic"><TR valign="top"><TD><P><IMG alt="\Est{S} = \min(\{\Est{T}|\ T \in S\})" src="latex304.png"></P></TD></TR><TR valign="top"><TD><P><IMG alt="\Lct{S} = \max(\{\Lct{T}|\ T \in S\})" src="latex305.png"></P></TD></TR><TR valign="top"><TD><P><IMG alt="\Dur{S} = \sum\limits_{T \in S} \Dur{T}" src="latex306.png"></P></TD></TR></TABLE><P></P><P></P><P>If the condition </P><BLOCKQUOTE><P><IMG alt="\Lct{S} - \Est{S} > \Dur{S}" src="latex307.png"></P></BLOCKQUOTE><P> holds, no schedule of the tasks in <IMG alt="S" src="latex7.png"> can exist. A strong propagator for capacity constraints fails in this case. </P><P>Now we introduce some domain reductions by considering a task <IMG alt="T" src="latex101.png"> and a set of tasks <IMG alt="S" src="latex7.png"> where <IMG alt="T" src="latex101.png"> does not occur in <IMG alt="S" src="latex7.png">. Assume that we can show that <IMG alt="T" src="latex101.png"> cannot be scheduled after all tasks in <IMG alt="S" src="latex7.png"> and that <IMG alt="T" src="latex101.png"> canot be scheduled between two tasks in <IMG alt="S" src="latex7.png"> (if <IMG alt="S" src="latex7.png"> contains at least two tasks). In this case we can conclude that <IMG alt="T" src="latex101.png"> must be scheduled before all tasks in <IMG alt="S" src="latex7.png">. </P><P>More formally, if </P><BLOCKQUOTE><P><IMG alt="\Lct{S} - \Est{S} < \Dur{S} + \Dur{T}" src="latex308.png"></P></BLOCKQUOTE><P> holds, <IMG alt="T" src="latex101.png"> cannot be scheduled between <IMG alt="\Lct{S}" src="latex309.png"> and <IMG alt="\Est{S}" src="latex310.png"> (it cannot be scheduled between two tasks of <IMG alt="S" src="latex7.png"> if <IMG alt="S" src="latex7.png"> contains at least two tasks). If </P><BLOCKQUOTE><P><IMG alt="\Lct{T} - \Est{S} < \Dur{S} + \Dur{T}" src="latex311.png"></P></BLOCKQUOTE><P> holds, <IMG alt="T" src="latex101.png"> cannot be scheduled after all tasks in <IMG alt="S" src="latex7.png">. Hence, if both conditions hold, <IMG alt="T" src="latex101.png"> must be scheduled before all tasks of <IMG alt="S" src="latex7.png"> and corresponding propagators can be imposed, narrowing the domains of variables. </P><P>Analogously, if </P><BLOCKQUOTE><P><IMG alt="\Lct{S} - \Est{S} < \Dur{S}+ \Dur{T}" src="latex312.png"></P></BLOCKQUOTE><P> and </P><BLOCKQUOTE><P><IMG alt="\Lct{S} - \Est{T} < \Dur{S}+ \Dur{T}" src="latex313.png"></P></BLOCKQUOTE><P> holds, <IMG alt="T" src="latex101.png"> must be last. </P><DIV class="apropos"><P class="margin">edge-finding</P><P> Similar rules can be formulated if <IMG alt="T" src="latex101.png"> is contained in <IMG alt="S" src="latex7.png">. For this kind of reasoning, the term <A name="label152"></A><EM>edge-finding</EM> was coined in <A href="bib.html#applegate.91">[AC91]</A>. There are several variations of this idea in <A href="bib.html#carlier.89">[CP89]</A>, <A href="bib.html#applegate.91">[AC91]</A>, <A href="bib.html#carlier.94">[CP94]</A>, <A href="bib.html#martin.96">[MS96]</A> for the Operations Research community and in <A href="bib.html#nuijten.94">[Nui94]</A>, <A href="bib.html#caseau.94a">[CL94]</A>, <A href="bib.html#baptiste.95a">[BLN95]</A>, <A href="bib.html#wuertz.96b">[Wür96]</A> for the constraint programming community; they differ in the amount of propagation and which sets <IMG alt="S" src="latex7.png"> are considered for edge-finding. The resulting propagators do a lot of propagation, but are also more expensive than e.g. reified constraints. Depending on the problem, one has to choose an appropriate propagator. </P></DIV><P> For unary resources Oz provides two propagators employing edge-finding to implement capacity constraints. The propagator <CODE>Schedule<SPAN class="keyword">.</SPAN>serialize</CODE> is an improved version of an algorithm described in <A href="bib.html#martin.96">[MS96]</A>. A single propagation step has complexity <IMG alt="O(n^2)" src="latex314.png"> where <IMG alt="n" src="latex43.png"> is the number of tasks the propagator is reasoning on, i. e. the number of tasks on the resource considered by the propagator. Because the propagator runs until propagation reaches a fixed-point, we have the overall complexity of <IMG alt="O(k \cdot n^3)" src="latex315.png"> when <IMG alt="k" src="latex114.png"> is the size of the largest domain of a task's start time (at most <IMG alt="k \cdot n" src="latex316.png"> values can be deleted from the domains of task variables). </P><P>The propagator <CODE>Schedule<SPAN class="keyword">.</SPAN>taskIntervals</CODE> provides weaker propagation than described in <A href="bib.html#caseau.94a">[CL94]</A> but provides stronger propagation than <CODE>Schedule<SPAN class="keyword">.</SPAN>serialize</CODE>. While a single propagation step has complexity <IMG alt="O(n^3)" src="latex317.png">, the overall complexity is <IMG alt="O(k \cdot n^4)" src="latex318.png">. </P><P>Now we can solve the bridge construction problem with a propagator using edge-finding. By the statement </P><DL class="anonymous"><DD class="code"><CODE>{ExploreBest {Compile Bridge <BR> Schedule<SPAN class="keyword">.</SPAN>serialized<BR> DistributeSorted} <BR> Earlier}</CODE></DD></DL><P> we compute the optimal solution in a full search tree with 508 choice nodes instead of 1268 as in the section before. </P><DIV class="apropos"><P class="margin">proof of optimality</P><P> The improvement by strong propagation becomes even more dramatic if we constrain the bridge problem further by stating that the makespan must be strictly smaller than 104. Since we know that 104 is the optimal solution we, thus, prove optimality of this makespan. The modified problem specification is </P><DL class="anonymous"><DD class="code"><CODE>OptBridge = {AdjoinAt Bridge constraints<BR> <SPAN class="keyword">proc</SPAN><SPAN class="variablename"> </SPAN>{<SPAN class="functionname">$</SPAN> Start Dur}<BR> {Bridge<SPAN class="keyword">.</SPAN>constraints Start Dur}<BR> Start<SPAN class="keyword">.</SPAN>pe <SPAN class="keyword"><:</SPAN> 104<BR> <SPAN class="keyword">end</SPAN>}</CODE></DD></DL><P> </P></DIV><P>Solving the modified problem with the simple propagator by </P><DL class="anonymous"><DD class="code"><CODE>{ExploreBest {Compile OptBridge <BR> Schedule<SPAN class="keyword">.</SPAN>serializedDisj<BR> DistributeSorted} <BR> Earlier}</CODE></DD></DL><P> we obtain a search tree with 342 choice nodes. Using the edge-finding propagator <CODE>Schedule<SPAN class="keyword">.</SPAN>serialized</CODE> instead we obtain a search tree with only 22 choice nodes. By using <CODE>Schedule<SPAN class="keyword">.</SPAN>taskIntervals</CODE> the search tree shrinks further to the size of 17 choice nodes. </P><P>Note that for the proof of optimality the domains of the start times are rather narrow. If we start with an unconstrained problem, the domains are rather wide. But if the domains are more narrow compared to the durations of the tasks, the conditions we have described above are more likely to become true and propagation may take place. This is the reason why edge-finding turns out to be a stronger improvement for the proof of optimality. </P></DIV><TABLE align="center" border="0" cellpadding="6" cellspacing="6" class="nav"><TR bgcolor="#DDDDDD"><TD><A href="node48.html#section.scheduling.bridge"><< Prev</A></TD><TD><A href="node46.html">- Up -</A></TD><TD><A href="node50.html#section.scheduling.strongser">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 (20110908185330)</SPAN></ADDRESS></BODY></HTML>
|