The Steiner Problem

Problem Specification

The ternary Steiner problem of order n asks for n(n - 1)/6 sets s_i $\subset$ {1,..., n} with cardinality 3 such that every two of them share at most one element. The mathematical properties of the problem require that n mod 6 has to be either 1 or 3 [11].

Viewpoint and Constraints

We create a list ss of n( n - 1 ) / 6 set variables and constrain every set to have a cardinality of 3 and to have an upper bound of {1,...,n}. Further we require that the cardinality of the intersubsection of every two distinct sets in ss must not exceed 1.

Branching Strategy

Branching simply takes the sets as they occur in ss and adds resp. removes elements from them starting from the smallest element.

Script

First, the list ss is created and its elements' upper bounds and cardinalities are appropriately constrained. The procedure intersect ensures that every two sets share at most one element by stating that the cardinality of the intersubsection of two sets is in {0,1}. Branching is straightforward and uses the provided library procedure setvarbranch.

exception FalseInput;

fun steiner n space  = 
   if ((n mod 6) = 1) orelse ((n mod 6) = 3)
   then
    let 
       val n' = (n *(n - 1)) div 6
       val ss = List.tabulate(n',(fn x => 
                  FS.upperBound(space,#[(1,n)])))
       fun intersect(space,[y])= ()
         | intersect(space,y::ys)= (List.app(fn x =>
              let 
                 val tmp = FS.setvar space
              in       
                (FS.relOp(space,y,FS.INTER,x,FS.SEQ,tmp);
                 FS.cardRange(space,0,1,tmp))
             end)
                (ys);intersect(space,ys))
    in
       List.app(fn x => FS.cardRange(space,3,3,x))ss;
       intersect(space,ss);
       FS.setvarbranch(space,Vector.fromList ss,
                             FS.FSB_NONE,FS.FSB_MIN);    
       ss
    end
    else                 
     raise FalseInput

Solving the Steiner problem of order 9 by invoking the Alice Explorer

Explorer.exploreOne(Steiner 9)

yields as solution

{ss = [setvar{| < 1..3 > (3)|}, setvar{| < 1, 4..5 > (3)|}, setvar{| < 1, 6..7 > (3)|},
setvar{| < 1, 8..9 > (3)|}, setvar{| < 2, 4, 6 > (3)|}, setvar{| < 2, 5, 8 > (3)|},
setvar{| < 2, 7, 9 > (3)|}, setvar{| < 3..4, 9 > (3)|}, setvar{| < 3, 5, 7 > (3)|},
setvar{| < 3, 6, 8 > (3)|}, setvar{| < 4, 7..8 > (3)|}, setvar{| < 5..6, 9 > (3)|}]}

The search tree has 4529 choice nodes, and 4505 failure nodes.

Figure 13: Search tree of the Steiner Problem

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 (n + 1). A set with three elements { x₁, x₂, x₃} can be mapped to an integer by (n + 1)²*x₁ + (n + 1)²*x₂ + x₃.

Extending the Solver

The finite set library provides FS.match to match the elements of a set s with a fixed number of elements to a vector of size # s 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 3 finite domains per list. Finally the order between adjacent sets is imposed by

N1 * N1 * y₁ + N1 * y₂ + y₃ < N1 * N1 * x₁ + N1 * x₂ + x₃.

let 
    val n1 = n + 1
    val n1n1 = n1 * n1
    val ivarlist = List.map(fn x => 
    let 
       val tmp = FD.rangeVec(space,3,(1,n))
     in
       (FS.match(space,x,tmp);Vector.toList tmp)
    end)(ss)
    fun redundantconstr(s,[y]) = ()
      | redundantconstr(space,y as [y1,y2,y3]::ys)= 
             (List.map(fn x as [x1,x2,x3] =>
                 post(space,`n1n1 `* FD(y1) `+ `n1 `* FD(y2) `+
                            FD(y3) `< `n1n1 `* FD(x1) `+ `n1 `* 
                            FD(x2) `+ FD(x3),FD.DOM))(ys);
              redundantconstr(space,ys))       
 in
    redundantconstr(space,ivarlist)
end;

This code is to be inserted right before the branching. Solving the Steiner problem of order 9 results in the following search tree.

Figure 14: Search tree of the optimized Script for the Steiner Problem

We see that the number of choice nodes decreases from 4529 to 419 and the number of failure nodes decreases from 4505 to 359.