15. Photo alignment

This chapter shows how to use reified constraints for solving an overconstrained problem.

15.1. Problem

Betty, Chris, Donald, Fred, Gary, Mary, Paul, Peter, and Susan want to align in a row for taking a photo. They have the following preferences:

  1. Betty wants to stand next to Donald, Gary, and Peter.

  2. Chris wants to stand next to Gary and Susan.

  3. Donald wants to stand next to Fred and Gary.

  4. Fred wants to stand next to Betty and Gary.

  5. Gary wants to stand next to Mary and Betty.

  6. Mary wants to stand next to Betty and Susan.

  7. Paul wants to stand next to Donald and Peter.

  8. Peter wants to stand next to Susan and Paul.

These preferences are obviously not satisfiable all at once (e.g., Betty cannot possibly stand next to three people at once). The problem is overconstrained. To solve an overconstrained problem, we turn it into an optimization problem: The task is to find an alignment that violates as few preferences as possible.

15.2. Model

We model the photo alignment as an array of integer variables pos such that pos[p] represents the position of person p in the final left-to-right order. The outline of a script for this problem is shown in A script for the photo alignment problem .

The cost() function as required by the class MinimizeScript (see Scripts ) just returns the number of violations.

Program 15.1 A script for the photo alignment problem
...
enum {
  Betty, Chris, Donald, Fred, Gary,
  Mary, Paul, Peter, Susan
};
const int n = 9;
const int n_prefs = 17;
int spec[n_prefs][2] = {
  {Betty,Donald}, {Betty,Gary}, {Betty,Peter},
  {Chris,Gary}, {Chris,Susan},
  {Donald,Fred}, {Donald,Gary},
  {Fred,Betty}, {Fred,Gary},
  {Gary,Mary}, {Gary,Betty},
  {Mary,Betty}, {Mary,Susan},
  {Paul,Donald}, {Paul,Peter},
  {Peter,Susan}, {Peter,Paul}
};

class Photo : public IntMinimizeScript {
  IntVarArray pos;
  IntVar      violations;
public:
  Photo(const Options& opt)
    : IntMinimizeScript(opt),
      pos(*this,n,0,n-1), violations(*this,0,n_prefs) {
    // [photo:constrain positions]
    // [photo:compute violations]
    // [photo:symmetry breaking]
    ...
  }
  virtual IntVar cost(void) const {
    return violations;
  }  
  ...
};
...

Download: photo.cpp

There are only two hard constraints for this model: no person can be in more than one place, and no two persons can stand in the same place. The first constraint is enforced automatically by the choice of variables, as each pos variable represents the unique position of a person (see also Choose variables to avoid constraints ). For the second constraint, the variables in the pos array must be pairwise distinct (see Distinct constraints ):

    distinct(*this, pos, IPL_BND);

We choose the bounds consistent variant of distinct (by giving the extra argument IPL_BND, see Selecting the propagation level ) as also the other propagators perform only bounds reasoning.

The remaining constraints implement the preferences and turn them into a measure of violation, which expresses how many preferences are not fulfilled in a solution. A preference \((i,j)\) is not fulfilled if the distance between the positions of person \(i\) and person \(j\) is greater than one. This can be implemented using a linear constraint, an absolute value constraint, and a reified constraint for each preference, as well as one linear constraint that constrains the sum of the violations:

...
    BoolVarArgs viol(*this,n_prefs,0,1);
    for (int i=0; i<n_prefs; i++) {
      IntVar distance(*this,0,n), diff(*this,-n,n);
      linear(*this, {1,-1},
                    IntVarArgs({pos[spec[i][0]],pos[spec[i][1]]}),
             IRT_EQ, diff);
      abs(*this, diff, distance);
      rel(*this, distance, IRT_GR, 1, viol[i]);
    }
    linear(*this, viol, IRT_EQ, violations);
    ...

Download: photo-without-modeling-support.cpp

Using the MiniModel library (see Boolean expressions and Expressions and relations ) yields more compact and readable code:

    BoolVarArgs viol(n_prefs);
    for (int i=0; i<n_prefs; i++) {
      viol[i] = expr(*this, abs(pos[spec[i][0]]-pos[spec[i][1]]) > 1);
    }
    rel(*this, violations == sum(viol));

We can observe that this problem has a symmetry, as reversing a solution yields again a solution. Symmetric solutions like this can be ruled out by arbitrarily picking two persons, and always placing one somewhere to the left of the other. For example, let us always place Betty somewhere to the left of Chris:

    rel(*this, pos[Betty] < pos[Chris]);

15.3. More information

This case study is also available as a Gecode example, see photo .