<!-- ********************************************************************** -->

<Chapter id="fset.examples.steiner"> <Title/The Steiner Problem/

<Para><Title/Problem Specification/ The ternary Steiner problem of
order <Math>n</Math> asks for <Math>n(n-1)/6</Math> sets <Math>s_i
\subset \{1,\ldots,n\}</Math> with cardinality <Math>3</Math> such
that every two of them share at most one element. The mathematical
properties of the problem require that <Math>n \bmod 6</Math> has to be
either <Math>1</Math> or <Math>3</Math> <Ptr to="LindnerRosa:80">.


<Para><Title/Model/ We create a list <<Ss>> of <Math>n(n-1)/6</Math>
set variables and constrain every set to have a cardinality of
<Math>3</Math> and to have an upper bound of
<Math>\{1,\ldots,n\}</Math>. Further we require that the cardinality
of the intersection of every two distinct sets in <<Ss>> must not
exceed <Math>1</Math>.


<Para><Title/Distribution Strategy/ Distribution simply takes the
sets as they occur in <<Ss>> and adds &resp; removes elements from them
starting from the smallest element.

<Para><Title/Solver/ The solver is created by a function <<Steiner>>
that takes the order of the Steiner problem as argument and checks if
it is a valid order. In case it is valid it returns the actual solver
with the list of solution sets as formal argument.

<P>First, the list <<Ss>> is created and its elements' upper bounds and
cardinalities are appropriately constrained. The nested loops built
with <<ForAllTail>> and <<ForAll>> impose the constraint that every
two sets share at most one element by stating that the cardinality of
the intersection of two sets is in <Math>\{0,1\}</Math>.
Distribution is straightforward and uses the provided library
abstraction <<FS.distribute>> for naive distribution..

<Code.Extern display to="fset_steiner.oz" class=linenumbers>

<P>
Solving the Steiner problem of order <Math>9</Math> by invoking the Oz
Explorer <<<{ExploreOne {Steiner 9}}>>> yields as solution 

<<<[{1#3}#3 {1 4#5}#3 {1 6#7}#3 {1 8#9}#3 {2 4 6}#3 {2 5 8}#3 
  {2 7 9}#3 {3#4 9}#3 {3 5 7}#3 {3 6 8}#3 {4 7#8}#3 {5#6 9}#3].>>>

The search tree has depth <Math/50/, <Math/4545/ choice nodes, and
<Math/4521/ failure nodes.

<PICTURE.extern id="pic.fset_steiner_naive" display to="fset_steiner_naive.gif" type=GIF>

<Para><Title/Improving the Model/ A promising way to improve the
efficiency of a constraint model (where the corresponding problem does
not have a unique solution) is to break symmetries and thus to improve
constraint propagation. Breaking symmetries can be achieved by
imposing an order, in our case, an order on the set variables in
<<Ss>>. We can simply interpret every set as a number with three
digits to the base <Math>(n+1)</Math>. A set with three elements
<Math>\{x_1,x_2,x_3\}</Math> can be mapped to an integer by
<Math>(n+1)^2x_1+(n+1)x_2+x_3</Math>.

<Para><Title/Extending the Solver/ The finite set library provides
<<FS.int.match>> to match the elements of a set <Math>s</Math> with a
fixed number of elements to a vector of size <Math>\#s</Math> of finite
domain variables. This library constraint in conjunction with <<Map>>
is used to convert the list of sets <<Ss>> to a list of finite domain
lists with <Math>3</Math> finite domains per list. Finally the order
between adjacent sets is imposed by 
<<<N1N1*X1 + N1*X2 + X3 <: N1N1*Y1+ N1*Y2 + Y3>>> 
employing a <<ForAllTail>> loop.

<Code.Extern display to="fset_steiner_order.oz" class=linenumbers>

This code is to be inserted right before the distribution. Solving the
Steiner problem of order <Math>9</Math> results in the following
search tree.

<PICTURE.extern id="pic.fset_steiner_order" display to="fset_steiner_order.gif" type=GIF>

We see that the number of choice nodes decreases from <Math/4545/ to
<Math/565/ and the number of failure nodes decreases from <Math/4521/
to <Math/54/. This reduction of the search space gives us a speed-up
of about <Math>7</Math> and reduces the memory consumption by about
<Math>5.5</Math>.

</Chapter>

