Symmetry-breaking constraints
In the field of mathematics called combinatorial optimization, the method of symmetry-breaking constraints can be used to take advantage of symmetries in many constraint satisfaction and optimization problems, by adding constraints that eliminate symmetries and reduce the search space size.
Symmetries in a combinatorial problem increase the size of the search space and therefore, time is wasted in visiting new solutions which are symmetric to the already visited solutions. The solution time of a combinatorial problem can be reduced by adding new constraints, referred as symmetry breaking constraints, such that some of the symmetric solutions are eliminated from the search space while preserving the existence of at least one solution.[1][2]
Symmetry is common in many real-life combinatorial problems. For example, certain vehicles in the vehicle routing problem might be identical. For a valid routing plan, every permutation of such identical vehicles yields another valid routing plan with the same objective function value.
References
- ↑ "Published key research papers on Symmetry Breaking Constraints".
- ↑ Walsh, Toby (2006). "General symmetry breaking constraints". Principles and Practice of Constraint Programming-CP. Springer Berlin Heidelberg: 650–664. doi:10.1007/11889205_46.