🧩 Constraint Solving POTD:Constraint Acquisition: Learning Constraint Models from Examples

[github-actions[bot]]

Emerging Topics · 2026-04-16

What if you didn't know the constraints? What if you had to discover them? Constraint Acquisition tackles exactly this scenario — inferring a constraint model from examples of valid and invalid assignments.

---

Problem Statement

Given:

• A set of variables X = {x1, x2, ..., xn} each with a finite domain D(xi)
• A constraint library Γ — a pool of candidate constraints (e.g., allDifferent, x + y ≤ z, x ≠ y, ...)
• Positive examples E+: complete assignments known to satisfy the unknown target network
• Negative examples E−: complete assignments known to violate at least one constraint

Find: A subset of constraints CN ⊆ Γ such that:

• Every assignment in E+ satisfies all constraints in CN
• Every assignment in E− violates at least one constraint in CN

Small Concrete Instance

Suppose a teacher designs a 4-variable scheduling puzzle with variables {A, B, C, D} and domains {1, 2, 3, 4}, but doesn't tell you the rules. You observe:

Example	A	B	C	D	Valid?
e1	1	2	3	4	✅
e2	2	1	4	3	✅
e3	1	1	3	4	❌
e4	1	2	2	4	❌
e5	1	2	3	3	❌

From e3 you deduce A ≠ B; from e4 you deduce B ≠ C; from e5 you deduce C ≠ D. Eventually you might infer allDifferent(A, B, C, D).

---

Why It Matters

Constraint modelling is the bottleneck. In practice, eliciting an accurate model from a domain expert is time-consuming and error-prone. Constraint acquisition automates this by letting users demonstrate acceptable and unacceptable configurations.

Human-computer interaction. Tools like interactive solvers and intelligent assistants can use acquisition algorithms to adapt to user preferences without requiring the user to articulate rules explicitly.

Reverse engineering & verification. Security researchers use constraint acquisition to infer protocol invariants or hardware safety properties from observed execution traces.

---

Modeling Approaches

Approach 1 — Version Space Learning (CONACQ)

The CONACQ algorithm (Bessiere et al., 2005) maintains a version space — the set of all constraint networks consistent with observed examples.

Key idea: The version space is represented implicitly as a collapse graph. Each node is a candidate constraint; each negative example collapses (eliminates) constraints that the example already violates. The learner queries the user about membership of new assignments.

bias B = { c ∈ Γ × scope | c is a candidate constraint }
for each negative example e−:
    remove from B all constraints c violated by e−
    (these are "too strong" — they falsely reject a valid solution)
for each positive example e+:
    mark all constraints in B that are satisfied by e+ as "still possible"
    remove constraints that no positive example satisfies
return the remaining set B as the learned network
```

**Trade-off:** Simple and fast but requires many examples for convergence. Query complexity can be exponential in the worst case.

#### Approach 2 — Active Learning (QuAcq)

QuAcq (Bessiere et al., 2013) is an *active* acquisition algorithm. Instead of passively waiting for examples, it *generates queries* to ask the user.

**Decision variables:** A Boolean assignment `q ∈ {0,1}n` representing a candidate complete assignment.

**Core algorithm:**
1. Pick a candidate assignment `q` that is consistent with all current constraints.
2. Ask the user: "Is this a valid solution?"
3. If **yes** (positive example): remove constraints violated by `q`.
4. If **no** (negative example): run a *find-scope* sub-procedure to identify the minimal violated constraint, then add it to the learned network.

```
CN ← ∅
while there exists q consistent with CN and undecided:
    answer ← query_user(q)
    if answer == YES:
        remove from B all c violated by q
    else:  // answer == NO
        scope ← find_scope(q, CN)
        c* ← find_constraint(scope, q, CN)
        CN ← CN ∪ {c*}
return CN

Trade-off: Dramatically fewer queries than passive learning — QuAcq achieves polynomial query complexity (in the number of constraints) when constraints have bounded arity. More complex to implement but far more practical.

Approach 3 — SAT / MaxSAT Encoding

Frame acquisition as a MaxSAT problem: introduce a Boolean variable bk for each candidate constraint ck. Encode:

• For each e−: at least one selected constraint must be violated → ∨k (bk ∧ ¬ck(e−))
• For each e+: no selected constraint is violated → minimize conflicts with e+

Objective: minimize the number of constraints selected (Occam's Razor), or minimize prediction error on a held-out set.

Trade-off: Declarative and flexible (easy to add preferences like "prefer global constraints"). Scales poorly for large candidate sets, but modern MaxSAT solvers handle moderate instances well.

Example: QuAcq find_scope in MiniZinc-style pseudo-code

% find_scope: given a negative query q, narrow down which variables
% are in the scope of the violated constraint.

function find_scope(q: Assignment, CN: ConstraintNetwork) -> Scope:
  S = all_variables  % start with full scope
  for each variable xi in some ordering:
    % Build q' by replacing xi's value with a "free" value
    q' = q with xi freed (try all values in domain)
    if exists assignment for xi such that q' is consistent with CN
       AND user_query(q') == YES:
      % xi is NOT in the scope of the violated constraint
      S = S \ {xi}
    % else xi must be involved
  return S  % minimal scope of violated constraint

---

Key Techniques

1. Bias and Language Bias

The constraint language (library Γ) must be chosen carefully. A too-large library slows convergence; a too-small one may miss the target. Modern systems use intensional biases (e.g., "all binary constraints of the form aixi + ajxj ≤ b") rather than enumerating every possible constraint.

2. Scope Inference and Arity Reduction

Finding which variables participate in a violated constraint (scope inference) is the hardest sub-problem. QuAcq's find_scope uses binary search over variable subsets, achieving O(n log n) queries per negative example for binary constraints.

3. Symmetry and Redundancy Pruning

Learned networks often contain redundant constraints (e.g., x ≠ y is subsumed by allDifferent(x, y, z)). Post-processing with a CP solver to detect and remove dominated constraints greatly compresses the learned model.

4. Partial Queries and Noise Tolerance

Real users make mistakes. Robust variants (e.g., CAR — Constraint Acquisition with Robustness) relax the requirement that every label is correct, using weighted voting or MaxSAT to find a network consistent with the majority of examples.

---

Challenge Corner

Extension: Standard acquisition assumes the constraint scope (which variables interact) is unknown. But what if you also don't know the arity — whether constraints are binary, ternary, or global?

Can you design a query strategy that efficiently discovers both the scope and the type of constraint simultaneously? What lower bound on the number of queries is required in the worst case?

---

References

1. Bessiere, C., Coletta, R., Freuder, E., O'Sullivan, B. (2005). Leveraging the learning power of examples in automated constraint acquisition. CP 2005. — Introduces CONACQ.

2. Bessiere, C., Coletta, R., Hebrard, E., Katsirelos, G., Lazaar, N., Narodytska, N., Quimper, C., Walsh, T. (2013). Constraint Acquisition via Partial Queries. IJCAI 2013. — Introduces QuAcq with polynomial query complexity.

3. Tsouros, D., Stergiou, K., Bessiere, C. (2023). Omni-directional search for constraint acquisition. IJCAI 2023. — Recent extension handling noisy oracles and global constraints.

4. Rossi, F., van Beek, P., Walsh, T. (eds.) (2006). Handbook of Constraint Programming. Elsevier. — Chapter 17 covers learning and constraint acquisition in depth.

Generated by Constraint Solving — Problem of the Day · ● 182K · ◷

• expires on Apr 23, 2026, 1:02 PM UTC

[github-actions[bot]]

This discussion has been marked as outdated by Constraint Solving — Problem of the Day.

A newer discussion is available at Discussion #26868.