Is a weight always a business priority?

No. It may encode search experience rather than organizational preference.

Does weighting remove constraints?

In the basic approach described here, it changes search guidance while retaining the constraints.

Is weighted-degree search identical to weighted local search?

No. One uses weights to guide variable selection; the other can use weighted violations to compare complete assignments.

AI Glossary / Graphs and symbolic AI / Intermediate

Constraint weighting

Definition

Constraint weighting assigns numerical weights to constraints to guide a solver's search. In a common local-search form, repeatedly troublesome or currently violated constraints receive higher weights, making their violations more costly in the search score. This can encourage the solver to leave an unproductive arrangement and explore different assignments.

What it means

An unweighted repair method may count every violated constraint equally. Several neighboring assignments can then look equally bad, leaving no clearly improving move. Changing weights changes the search landscape without changing which assignments satisfy all mandatory constraints.

These adaptive weights need not represent business importance. A rule may gain weight because the search keeps encountering it, not because an owner decided that it matters more than another rule.

The term also appears in systematic search. A solver can increase weights for constraints associated with failures and use their accumulated weights when choosing which variable to assign next. That weighted-degree approach uses failure history for branching rather than directly minimizing a weighted violation score. The intended mechanism should therefore be stated.

How it works

For a simple local-search version, begin with a complete assignment and positive weights, often initially equal. Compute its score by adding the weights of violated constraints. Evaluate permitted changes, such as changing one variable's value, and prefer moves that lower the score.

If the search reaches a point with no improving move, increase selected violation weights according to the algorithm's rule. Reevaluate the neighbors under the revised score. Previously unattractive moves may now become useful.

Some methods add randomness, restarts, or weight adjustment policies. Their behavior depends on the neighborhood, update rule, and stopping conditions.

In weighted-degree search, by contrast, a failure such as a domain becoming empty can increase an associated constraint's weight. Variable selection then considers weighted connections, sometimes together with domain size. This is search guidance, not a proof that a highly weighted variable is inherently defective.

Three practical examples

1. A timetable repair procedure raises the search penalty on recurring room clashes, encouraging a different arrangement of sessions.

2. A configuration solver uses failure-based weights to prioritize decisions involved in repeated compatibility conflicts.

3. A roster prototype compares adaptive weighting with ordinary violation counting across the same test instances, recording success rates and runtime rather than assuming universal improvement.

Think of it this way

Think of putting a more noticeable marker beside a puzzle rule that you keep breaking. The marker draws attention to a recurring obstacle and encourages a different next move.

The rule itself has not changed, and a quieter marker does not make another mandatory rule optional. The analogy also leaves out algorithmic details: a solver needs precise numerical updates and a defined method for selecting moves, not merely human attention.

Worked example

Consider two Boolean variables X and Y and three constraints:

C1: X or Y. C2: not X or Y. C3: X or not Y.

Use 0 for false and 1 for true, allow only single-variable flips, and give every constraint weight 1. At assignment (0, 0), only C1 fails, so the score is 1. Its two neighbors are (1, 0), which violates only C2, and (0, 1), which violates only C3. Both also score 1. There is no strictly improving neighbor.

Increase the weight of the currently violated C1 to 2, leaving the others at 1. The current assignment now scores 2, while either neighbor scores 1. Choose (1, 0). From there, flipping Y gives (1, 1), which satisfies all three constraints and scores 0.

The illustration shows how weighting breaks this plateau for this move rule. It does not prove that every plateau can be escaped immediately or that weighting is always faster than allowing sideways moves.

Illustrative case study

Fictional case: Willow Events tests a workshop scheduler that repeatedly shifts the same room conflict between sessions. The developer introduces adaptive violation weights and records each update.

During review, a planner mistakes a large weight for a statement that one department deserves priority. The team separates business preferences from search-history weights in the interface and documentation. It also checks every final timetable against mandatory rules. The lesson is that an internal search score needs a clear interpretation before it is exposed as a decision explanation.

Common misconceptions and mistakes

Do not confuse adaptive search weights with policy-approved preference penalties. They may use similar arithmetic while serving different purposes.

Do not assume a small weighted score means a feasible result. With positive weights, zero violation cost establishes satisfaction of the scored constraints; a positive score still represents violations.

Do not use a high weight as evidence that the corresponding requirement is wrong. Interactions and search history may explain the difficulty.

Finally, local search that reaches its time limit has not thereby proved infeasibility. Weighting changes how the search proceeds, not the meaning of a proof.

Business use

Constraint weighting can support scheduling and configuration systems that must search large spaces of combinations. A useful evaluation compares approaches on representative instances under consistent limits and records variability across runs.

Keep mandatory requirements distinct from negotiable preferences. If a business wants to relax a requirement, that is an explicit modeling decision; a solver's weight update should not silently authorize it. Preserve enough search configuration to reproduce important results.

Check your understanding

A mandatory constraint's adaptive weight rises from 1 to 5. Does violating a different mandatory constraint become acceptable?

Answer: No. The score may favor a temporary search move, but a final feasible solution must still satisfy every mandatory constraint.

Related terms

Constraint satisfaction
Local search
Min-conflicts
local minimum
weighted degree
constraint optimization
hard constraint
soft constraint

Learn next

Compare the worked example with a version that permits sideways moves before changing weights. Then study weighted-degree variable ordering and identify exactly which failures trigger updates. Keep algorithmic weights separate from any preference costs in your notes.

Sources

Primary sources: John Thornton, Constraint Weighting Local Search for Constraint Satisfaction: https://jthornton.org/wp-content/uploads/2021/04/PhD2000.pdf

Grimes and Wallace, Learning from Failure in Constraint Satisfaction Search: https://cdn.aaai.org/Workshops/2006/WS-06-11/WS06-11-003.pdf

The sources cover local-search weighting and failure-guided variable ordering. The Boolean example and fictional case are original.

Previous: Constraint satisfaction problem Next: Construct validity