| Pattern name |
ReflectionSymmetry. |
| Context | A array of decision variables which can be reversed. |
| Problem |
This symmetry doubles the size of the search space and the number of
solutions. |
| Forces |
Failing to eliminate this increases search. Eliminating symmetry may conflict with the branching heuristic. |
| Solution |
Post constraints ordering first and last variables. If they cannot be equal, make this a strict ordering constraint. |
| Example |
Car sequencing problem,
prob001 in
CSPLib. |
| References |
Succeed-first or Fail-first: A Case Study in Variable and Value Ordering
Heuristics
(ps, abstract) Barbara Smith, School of Computing Research Report 96.26, University of Leeds, September 1996. Presented at the ILOG Solver and ILOG Schedule 2nd International Users' Conference, Paris, July 1996. Also in the Proceedings of PACT'97, pp. 321-330.
|