AI Glossary / Graphs and symbolic AI / Advanced

Shaving

Definition

Shaving is a constraint-programming technique that temporarily tests a possible variable value or domain restriction, propagates its consequences and permanently removes it if the test proves inconsistency. It uses hypothetical assignments to eliminate choices that ordinary propagation has not already ruled out.

What it means

A constraint problem contains variables, their allowed values and rules linking them. Propagation reduces domains by removing values that cannot satisfy the constraints under the current information. However, a value can survive local checks while still leading inevitably to failure once it is assumed.

Shaving probes such possibilities. The solver temporarily commits to a candidate, runs a chosen consistency or propagation procedure and checks for contradiction. If the candidate empties a domain or otherwise proves failure, the original problem can safely exclude it.

If no contradiction is found, the candidate has merely survived that test. It has not necessarily been shown to belong to a complete solution. Proving impossibility differs from failing to prove it.

How it works

The solver records enough information to restore its previous state, then restricts a variable, often to one candidate value or a domain bound. Propagation runs on this temporary problem. A contradiction justifies a permanent deletion or bound tightening after restoration.

If the probe succeeds without contradiction, the solver restores the original state without concluding that the choice is globally feasible. Different shaving methods choose different candidates, consistency levels and stopping policies. Systematically testing singleton assignments with arc consistency is closely related to singleton arc consistency, but “shaving” also covers more selective procedures.

The extra reasoning costs time. A strong probe may eliminate many values but take longer than the search it saves. Methods such as Quick Shaving investigate how to target probing more efficiently. Any permanent pruning must follow from a sound contradiction test; a timeout, low heuristic score or failure to discover a solution is not enough.

Three practical examples

• A scheduling solver temporarily fixes a job's starting time and removes that choice if propagation proves the remaining schedule impossible.
• A finite-domain puzzle solver probes values that survive binary constraint checks, looking for contradictions that emerge only after assignment.
• An optimization model tests whether a proposed objective bound is compatible with its constraints, distinguishing a proved infeasible bound from an unfinished search.

Think of it this way

Think of trying a key in a controlled test before committing to it. If the key demonstrably cannot turn the required lock, it can be removed from consideration. If it turns that lock, it may still fail at another lock later.

The analogy is limited because constraint shaving concerns formal implications, not physical trial-and-error. The solver must restore temporary changes correctly, and the rejection must be logically justified within the encoded problem.

Worked example

Pruning beyond separate pairwise checks

Consider an invented problem with X allowed values {1, 2, 3}, Y allowed {1, 2} and Z allowed {1, 2}. The constraints are X not equal to Y, X not equal to Z and Y not equal to Z. Assume the solver initially propagates these as separate binary inequality constraints.

Every value initially has support in each neighboring domain, so ordinary binary arc consistency does not remove 1 or 2 from X. Now probe X = 1. Propagation forces Y = 2 and Z = 2, contradicting Y not equal to Z. Restore the temporary state and delete 1 from X.

Probe X = 2. It forces Y = 1 and Z = 1, again inconsistent, so delete 2. X is now fixed to 3, with solutions such as Y = 1, Z = 2. This example is about the chosen binary propagation: a stronger global all-different propagator could infer X = 3 directly, reducing the additional benefit of shaving.

Illustrative case study

Fictional case study: Birch Scheduling develops a finite-domain model for assigning small jobs to slots. Many candidate start times survive its initial propagation, but several cause immediate contradictions when fixed temporarily.

The team adds selective shaving and measures total solving time rather than celebrating the number of removed values alone. On some instances the probes reduce subsequent search; on others they repeat expensive work for little gain. The developers restrict probing to situations where the measured trade-off is useful.

They also discover that a failed probe was leaving temporary domain changes behind. Correct restoration becomes part of implementation validation. The fictional lesson is that stronger pruning needs both sound reasoning and careful state management.

Common misconceptions and mistakes

• A value that survives shaving is guaranteed feasible. It only survived the chosen consistency test.
• A probe that times out proves inconsistency. It does not; deletion requires a sound failure result.
• More pruning always means faster solving. Additional propagation can cost more than the search it avoids.
• Shaving is ordinary backtracking under another name. Both explore assumptions, but shaving uses probes to strengthen domains before or during the main search rather than simply continuing every surviving branch.

Business use

Shaving can help specialist scheduling, configuration and allocation models where difficult interactions leave many misleading domain values. Its practical value depends on the base propagators, instance structure and cost of temporary tests.

Compare complete solving runs under equivalent limits and settings. Record whether the objective is finding any solution, proving infeasibility or finding an optimum. A smaller search tree is useful evidence, but runtime, memory and correctness of restoration are also important. Improvements on one instance family should not be presented as guarantees for all workloads.

People also ask

Does shaving change the intended set of solutions?

Sound shaving removes only impossible choices, so it preserves solutions of the encoded problem.

Is it limited to individual values?

No. Variants can test bounds or other temporary domain restrictions, provided the resulting inference justifies the pruning performed.

Can stronger propagation make shaving less useful?

Yes. If the base propagator already derives the same exclusions efficiently, repeated probes may add little value.

Check your understanding

A temporary assignment does not trigger a contradiction, but the solver has not constructed a complete solution. May the value be marked “proven feasible”?

Answer: No. It remains a candidate. Lack of detected failure is weaker than an actual satisfying assignment or another valid feasibility proof.

Related terms

• Domain
• Constraint propagation
• Probing
• Constraint programming
• arc consistency
• singleton arc consistency
• backtracking
• all-different constraint

Learn next

Read arc consistency and global constraint. Reproduce the X/Y/Z example, recording temporary and permanent deletions separately. Explain why the same example may behave differently when the inequalities are represented by a stronger global constraint.

• Global constraint

More in Graphs and symbolic AI

• Set of support - A set of support is a selected group of clauses used to guide resolution-based theorem proving.
• Set semantics - Set semantics interprets a collection through set membership: an item is either present or absent, and repeated copies do not add meaning.
• Shape - Shape is the geometric form of an object or region, described through features such as its boundary, surface, proportions and arrangement of parts.
• Shift-reduce parsing - Shift-reduce parsing builds a grammatical analysis by moving input items onto a stack and combining items at the top of that stack into larger structures.
• Shortest Augmenting Path - Shortest Augmenting Path is a maximum-flow approach that increases flow through a network by using short source-to-sink paths in the residual network.
• (Shortest Path) Betweenness - (Shortest Path) Betweenness is a network measure describing how often a node lies between other nodes on shortest paths.

Sources

Lhomme, Quick Shaving, AAAI 2005 primary paper: https://fileadmin.cs.lth.se/ai/Proceedings/aaai05/PAPERS/AAAI05-065.pdf. The introduction and description of shaving and propagation-guided pruning were reviewed. Quick Shaving is a particular method within the broader technique; its experimental results are not generalised here. The inequality example and scheduling case are original illustrations.

Previous: Sharpening Next: Shear matrix