Must every value be interchangeable?

No. Symmetry may apply only within subsets of values or through particular transformations.

Is this the same as variable symmetry?

No. Value symmetry changes assignments' values while leaving variables in place.

Can symmetry breaking make a problem harder in practice?

Additional constraints and interactions can affect search, so performance should be measured rather than inferred from solution counts alone.

AI Glossary / Graphs and symbolic AI / Advanced

Value symmetry

Definition

Value symmetry is a symmetry of a constraint problem that changes assigned values while leaving the variables in place and preserves solutions. A common form is a consistent permutation of interchangeable value labels across an assignment. Recognizing it lets a solver avoid exploring multiple labelings of the same underlying solution pattern.

What it means

Suppose a graph must be colored with labels 1, 2, and 3, and the constraints only require neighboring vertices to have different colors. Renaming every occurrence of color 1 as 2 and every occurrence of 2 as 1 preserves a valid coloring. The vertices stay in their original positions; only their values change.
This differs from variable symmetry, which rearranges variables. It also differs from changing one isolated value while keeping all other assignments fixed. A valid global renaming can require coordinated changes across the whole solution. Labels alone cannot establish symmetry: constraints, domain restrictions, and any optimization objective must be examined.

How it works

Identify a bijective transformation of values and show that applying it to a solution produces another solution. In optimization, also establish that the transformation preserves the relevant objective value if it is to be treated as an equivalent alternative for pruning.
Symmetry-breaking constraints select representatives from groups of equivalent solutions. They should preserve at least one representative from every relevant group. For interchangeable labels, value precedence can require the first occurrence of label 1 to precede the first occurrence of 2, and similarly for later labels when used.
Such constraints reduce redundant labelings; they do not change the original operational requirements. Their runtime effect depends on propagation and search, not just the reduction in represented solutions.

Three practical examples

A resource-assignment model uses machine labels as values. If the machines have identical capabilities, availability, and costs, consistently swapping their labels may preserve both feasibility and objective value. A special capability or maintenance window can destroy that equivalence.
A graph-coloring model uses color labels solely to distinguish adjacent vertices. Global color permutations preserve the inequalities, so one representative of each relabeling pattern can suffice when the task is to find a coloring.
A grouping model assigns items to unlabeled groups using numerical group identifiers. Renaming the groups may generate redundant solutions. If one group has a special capacity or business role, its identifier cannot automatically be included among the interchangeable values.

Think of it this way

Imagine several identical storage boxes distinguished only by removable name tags. Swapping the tags everywhere in the plan does not change how the items are grouped. Moving just one item's tag assignment, however, changes the grouping and may break a requirement. Symmetry relies on consistent renaming.

Worked example

Take four vertices arranged in a path: A-B-C-D. Each receives one of three colors, 1, 2, or 3. Adjacent vertices must have different colors. There are 3 choices for A and 2 choices for each subsequent vertex, giving 3 × 2 × 2 × 2 = 24 valid assignments.
The assignment (1,2,1,2) is valid. Globally exchanging colors 1 and 2 produces (2,1,2,1), also valid. Changing only A from 1 to 2 instead produces (2,2,1,2), which violates the A-B constraint. Global value symmetry does not authorize arbitrary isolated substitutions.
Choose a canonical labeling by naming the first color encountered 1, the next previously unseen color 2, and the next 3. The 24 assignments reduce to four representatives: (1,2,1,2), (1,2,1,3), (1,2,3,1), and (1,2,3,2). Every valid assignment can be consistently renamed into one of these patterns.
Merely requiring A=1 leaves eight valid assignments, so it breaks only part of the symmetry. First-occurrence ordering removes the remaining duplicate labelings in this example.
If a new requirement fixes A to color 3, unrestricted color permutations are no longer symmetries of the revised problem. Adding A=1 would then remove every solution, showing why symmetry must be established for the actual model before a breaking constraint is applied.

Illustrative case study

In a fictional packaging operation, a solver assigns jobs to three apparently identical lines. A developer adds first-occurrence ordering over the line identifiers to suppress equivalent assignments.
During review, the team discovers that one line alone supports a particular package material. The earlier assumption of full interchangeability is therefore false. The team restricts any permitted renaming to lines whose relevant capabilities and costs actually match, and checks representative assignments against the complete model.
The corrected approach removes only demonstrably redundant alternatives. Reviewers also clarify that an output report must map the chosen representative back to real equipment identifiers. The benefit comes from avoiding duplicate search while preserving operational meaning.

Common misconceptions and mistakes

“Value symmetry means every value can replace every other independently.” A transformation may require coordinated substitutions throughout the assignment.
“Matching labels or data types prove symmetry.” Feasibility constraints and relevant objective contributions determine whether a transformation is valid.
“Fixing the first variable breaks every symmetry.” It may leave many equivalent labelings, as the worked example shows.
“Symmetry breaking preserves every labeled solution.” It intentionally removes equivalent labelings while retaining suitable representatives.
“Feasibility symmetry is enough for optimization.” A transformation that changes cost cannot automatically be used to discard objective-distinct choices.

Business use

Value symmetry can reduce redundant search in scheduling, allocation, and grouping applications. Start by documenting why particular values are interchangeable in the model, including less visible differences such as eligibility rules, location, setup costs, and existing commitments.
Test proposed breaking constraints on small instances whose solutions can be enumerated. Confirm that each original equivalence class still has a representative and that optimal objective values are preserved where required. Recheck the assumption when business rules change. If the task requires counting or listing all distinct labeled assignments, account for the removed labelings explicitly instead of reporting representative counts as the original total.

Check your understanding

Why are there 24 path colorings?

Answer: The first vertex has three choices and each of the next three has two.

Why is a global swap valid?

Answer: Every adjacent pair remains unequal after a bijective renaming.

Why does the added A=3 requirement matter?

Answer: It distinguishes a particular label and invalidates unrestricted color renaming.

Related terms

Constraint satisfaction problem
Graph coloring
variable symmetry
symmetry breaking
interchangeable values
value precedence
canonical representative
combinatorial optimization

Learn next

Compare global value permutations with isolated value substitutions. Then implement first-occurrence ordering on a small model and verify which solution classes it preserves.

Sources

Walsh, Symmetry Breaking using Value Precedence: https://arxiv.org/pdf/0903.1136 Gent and colleagues, Symmetry and Consistency: https://sites.cs.st-andrews.ac.uk/people/ipg1/papers/CP05-159revisedCRD-TK.pdf

Previous: Value sensitive design Next: ValueDICE