Does constraint learning allow the solver to invent new requirements?

A sound solver learns consequences of existing requirements and assumptions, rather than arbitrary restrictions that remove valid solutions.

Can one learned nogood apply in several branches?

Yes. It can reject the same incompatible combination regardless of unrelated choices made around it.

Is every failed run evidence for a nogood?

No. A justified inconsistency or impossibility explanation is needed; a timeout alone is insufficient.

AI Glossary / Graphs and symbolic AI / Intermediate

Constraint learning

Definition

Constraint learning records new restrictions derived from failures encountered while solving a constraint problem. A common form stores a nogood: a combination of assignments that cannot be part of any solution under the current model. The solver can then avoid or prune that combination when it appears again, instead of rediscovering the same reason for failure.

What it means

The learned restriction is not an arbitrary new business rule. In a sound learning method, it follows from the existing constraints and the assumptions under which the failure was established. It excludes no genuine solution of that model.

The purpose is to turn search experience into reusable reasoning. Backtracking abandons a failed branch, and backjumping chooses a relevant earlier decision to revise. Constraint learning additionally retains information that can help in a different branch later.

This meaning differs from learning an unknown constraint model from examples or user demonstrations. Here, the problem's rules are already specified, and the solver derives additional consequences to make solving more efficient.

How it works

When a branch fails, the solver identifies a sufficient explanation for that failure. The explanation may involve a subset of the current assignments rather than every decision made so far.

It converts that explanation into a restriction forbidding the incompatible combination. For Boolean assignments, a learned clause can express that at least one implicated choice must change. For other domains, the representation may use a nogood or another supported constraint form.

The stored restriction can later reject a repeated combination or propagate a consequence before the whole combination is assembled. Smaller explanations can apply more widely, although minimizing them may be expensive.

Learning also consumes memory and processing time. Solvers may manage which learned restrictions remain active. If the original model or temporary assumptions change, the validity and scope of learned information must be handled correctly.

Three practical examples

1. A scheduling solver retains a combination of resource choices that cannot fit within a capacity limit, preventing repeated exploration of that same combination.

2. A configuration solver learns that several selected options cannot coexist and uses the result to rule out the last incompatible option earlier in later searches.

3. A satisfiability solver derives a clause from a conflict so future decisions can trigger propagation instead of reproducing the identical contradiction.

Think of it this way

Think of constraint learning as writing down a proven dead-end combination on a reusable checklist. The note says which choices cannot all be made together, so the solver can recognize the pattern even after other choices have changed.

The analogy has limits. The note must be logically justified and tied to the right model assumptions. A failed attempt caused by a timeout or an implementation bug is not a valid reason to forbid a combination.

Worked example

Consider three integer variables representing toy resource amounts: A has domain {1, 3}, B has {2, 4}, and C has {2, 3}. Require A + B + C to be at most 8.

Suppose a search chooses A = 3 and B = 4. C = 2 gives total 9, and C = 3 gives total 10. Every remaining C value fails.

The solver can learn the nogood NOT(A = 3 AND B = 4). Its justification is that C is always at least 2, so the two chosen values already imply a total of at least 9. No assignment to C can repair that pair.

In a later branch, once A = 3 is selected, the learned restriction can eliminate B = 4 without trying C again. If A = 1, however, B = 4 remains possible: C = 2 gives total 7 and C = 3 gives total 8.

There are eight total domain combinations and six valid ones. The nogood removes exactly the two invalid combinations in this small example. It summarizes a consequence of the capacity rule; it does not change which complete solutions are valid.

Illustrative case study

Fictional case: Cedar Scheduling uses the capacity problem as a teaching demonstration. Its first search trace repeatedly tries the pair A = 3 and B = 4 after unrelated choices elsewhere in the model change.

The team records the pair as a derived nogood and checks that all six originally valid combinations remain permitted. It stores the supporting assumptions to avoid invalid reuse after model changes.

The case illustrates reusable reasoning. No runtime improvement is claimed.

Common misconceptions and mistakes

Do not learn a prohibition merely because the solver has not yet found a completion. Failure to find a solution within a limit is not proof that none exists.

Do not confuse a nogood with a list of individually forbidden values. In the example, A = 3 and B = 4 are each possible separately; their combination is impossible.

Do not treat learned constraints as independent facts after changing the model. A restriction derived from a capacity of 8 may be invalid if the capacity increases. Finally, learning every possible redundant consequence can cost more than it saves.

Business use

For business teams, constraint learning explains how a solver can use earlier failures productively without changing the underlying requirements. It may also provide concise explanations of incompatible decision combinations.

Reviewers should distinguish solver-derived restrictions from policy choices entered by people. When learned information is persisted across runs, its relationship to the model version and temporary assumptions matters. Performance should be evaluated on representative workloads, because explanation generation, storage, and propagation all contribute to the total cost.

Check your understanding

The solver learns NOT(A = 3 AND B = 4). Does this mean B = 4 is always forbidden?

Answer: No. It is forbidden together with A = 3 under the stated model. Other A values may allow B = 4.

Related terms

Conflict set
Constraint satisfaction
Conflict-directed backjumping
Search
Nogood
clause learning
propagation
model assumptions

Learn next

Enumerate the capacity example and verify that the learned restriction removes no valid solution. Then compare recording an entire failed assignment with extracting a smaller explanation, and examine how learned clauses support later propagation.

Sources

Russell and Norvig, Artificial Intelligence: A Modern Approach, Constraint Satisfaction Problems: https://aima.cs.berkeley.edu/2nd-ed/newchap05.pdf . The primary distinction between conflict-directed backtracking and learning derived constraints was consulted. The resource calculation and fictional trace are original. Scope is search-derived learning, not induction of a constraint model from data.

Previous: Constraint hypergraph Next: Constraint logic programming