🧩 Constraint Solving POTD:Product Configuration — Constraint Satisfaction at the Point of Sale

[github-actions[bot]]

Category: Configuration | Date: 2026-04-07

Configure a product from a catalogue of components — respecting compatibility rules — so every option the customer picks yields a valid, buildable system.

---

Problem Statement

A product configurator presents a user with choices across several feature variables, each with a finite domain of options. Compatibility rules eliminate forbidden combinations. The task is to ensure every partial selection the user makes can be extended to a complete valid configuration — and ideally to find the one that maximises some objective (e.g., performance-per-dollar).

Concrete Instance

Configure a desktop PC from five feature groups:

Feature	Options
cpu	i5, i7, r5, r9
ram	8GB, 16GB, 32GB, 64GB
gpu	integrated, gtx3060, rtx4090
storage	ssd256, ssd512, ssd1tb
psu	450w, 650w, 850w

Compatibility constraints (a sample):

integrated_gpu  →  cpu ∈ {i5, i7}            # integrated GPU is Intel-only
rtx4090         →  psu = 850w                 # power hungry GPU
r9              →  ram ≥ 16GB                 # AMD flagship needs memory
r9              →  psu ≥ 650w
gtx3060         →  psu ≥ 650w
ssd1tb          →  psu ≥ 450w                 # always satisfied, redundant but illustrative
```

A **valid configuration** assigns one option to every feature such that all constraints hold. An interactive configurator also needs **propagation**: selecting `rtx4090` must immediately eliminate `psu = 450w` from the user's choices.

---

### Why It Matters

**Mass customisation & e-commerce** — Companies like Dell, BMW, and Cisco use product configurators to let customers build personalised products while guaranteeing every order is manufacturable. Invalid configurations reaching production can cost thousands of dollars per incident.

**Software & cloud provisioning** — Choosing VM sizes, storage tiers, networking options, and OS images for a cloud deployment is a configuration problem where incompatible selections must be ruled out before the order is placed.

**Manufacturing & supply chain** — Bills of materials are generated from configurations; incorrect combos cascade into procurement errors and assembly-line stoppages.

---

### Modelling Approaches

#### Approach 1 — Binary CSP / Constraint Network

The most direct model treats each feature as a variable and each compatibility rule as a **binary or unary constraint**.

**Decision variables:**
```
cpu      ∈ {i5, i7, r5, r9}
ram      ∈ {8, 16, 32, 64}          # GB
gpu      ∈ {integrated, gtx3060, rtx4090}
storage  ∈ {ssd256, ssd512, ssd1tb}
psu      ∈ {450, 650, 850}          # watts
```

**Constraints (some as tables / implications):**
```
table([cpu, gpu], {(i5,integrated),(i7,integrated),(i5,gtx3060),...})
gpu = rtx4090  →  psu = 850
cpu = r9       →  ram ≥ 16
cpu = r9       →  psu ≥ 650
gpu = gtx3060  →  psu ≥ 650
```

**Trade-offs:** Very natural to express. Constraint propagation (arc consistency) is directly applicable and filters infeasible options in real time. Works well when rules are pairwise; gets verbose with higher-arity interactions.

---

#### Approach 2 — MIP / Pseudo-Boolean Optimisation

When we add **pricing and an objective** (maximise performance score within a budget), a Mixed-Integer Programme is appropriate.

**Decision variables (one-hot encoding):**
```
x[cpu,v]  ∈ {0,1}   for each value v of cpu
x[ram,v]  ∈ {0,1}   for each value v of ram
...
∑_v x[feat,v] = 1   for each feature feat   (exactly one option chosen)
```

**Implication as linear inequality:**
```
# "if rtx4090 chosen then psu must be 850w"
x[gpu, rtx4090] ≤ x[psu, 850w]
```

**Objective:**
```
maximise  ∑_{feat,v}  perf[feat,v] · x[feat,v]
subject to  ∑_{feat,v}  cost[feat,v] · x[feat,v]  ≤  budget

Trade-offs: Handles objectives and budgets cleanly. LP relaxation gives good bounds. But one-hot explosion grows the model for large catalogues (millions of SKUs). Propagation is weaker than CP at the combinatorial level.

---

Approach 3 — Knowledge Compilation (BDD / d-DNNF)

For interactive configurators where sub-millisecond response is critical, the entire constraint network can be compiled offline into a Binary Decision Diagram (BDD) or a decomposable negation normal form (d-DNNF). At query time, inference is linear in the compiled structure size.

Trade-offs: Extremely fast online phase; offline compilation can be expensive and the compiled form may be exponentially large in the worst case. Best suited when the catalogue is fixed and queries are frequent (e.g., a web shop serving millions of sessions).

Example Model — MiniZinc (CP approach)

include "globals.mzn";

% Feature domains
int: nCPU = 4;   int: nRAM = 4;   int: nGPU = 3;
int: nPSU = 3;

var 1..nCPU: cpu;   % 1=i5, 2=i7, 3=r5, 4=r9
var 1..nRAM: ram;   % 1=8GB, 2=16GB, 3=32GB, 4=64GB
var 1..nGPU: gpu;   % 1=integrated, 2=gtx3060, 3=rtx4090
var 1..nPSU: psu;   % 1=450w, 2=650w, 3=850w

% integrated GPU requires Intel CPU (1 or 2)
constraint  gpu = 1  ->  cpu <= 2;

% rtx4090 requires 850w PSU
constraint  gpu = 3  ->  psu = 3;

% r9 requires >= 16GB RAM and >= 650w
constraint  cpu = 4  ->  ram >= 2;
constraint  cpu = 4  ->  psu >= 2;

% gtx3060 requires >= 650w
constraint  gpu = 2  ->  psu >= 2;

array[1..nGPU] of int: perf = [0, 50, 120];
array[1..nRAM] of int: perf_ram = [0, 10, 20, 35];

solve maximize perf[gpu] + perf_ram[ram];

---

Key Techniques

1. Arc Consistency (AC-3 / AC-4) for Propagation

The interactive use-case demands that when a user picks an option, all now-impossible options are immediately removed from other features. Arc consistency enforces that for every remaining value v of variable X, there exists at least one support in every neighbouring variable's current domain. AC-3 runs in O(ed³) for e edges and domain size d — fast enough for real-time UI updates.

2. Implication Graphs & Unit Propagation

When constraints are expressed as implications (a → b, a → ¬c), they form an implication graph. Selecting an option triggers a cascade of forced deductions — exactly unit propagation from SAT. Many commercial configurators compile rules into Horn clauses and use dedicated unit propagation engines for this reason.

3. Symmetry Breaking & Canonicalisation

Large catalogues often contain nearly-identical products (e.g., different RAM modules with the same capacity but different brands). Grouping equivalent options and breaking symmetry reduces the search space significantly. In the MIP model, symmetry between identical options can be broken by lexicographic ordering constraints on their indicator variables.

4. Consistency Maintenance during Interactive Configuration

A key property beyond satisfiability is backtrack-free guarantee: every option still shown to the user must be completable to a full valid configuration. This requires full lookahead (enforcing arc consistency after each selection), not just filtering the locally infeasible options. This is sometimes called the complete configuration property.

---

Challenge Corner

Can you guarantee backtrack-free configuration without rerunning full AC after every pick?

In practice, re-running AC-3 after each user selection can be expensive for large catalogues. One approach is to precompute a compiled representation (BDD or ZBDD) of the solution space offline. Can you think of an incremental AC data structure that avoids restarting from scratch each time? How does this relate to watched literals in DPLL-based SAT solvers?

Bonus: How would you handle mandatory features (options the user hasn't chosen yet but which are forced by current selections)? What data structure efficiently tracks these implied singletons?

---

References

1. Sabin & Weigel (1998) — Product Configuration Frameworks: A Survey. IEEE Intelligent Systems, 13(4). A foundational survey of the field.
2. Dechter, R. (2003) — Constraint Processing. Morgan Kaufmann. Chapters 3–4 cover arc consistency and propagation algorithms in depth.
3. Janhunen et al. — [Knowledge Compilation for Product Configuration]((link.springer.com/redacted) Good treatment of BDD-based offline compilation.
4. OR-Tools CP-SAT — [Google OR-Tools documentation]((developers.google.com/redacted) The AddBoolOr, AddImplication, and AddAllowedAssignments primitives map directly to configuration constraints.

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

• expires on Apr 14, 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 #25299.