<!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
<HTML><HEAD><TITLE>8.2 Example: Aligning for a Photo</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="node36.html#section.reified.started"><< Prev</A></TD><TD><A href="node35.html">- Up -</A></TD><TD><A href="node38.html#section.reified.srat">Next >></A></TD></TR></TABLE><DIV id="section.reified.photo"><H2><A name="section.reified.photo">8.2 Example: Aligning for a Photo</A></H2><P>We will now see an overconstrained problem for which it is impossible to satisfy all constraints. The problem specification will distinguish between primary and secondary constraints, and the goal is to find a solution that satisfies all primary constraints and as many of the secondary constraints as possible. </P><DIV class="unnumbered"><H3><A name="label101">Problem Specification</A></H3><P>Betty, Chris, Donald, Fred, Gary, Mary, and Paul want to align in one row for taking a photo. Some of them have preferences next to whom they want to stand: </P><OL type="1"><LI><P>Betty wants to stand next to Gary and Mary.</P></LI><LI><P>Chris wants to stand next to Betty and Gary.</P></LI><LI><P>Fred wants to stand next to Mary and Donald.</P></LI><LI><P>Paul wants to stand next to Fred and Donald.</P></LI></OL><P> Obviously, it is impossible to satisfy all preferences. Can you find an alignment that maximizes the number of satisfied preferences? </P></DIV><DIV class="unnumbered"><H3><A name="label102">Model</A></H3><P>The model has a variable <IMG alt="A_p" src="latex182.png"> for every person, where <IMG alt="A_p" src="latex182.png"> stands for the position <IMG alt="p" src="latex183.png"> takes in the alignment. Since there are exactly 7 persons, we have <IMG alt="A_p\in 1\#7" src="latex184.png"> for every person <IMG alt="p" src="latex183.png">. Moreover, we have <IMG alt="A_p\neq A_q" src="latex185.png"> for every pair <IMG alt="p" src="latex183.png">,<IMG alt="q" src="latex186.png"> of distinct persons. The model has a variable <IMG alt="S_i\in0\#1" src="latex187.png"> for each of the 8 preferences, where <IMG alt="S_i=1" src="latex188.png"> if and only if the <IMG alt="i" src="latex115.png">-th preference is satisfied. To express this constraint, we constrain the control variable <IMG alt="S" src="latex7.png"> of a preference ``person <IMG alt="p" src="latex183.png"> wants to stand next to person <IMG alt="q" src="latex186.png">'' by means of the reified constraint </P><BLOCKQUOTE><P><IMG alt="(|A_p-A_q|=1
\;\leftrightarrow\;
S=1)
\;\land\;
S\in0\#1" src="latex189.png"></P></BLOCKQUOTE><P> </P><P>Finally, there is a variable </P><BLOCKQUOTE><P><IMG alt="{\it Satisfaction} \;=\; S_1\;+\;\ldots\;+\;S_8" src="latex190.png"></P></BLOCKQUOTE><P> denoting the number of satisfied preferences. We want to find a solution that maximizes the value of <IMG alt="{\it Satisfaction}" src="latex191.png">. </P><P>The experienced constraint programmer will note that we can eliminate a symmetry by picking two persons <IMG alt="p" src="latex183.png"> and <IMG alt="q" src="latex186.png"> and imposing the order constraint <IMG alt="A_p<A_q" src="latex192.png">. </P></DIV><DIV class="unnumbered"><H3><A name="label103">Distribution Strategy.</A></H3><P>To maximize <IMG alt="{\it Satisfaction}" src="latex191.png">, we employ a two-dimensional distribution strategy, which first distributes on <IMG alt="{\it Satisfaction}" src="latex191.png">, trying the values <IMG alt="8,\,7,\,\ldots\,1" src="latex193.png"> in this order. Once <IMG alt="{\it Satisfaction}" src="latex191.png"> is determined, we distribute on the variables <IMG alt="A_p" src="latex182.png"> using a first-fail strategy that splits the domain of the selected variable.</P></DIV><DIV class="unnumbered"><H3><A name="label104">Script.</A></H3><P></P><DIV id="progphoto"><HR><P><A name="progphoto"></A></P><DL class="anonymous"><DD class="code"><CODE><SPAN class="keyword">proc</SPAN><SPAN class="variablename"> </SPAN>{<SPAN class="functionname">Photo</SPAN> Root}<BR> Persons = [betty chris donald fred gary mary paul]<BR> Preferences = [betty<SPAN class="keyword">#</SPAN>gary betty<SPAN class="keyword">#</SPAN>mary chris<SPAN class="keyword">#</SPAN>betty chris<SPAN class="keyword">#</SPAN>gary<BR> fred<SPAN class="keyword">#</SPAN>mary fred<SPAN class="keyword">#</SPAN>donald paul<SPAN class="keyword">#</SPAN>fred paul<SPAN class="keyword">#</SPAN>donald]<BR> NbPersons = {Length Persons}<BR> Alignment = {FD<SPAN class="keyword">.</SPAN>record alignment Persons 1<SPAN class="keyword">#</SPAN>NbPersons}<BR> Satisfaction = {FD<SPAN class="keyword">.</SPAN>decl} <BR> <SPAN class="keyword">proc</SPAN><SPAN class="variablename"> </SPAN>{<SPAN class="functionname">Satisfied</SPAN> P<SPAN class="keyword">#</SPAN>Q S}<BR> {FD<SPAN class="keyword">.</SPAN>reified<SPAN class="keyword">.</SPAN>distance Alignment<SPAN class="keyword">.</SPAN>P Alignment<SPAN class="keyword">.</SPAN>Q <SPAN class="string">'=:'</SPAN> 1 S}<BR> <SPAN class="keyword">end</SPAN> <BR><SPAN class="keyword">in</SPAN> <BR> Root = r(satisfaction: Satisfaction<BR> alignment: Alignment)<BR> {FD<SPAN class="keyword">.</SPAN>distinct Alignment}<BR> {FD<SPAN class="keyword">.</SPAN>sum {Map Preferences Satisfied} <SPAN class="string">'=:'</SPAN> Satisfaction}<BR> Alignment<SPAN class="keyword">.</SPAN>fred <SPAN class="keyword"><:</SPAN> Alignment<SPAN class="keyword">.</SPAN>betty % <SPAN class="comment">breaking symmetries<BR></SPAN> {FD<SPAN class="keyword">.</SPAN>distribute generic(order:naive value:max) [Satisfaction]}<BR> {FD<SPAN class="keyword">.</SPAN>distribute split Alignment}<BR><SPAN class="keyword">end</SPAN></CODE></DD></DL><P class="caption"><STRONG>Figure 8.1:</STRONG> A script for the Photo Puzzle.</P><HR></DIV><P> </P><P>The script in <A href="node37.html#progphoto">Figure 8.1</A> constrains its root variable to a record consisting of the number of satisfied preferences and a record mapping the names of the persons to their positions in the alignment. The fields of the record <CODE>Alignment</CODE> implement the variables <IMG alt="A_p" src="latex182.png"> of the model. </P><P class="margin"><CODE>Satisfied</CODE></P><P> The script introduces the defined constraint <CODE>{Satisfied P<SPAN class="keyword">#</SPAN>Q S}</CODE>, which implements the reification of the constraint ``<CODE>P</CODE> stands next to <CODE>Q</CODE>'' with respect to <CODE>S</CODE>. </P><P>The statement </P><BLOCKQUOTE class="code"><CODE>{FD<SPAN class="keyword">.</SPAN>sum {Map Preferences Satisfied} <SPAN class="string">'=:'</SPAN> Satisfaction}</CODE></BLOCKQUOTE><P> constrains the variable <CODE>Satisfaction</CODE> to the number of satisfied preferences. </P><P id="page.reified.photosol">The statement <CODE>{ExploreOne Photo}</CODE> will run the script until a first solution is found. The first solution satisfies 6 preferences and looks as follows: </P><BLOCKQUOTE class="code"><CODE>6 <SPAN class="keyword">#</SPAN> alignment(betty:5 chris:6 donald:1 fred:3 <BR> gary:7 mary:4 paul:2)</CODE></BLOCKQUOTE><P> By construction of the script, this is the maximal number of preferences that can be satisfied simultaneously. </P></DIV><DIV class="unnumbered"><H3><A name="label105">Exercises</A></H3><DIV class="exercise" id="reified.ex.c"><P><B>Exercise 8.3</B> (<A href="answers.html#label186">See solution</A>)</P><BLOCKQUOTE><P>Modify the script such that the first solution minimizes the number of preferences satisfied.</P></BLOCKQUOTE></DIV></DIV></DIV><TABLE align="center" border="0" cellpadding="6" cellspacing="6" class="nav"><TR bgcolor="#DDDDDD"><TD><A href="node36.html#section.reified.started"><< Prev</A></TD><TD><A href="node35.html">- Up -</A></TD><TD><A href="node38.html#section.reified.srat">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
>
1211
