🧩 Constraint Solving POTD:Problem of the Day: Product Configuration Problem

[github-actions[bot]]

Problem Statement

The Task: You are an e-commerce platform helping customers configure custom products. A customer wants to build a laptop by selecting compatible components: a CPU, memory, storage, and graphics options.

Concrete Instance:

• CPUs: Intel i5, Intel i7, AMD Ryzen 5 (each has power requirements and costs)
• Memory: 8GB, 16GB, 32GB (each has different speed ratings)
• Storage: 256GB SSD, 512GB SSD, 1TB HDD (each has speed/cost trade-offs)
• GPU: Integrated (free), NVIDIA GTX 1650 (requires ≥65W PSU), RTX 3070 (requires ≥150W PSU)

Constraints:

• Total system power cannot exceed 500W
• If GPU is RTX 3070, CPU must be i7 and memory must be ≥16GB
• If memory is 32GB, storage must be SSD (not HDD)
• Budget cap: €2000

Goal: Find all valid configurations, or maximize performance within budget.

---

Why It Matters

E-Commerce & Personalization: Product configurators power millions of online purchases daily—from laptops to cars to cloud services. Invalid configurations waste customer time and increase support costs.

Supply Chain & Manufacturing: Factories must validate customer orders against component availability, assembly constraints, and regulatory requirements before production.

Configuration Management: Cloud platforms, software licenses, and custom manufacturing all use constraint solvers to check compatibility and generate valid configurations efficiently.

---

Modeling Approaches

Approach 1: Constraint Programming (CP)

Paradigm: Explicit decision variables with constraints over discrete domains.

Key Variables:

• cpu ∈ {i5, i7, ryzen5}
• memory ∈ {8, 16, 32} (in GB)
• storage ∈ {ssd256, ssd512, hdd1tb}
• gpu ∈ {integrated, gtx1650, rtx3070}

Constraints:

• Power: power(cpu) + power(gpu) ≤ 500
• GPU-CPU compatibility: gpu = rtx3070 ⟹ cpu = i7
• GPU-Memory compatibility: gpu = rtx3070 ⟹ memory ≥ 16
• Storage-Memory compatibility: memory = 32 ⟹ storage ∈ {ssd256, ssd512}
• Budget: cost(cpu) + cost(memory) + cost(storage) + cost(gpu) ≤ 2000

Strengths:

• Highly declarative; constraints map directly to business rules
• Excellent propagation: domain reduction happens early
• Natural handling of implication constraints

Trade-offs:

• Requires domain-specific solver (Choco, OR-Tools, Gecode)
• May need symmetry breaking for large product catalogs

Example Model (Pseudo-code)

variables:
  cpu ∈ {i5, i7, ryzen}
  memory ∈ {8, 16, 32}
  storage ∈ {ssd256, ssd512, hdd}
  gpu ∈ {integrated, gtx1650, rtx3070}

constraints:
  power[cpu] + power[gpu] ≤ 500
  (gpu = rtx3070) ⟹ (cpu = i7)
  (gpu = rtx3070) ⟹ (memory ≥ 16)
  (memory = 32) ⟹ (storage ≠ hdd)
  cost[cpu] + cost[memory] + cost[storage] + cost[gpu] ≤ 2000

objective:
  maximize performance[cpu] + performance[gpu]

Approach 2: SAT Encoding

Paradigm: Boolean variables and clauses; configuration as a satisfiability problem.

Key Variables:

• For each component type and option: binary variable (e.g., x_i7 = true iff CPU is i7)
• Additional Boolean variables for auxiliary constraints

Constraints (as CNF clauses):

• Exactly-one encoding: (x_i5 ∨ x_i7 ∨ x_ryzen) ∧ (¬x_i5 ∨ ¬x_i7) ∧ ...
• Implication: (gpu_rtx3070) ⟹ (cpu_i7) becomes ¬gpu_rtx3070 ∨ cpu_i7
• Numeric constraints via Tseitin encoding or direct clausal reasoning

Strengths:

• Highly optimized SAT solvers (MiniSat, CaDiCaL) available
• Proves unsatisfiability definitively
• Scales well to large, complex configurations

Trade-offs:

• Numeric constraints (power ≤ 500) are awkward to encode; requires conversion to 0-1 form
• Less natural domain modeling; loses structure

---

Key Techniques

1. Domain Reduction via Constraint Propagation

Arc consistency (AC-3) or bounds consistency algorithms eliminate impossible values early. For instance, if gpu = rtx3070 is assigned, propagators immediately reduce cpu domain to {i7} and memory to {16, 32}, pruning the search tree before branching.

2. Implication and Channeling Constraints

Configuration problems often encode as "if component A is chosen, then component B must satisfy property X." Global constraints like element() or table constraints let solvers reason about these dependencies efficiently, rather than posting many individual clauses.

3. Symmetry Breaking and Decomposition

In large product catalogs with multiple similar options, symmetry breaking reduces redundant search. Alternatively, decompose the problem: first validate feasibility (does any valid config exist?), then optimize (find best config), rather than interleaving both.

---

Challenge Corner

Open Question: Suppose the product catalog grows to 100 CPUs, 50 memory SKUs, and 30 GPU options. A naive model would have 100 × 50 × 30 × ... = millions of implicit configurations to explore.

• How would you use lazy constraint generation to avoid explicitly enumerating all options?
• Can you exploit hierarchical structure (e.g., component families, performance tiers) to model efficiently?
• What happens if you add real-time stock constraints that change throughout the day?

---

References

1. Rossi, F., van Beek, P., & Walsh, T. (Eds.). (2006). Handbook of Constraint Programming. Elsevier. — Comprehensive reference on CSP theory and practice; Chapter on applications covers configuration extensively.

2. Hurley, B. & O'Sullivan, B. (2014). "Towards a Unified Framework for Configuration." AI Magazine, 35(3). — Surveys configuration as a CSP specialization; discusses interactive solvers and preference handling.

3. Junker, U. (2006). "Configuration." Handbook of Constraint Programming, Chapter 22. — Focused treatment of configuration problems, interactive solvers, and repair strategies.

4. Blogpost: "Constraint Programming for Product Configuration." Available at constraint-programming-tutorial.com (example; verify for real resources). — Practical guide to modeling e-commerce configurators using open-source CP tools.

---

Tomorrow: We'll explore Satisfiability (SMT) — extending SAT with theories like linear arithmetic to handle even richer problem domains!

Generated by 🧩 Constraint Solving — Problem of the Day · haiku45 27.8K · ◷

• expires on Jun 5, 2026, 12:31 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 #35909.