10.1 Example: Aligning for a Photo, Revisited

In Section 8.2 we have searched for a solution of the alignment problem which satisfies the maximal number of preferences. To this aim we have introduced a variable which counts the number of satisfied preferences. By distributing this variable with its maximal value first, we have guaranteed that the first solution found is indeed the optimal one.

In this section we replace this ad-hoc approach by branch and bound. We first restate the script for the problem by omitting the distribution code for the variable summing up the satisfied preferences. The resulting script is shown in Figure 10.1.

proc {RevisedPhoto Root}
   Persons       = [betty chris donald fred gary mary paul]
   Preferences   = [betty#gary betty#mary  chris#betty chris#gary
                    fred#mary  fred#donald paul#fred   paul#donald]
   NbPersons     = {Length Persons}
   Alignment     = {FD.record alignment Persons 1#NbPersons}
   Satisfaction  = {FD.decl}  
   proc {Satisfied P#Q S}
      {FD.reified.distance Alignment.P Alignment.Q '=:' 1 S}
   end 
in 
   Root = r(satisfaction: Satisfaction
            alignment:    Alignment)
   {FD. distinct Alignment}
   {FD.sum {Map Preferences Satisfied} '=:' Satisfaction}
   Alignment.fred <: Alignment.betty     % breaking symmetries
   {FD.distribute split Alignment}
end

Figure 10.1: The revised script for the Photo Puzzle.

Next we define an ordering procedure which states that the overall sum of satisfied preferences in an alternative solution must be strictly greater than the corresponding sum in a previous solution:

proc {PhotoOrder Old New}
   Old.satisfaction <: New.satisfaction
end

The optimal solution can be found with the statement

{ExploreBest RevisedPhoto PhotoOrder}

We obtain the same solution as in *. But now only 141 choice nodes are needed to find the optimal solution whereas 219 choice nodes were needed in Section 8.2. Furthermore, branch and bound allows us to prove in an efficient way that the last solution found is really the optimal one. The full search tree (including the proof of optimality) contains 169 choice nodes; still less than for the search for the best solution with the ad-hoc method. If we inspect the solutions, we observe that the first solution satisfies only a single preference. By imposition of the ordering procedure by the search engine, the next found solution must satisfy more preferences. Indeed, the second solution satisfies two preferences. Following this approach we finally arrive at the optimal solution with six satisfied preferences.