In the field of mathematics called
combinatorial optimization
Combinatorial optimization is a subfield of mathematical optimization that consists of finding an optimal object from a finite set of objects, where the set of feasible solutions is discrete or can be reduced to a discrete set. Typical combina ...
, the method of symmetry-breaking constraints can be used to take advantage of
symmetries
Symmetry () in everyday life refers to a sense of harmonious and beautiful proportion and balance. In mathematics, the term has a more precise definition and is usually used to refer to an object that is invariant under some transformations ...
in many
constraint satisfaction In artificial intelligence and operations research, constraint satisfaction is the process of finding a solution through
a set of constraints that impose conditions that the variables must satisfy. A solution is therefore an assignment of value ...
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.
Symmetry is common in many real-life combinatorial problems. For example, certain vehicles in the
vehicle routing problem
The vehicle routing problem (VRP) is a combinatorial optimization and integer programming problem which asks "What is the optimal set of routes for a fleet of vehicles to traverse in order to deliver to a given set of customers?" It generalises ...
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
*
{{Combin-stub