5.8. Breaking symmetries with SymmetryBreakers

Now that we have seen the Decision and DecisionVisitor classes in details and that we are trying to solve the n-Queens Problem, how could we resist to introduce SymmetryBreakers?

Breaking symmetries of a model or a problem is a very effective technique to reduce the size of the search tree and, most of the time, it also permits to reduce - sometimes spectacularly - the search time.

We have already seen this effectiveness when we introduced a constraint to avoid mirror Golomb rulers in section Breaking symmetries with constraints.

This time, we will use SymmetryBreakers. As their name implies, their role is to break symmetries. In contrast to explicitly adding symmetry breaking constraints in the model before the solving process, SymmetryBreakers add them automatically when required during the search, i.e. on the fly.

5.8.1. The basic idea

The basic idea is quite simple. Consider again the 4-Queens Problem. The following figures represent two symmetric solutions.

These two solutions are symmetric along a vertical axis dividing the square in two equal parts. If we have (or ) during the search, we know that we don’t have to test a solution with (or ) as every solution with () has an equivalent symmetric solution with ().

You can tell the CP solver not to visit the branch if during the search we already have tried to set . To do this, we use a SymmetryManager and a SymmetryBreaker. The SymmetryManager collects SymmetryBreakers for a given problem. During the search, each Decision is visited by all the SymmetryBreakers. If there is a match between the Decision and a SymmetryBreaker, the SymmetryManager will, upon refutation of that Decision issue a Constraint to forbid the symmetrical exploration of the search tree. As you might have guessed, SymmetryManagers are SearchMonitors and SymmetryBreakers are DecisionVisitors.

5.8.2. SymmetryBreakers

1. C++ code:
   1. nqueens7.cc

Let’s create a SymmetryBreaker for the vertical axial symmetry. Because the square has lots of symmetries, we introduce a helper method to find the symmetric indices of the variables and the symmetric values for a given variable:

int symmetric(int index) const { return size_ - 1 - index}

where size_ denotes the number of variables and the range of possible values () in our model.

The next figure illustrates the returned indices by the symmetric() method.

The indices returned by the symmetric() method.

We also use two methods to do the translation between the indices and the variables. Given an IntVar * var, Index(var) returns the index of the variable corresponding to var:

int Index(IntVar* const var) const {
  return FindWithDefault(indices_, var, -1);
}

FindWithDefault() is defined in the header constraint_solver/constraint_solveri.h. Given an std::map<IntVar*, int> like indices_, it returns the corresponding int if it finds the IntVar *. If it doesn’t find the IntVar *, it returns the default argument given, in this case.

To do the converse translation, we use the Var() method:

IntVar* Var(int index) const {
  return vars_[index];
}

where vars_ is the private std::vector<IntVar*> with the variables of our model.

We create a base SymmetryBreaker for the n-Queens Problem:

class NQueenSymmetry : public SymmetryBreaker {
 public:
  NQueenSymmetry(Solver* const s, const std::vector<IntVar*>& vars)
      : solver_(s), vars_(vars), size_(vars.size()) {
    for (int i = 0; i < size_; ++i) {
      indices_[vars[i]] = i;
    }
  }
  virtual ~NQueenSymmetry() {}

 protected:
  int Index(IntVar* const var) const {
    return FindWithDefault(indices_, var, -1);
  }
  IntVar* Var(int index) const {
    return vars_[index];
  }
  int size() const { return size_; }
  int symmetric(int index) const { return size_ - 1 - index; }
  Solver* const solver() const { return solver_; }

 private:
  Solver* const solver_;
  const std::vector<IntVar*> vars_;
  std::map<IntVar*, int> indices_;
  const int size_;
};

Now, we can specialize it for each symmetry we want to break.

How do we tell a SymmetryBreaker to notify the SymmetryManager to add a corresponding constraint upon refutation of a given Decision? For the n-Queens Problem, we can use the AddIntegerVariableEqualValueClause() method of the SymmetryBreaker class. Given the assignation of a value to an IntVar, give this method the corresponding symmetric assignation. We call this corresponding assignment a clause. This clause only makes sense if the Decision assigns a value to an IntVar and this is why we declare the corresponding clause only in the VisitSetVariableValue() method of the SymmetryBreaker. All this might sound complicated but it is not:

//  Vertical axis symmetry
class SY : public NQueenSymmetry {
 public:
  SY(Solver* const s, const std::vector<IntVar*>& vars) :
                                          NQueenSymmetry(s, vars) {}
  virtual ~SY() {}

  virtual void VisitSetVariableValue(IntVar* const var, int64 value) {
    const int index = Index(var);
    IntVar* const other_var = Var(symmetric(index));
    AddIntegerVariableEqualValueClause(other_var, value);
  }
};

Given an IntVar* var that will be given the value value by a Decision during the search, we ask the SymmetryManager to avoid the possibility that the variable other_var could be assigned the same value value upon refutation of this Decision. This means that the other_var variable will never be equal to value in the opposite branch of the search tree where var is different than value. In this manner, we avoid searching a symmetrical part of the search tree we have “already” explored.

What happens if another type of Decisions are returned by the DecisionBuilder during the search? Nothing. The refutation of the clause will only be applied if a Decision triggers a VisitSetVariableValue() callback.

The SymmetryBreaker class defines two other clauses:

• AddIntegerVariableGreaterOrEqualValueClause(IntVar* const var, int64 value) and
• AddIntegerVariableLessOrEqualValueClause(IntVar* const var, int64 value).

Their names are quite explicit and tell you what their purpose is. These methods would fit perfectly within a VisitSplitVariableDomain() call for instance.

5.8.3. The SymmetryManager

Because the n-Queens Problem is defined on a square, we have a lots of symmetries we can avoid:

• Vertical axis symmetry: we already defined the SY class;
• Horizontal axis symmetry: class SX;
• First diagonal symmetry: class SD1;
• Second diagonal symmetry: class SD2;
• 1/4 turn rotation symmetry: class R90;
• 1/2 turn rotation symmetry: class R180;
• 3/4 turn rotation symmetry: class R270.

We store the corresponding SymmetryBreaker objects in an std::vector<SymmetryBreaker*>:

std::vector<SymmetryBreaker*> breakers;
NQueenSymmetry* const sy = s.RevAlloc(new SY(&s, queens));
breakers.push_back(sy);
NQueenSymmetry* const sx = s.RevAlloc(new SX(&s, queens));
breakers.push_back(sx);
NQueenSymmetry* const sd1 = s.RevAlloc(new SD1(&s, queens));
breakers.push_back(sd1);
NQueenSymmetry* const sd2 = s.RevAlloc(new SD2(&s, queens));
breakers.push_back(sd2);
NQueenSymmetry* const r90 = s.RevAlloc(new R90(&s, queens));
breakers.push_back(r90);
NQueenSymmetry* const r180 = s.RevAlloc(new R180(&s, queens));
breakers.push_back(r180);
NQueenSymmetry* const r270 = s.RevAlloc(new R270(&s, queens));
breakers.push_back(r270);

We then create a SymmetryManager:

SearchMonitor* const symmetry_manager = s.MakeSymmetryManager(breakers);

and add this SearchMonitor to the other SearchMonitors:

std::vector<SearchMonitor*> monitors;
...
monitors.push_back(symmetry_manager);
...
DecisionBuilder* const db = s.MakePhase(...);
...
s.Solve(db, monitors);

These seven SymmetryBreakers are enough to avoid duplicate solutions in the search, i.e. they force the solver to find only unique solutions up to a symmetry.

5.8.4. Results

Let’s compare[1] some statistics of this algorithm with our best try from previous section:

	Statistics	Second try	With SymmetryBreakers
7	Failures	92	24
	Branches	82	44
8	Failures	328	71
	Branches	654	139
9	Failures	1216	272
	Branches	2430	541
10	Failures	4500	1074
	Branches	8998	2142
11	Failures	17847	4845
	Branches	35692	9686
12	Failures	86102	23159
	Branches	172202	46312

Of course, the comparison is a little biased as in the case of the SymmetryBreakers we don’t try to count or reproduce all the solutions. We are only looking at unique solution up to a symmetry. With a little bit more work, you could retrieve all the solutions and the work to do so is minimal compared to the traversal of the search tree. So our method would still be efficient.

Footnote

[1]	Don’t forget to use the use_symmetry flag!