🧩 Constraint Solving POTD:Constraint Acquisition — Learning Constraint Models from Data

[github-actions[bot]]

📅 March 25, 2026 · Category: Emerging Topics

---

What if instead of writing constraints by hand, you could learn them automatically from examples? Today's problem sits at the intersection of constraint programming and machine learning: Constraint Acquisition — the art of inferring a constraint model from observed data.

---

Problem Statement

Given a set of classified examples over a fixed set of variables, find a constraint network that:

• Accepts all positive examples (valid assignments), and
• Rejects all negative examples (invalid assignments).

More formally: let X = {x₁, …, xₙ} be variables with domains D₁, …, Dₙ, and let E⁺ and E⁻ be finite sets of complete assignments. The goal is to find a set of constraints C over X such that every e ∈ E⁺ satisfies C and every e ∈ E⁻ violates at least one constraint in C.

A Small Concrete Instance

Suppose we observe four variables x₁, x₂, x₃, x₄ ∈ {1, 2, 3, 4} and receive these examples:

Assignment	Label
(1, 2, 3, 4)	✅ positive
(2, 1, 4, 3)	✅ positive
(3, 4, 1, 2)	✅ positive
(1, 1, 2, 3)	❌ negative
(2, 2, 1, 3)	❌ negative
(1, 2, 2, 4)	❌ negative

A learner should infer: AllDifferent(x₁, x₂, x₃, x₄) — all variables must take distinct values.

Input: variables with domains, positive and negative example assignments.
Output: a set of constraints (from some background language Γ) consistent with all examples.

---

Why It Matters

Modeling is the hardest part of CP. Expert modelers spend significant time formulating constraints, and errors are common. Constraint acquisition lowers the barrier to deploying constraint-based systems by automating this step.

Business rules are often implicit. In enterprise settings, valid configurations, schedules, or plans are known but hard to articulate as formal rules. Acquisition can extract those rules from historical data or from an interactive oracle (a domain expert who answers yes/no questions).

Preference learning and personalisation. In configuration and recommender systems, user preferences can be treated as soft constraints to be learned from feedback — enabling solvers to find solutions tailored to individual users.

---

Modeling Approaches

Approach 1: Version Space Learning (CONACQ)

The classical approach maintains a version space: the set of all constraint networks consistent with the examples seen so far.

Bias language Γ: define a finite set of candidate constraints (e.g., all binary constraints between pairs of variables from a library: =, ≠, <, ≤, |, etc.).

Decision variables: for each candidate constraint c ∈ Γ, a boolean y_c ∈ {0, 1} indicates whether c is in the target network.

Key invariants:

For each e ∈ E⁺: all selected constraints must be satisfied
  → ∀c ∈ Γ, y_c = 1  ⟹  c(e) = true

For each e ∈ E⁻: at least one selected constraint must be violated
  → ∃c ∈ Γ, y_c = 1  ∧  c(e) = false
```

As new examples arrive, constraints are pruned from `Γ` (a positive example rules out any violated constraint; a negative example ensures at least one rejecting constraint remains selected).

**Trade-offs:** Simple and anytime, but the version space can be exponentially large, and the learned network may be incomplete (too few constraints) or over-constrained (too many).

#### Approach 2: Partial MaxSAT / MIP Formulation

For batch learning, encode acquisition as a **MaxSAT or MIP** problem to find the *smallest* consistent constraint network.

**Variables:** `y_c ∈ {0, 1}` for each candidate `c ∈ Γ`.

**Constraints:**
```
# Every negative example is rejected by at least one constraint:
∀ e ∈ E⁻:  Σ_{c : c(e)=false} y_c  ≥  1

# No constraint rejects a positive example:
∀ e ∈ E⁺, ∀ c ∈ Γ : c(e)=false:  y_c = 0

Objective: minimize |{c : y_c = 1}| (Occam's razor — prefer a simpler model).

Trade-offs: Finds provably minimal networks; scales well for moderate |E| and |Γ|; naturally handles noisy data by relaxing hard constraints on E⁺.

Example: QuAcq Active Learning Loop (Pseudo-code)

# QuAcq: Query-driven Constraint Acquisition
# Gamma = background constraint library (all candidate constraints)
# C_L   = learned constraints so far (starts empty)
# C_T   = target constraints (unknown to learner)

def quacq(Gamma, oracle):
    C_L = []
    while True:
        # Generate a query: an assignment e that satisfies C_L
        e = find_solution(C_L, domains)
        if e is None:
            return C_L  # No more solutions — C_L = C_T

        # Ask the oracle: is e a valid assignment?
        if oracle.classify(e) == POSITIVE:
            # Remove from Gamma any constraint violated by e
            Gamma = [c for c in Gamma if c.satisfied_by(e)]
        else:
            # e is negative: find a "conflict set" — a minimal
            # subset of variables whose partial assignment e|_S
            # is already rejected by C_T
            S = find_conflict_set(e, oracle)
            # Learn: at least one constraint in Gamma over S
            #        must be in C_T
            new_constraint = choose_from(Gamma, scope=S)
            C_L.append(new_constraint)
            Gamma.remove(new_constraint)

QuAcq drives learning by generating discriminating queries — assignments that are solutions under the current partial model but may violate unknown target constraints. Each negative answer focuses the search.

---

Key Techniques

1. Version Space & Constraint Elimination

Every positive example immediately eliminates from Γ any constraint it violates (that constraint cannot be in the target). Every negative example guarantees that at least one remaining candidate must be in the target, which drives the search. Efficient data structures (indexed by constraint scope) make this tractable even for large |Γ|.

2. Active Learning and Query Generation

Passive acquisition (learning only from given examples) is data-hungry. Active acquisition generates queries by solving a CSP over the current partial model — each query is designed to maximally discriminate between possible target networks. The QuAcq algorithm provably converges to the target using O(n² · log|Γ|) queries in the best case, where n is the number of variables.

3. Scope Inference via Conflict Sets

Rather than guessing which variables are related, modern algorithms identify conflict sets: minimal subsets of variables whose joint assignment is already infeasible. Finding a minimum conflict set (analogous to MUS extraction in SAT) focuses the learner on the right variable pairs or tuples, drastically pruning Γ.

---

Challenge Corner

🧠 Extension — handling noise: Real-world data is noisy; some positive examples may accidentally violate a true constraint. How would you adapt the MIP formulation to tolerate a bounded number of mis-labelled examples? Can you formulate a soft version where constraints are associated with confidence weights?

🧠 Symmetry and redundancy: A learned network may contain redundant constraints (one implies another). Can you add a post-processing step to compute a canonical or irredundant basis for the learned network?

🧠 Global constraints: The examples above hint at AllDifferent. But acquisition frameworks typically work over binary or low-arity constraint libraries. Can you design a procedure that recognises when a set of binary ≠ constraints should be lifted to a single AllDifferent global constraint?

---

References

1. Bessiere, C., Coletta, R., Freuder, E., & O'Sullivan, B. (2004). Query-driven Constraint Acquisition. IJCAI 2005. — the original CONACQ paper.
2. Bessiere, C., Daoudi, A., Hebrard, E., Katsirelos, G., Lazaar, N., Mechqrane, Y., Paparrizou, A., Quimper, C-G., Walsh, T. (2017). Learning Constraints through Partial Queries. Artificial Intelligence, 261, 1–28. — QuAcq and its analysis.
3. Tsouros, D., Berden, S., & Guns, T. (2023). Constraint Acquisition: Current Research and Challenges. IJCAI 2023 Survey Track. — excellent accessible overview of the field in 2023.
4. Rossi, F., van Beek, P., & Walsh, T. (eds.) (2006). Handbook of Constraint Programming. Elsevier. — Chapter 22 covers learning and constraint acquisition in the broader CP context.

---

Constraint acquisition bridges the gap between machine learning and constraint programming — instead of learning a function, you learn a feasibility boundary. As datasets grow and domain experts become the bottleneck, these techniques are more relevant than ever.

Tomorrow: another problem from the constraint solving universe. Stay curious! 🔍

AI generated by Constraint Solving — Problem of the Day · history

• expires on Apr 1, 2026, 12:56 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 #23114.