🧩 Constraint Solving POTD:Problem of the Day: Product Configuration with Compatibility Constraints

[github-actions[bot]]

Problem Statement

A bicycle maker lets customers choose five components. Each option has a price:

Component	Options (price)
Frame	S (300), M (350), L (420)
Wheels	W26 (80), W29 (120)
Brakes	Rim (40), Disc (110)
Suspension	None (0), Front (150), Full (400)
Drivetrain	Single (60), Double (90)

Compatibility rules:

• C1: Small frames (S) only take 26-inch wheels (W26).
• C2: Full suspension needs disc brakes and cannot go on an S frame.
• C3: Front suspension needs disc brakes.
• C4: A double drivetrain needs disc brakes.
• C5: Customers buy these for trails, so None suspension is not allowed.

Input: the option prices, the compatibility rules, and the mandatory-suspension requirement above.
Output: one option per component that satisfies every rule, with minimal total price.

Task: pick one option per component so that all rules hold and the total price is minimal. The product space has 3 × 2 × 2 × 3 × 2 = 72 configurations. Brute force finds 18 valid ones, and the optimum costs 700: S, W26, Disc, Front, Single (300 + 80 + 110 + 150 + 60).

Why It Matters

• Sales configurators (cars, PCs, bicycles) must reject unbuildable orders while still letting the customer see every valid option.
• Bill-of-materials validation in manufacturing ERP systems uses the same rules to catch incompatible parts before production.
• Telecom and network equipment configuration selects compatible cards, chassis, and power modules, often at scale.

Modeling Approaches

1. Finite-domain CP (MiniZinc-style)

• Variables: one finite-domain variable per component (f, w, b, s, d).
• Constraints: each rule becomes an implication, e.g. s = Full → (f ≠ S ∧ b = Disc).
• Objective: minimize the sum of per-option prices.
• Trade-off: rules read almost like the English specification. Propagation prunes domains early, but a cost objective needs branch-and-bound on top.

Example Model (MiniZinc-style pseudo-code)

enum Frame = {S, M, L};   enum Wheels = {W26, W29};
enum Brakes = {Rim, Disc}; enum Susp = {None, Front, Full};
enum Drive = {Single, Double};
var Frame: f;  var Wheels: w;  var Brakes: b;
var Susp: s;   var Drive: d;

constraint f = S -> w = W26;                  % C1
constraint s = Full -> (f != S /\ b = Disc);  % C2
constraint s = Front -> b = Disc;             % C3
constraint d = Double -> b = Disc;            % C4
constraint s != None;                         % C5

var int: cost = price_f[f] + price_w[w] + price_b[b]
              + price_s[s] + price_d[d];
solve minimize cost;

2. Binary MIP (one-hot encoding)

• Variables: x_o ∈ {0,1} for each option o, with Σ_{o ∈ C} x_o = 1 for each component C.
• Constraints: every rule is linear over the binaries, e.g. x_Full ≤ 1 − x_S (C2), x_Full ≤ x_Disc (C2), x_Front ≤ x_Disc (C3), x_None = 0 (C5).
• Objective: minimize Σ_o p_o · x_o.
• Trade-off: the LP relaxation gives a lower bound for pruning, and the model suits cost-driven optimization. The encoding is less readable, and rules with many alternatives need extra variables.

A third option, a pure SAT encoding with clauses plus a cardinality/PB objective, works well for enumerating all valid configurations, but it is weaker for finding the cheapest one.

Key Techniques

1. Table and implication propagation. Once f = S is fixed, C1 and C2 remove W29 and Full from the other domains immediately, shrinking the search before any branching happens.
2. Cost-bounded branch-and-bound. A naive lower bound (the cheapest option in each component, ignoring the rules C1–C4 but keeping C5) gives 300 + 80 + 40 + 150 + 60 = 630. That bound is loose because Rim brakes conflict with suspension. Once s = Front is propagated, C3 forces Disc, and the bound becomes exact at 700. Searching cheapest-first with this bound prunes most of the 72 leaves.
3. Explanations for interactive use. In a live configurator, when a user picks Full on an S frame, the solver should explain which rule (C2) blocks the choice. Conflict-driven learning or minimal unsatisfiable subsets produce these messages.

Challenge Corner

• Add weights. Give each option a weight and cap the bike at 14 kg. Does the cheapest valid bike change? Which constraint becomes the bottleneck?
• Pareto front. Instead of one cheapest bike, find all configurations that are non-dominated in (price, weight). How would you enumerate them with a CP or MIP solver?
• Fewer variables. Can the one-hot MIP be shrunk by merging Front and Full into a single "has suspension" variable plus a type? What do you lose in propagation strength?

References

• Rossi, F., van Beek, P., & Walsh, T. (eds.), Handbook of Constraint Programming, Elsevier, 2006. Chapters on modeling and global constraints cover table constraints and propagation.
• Felfernig, A., Hotz, L., Bagley, C., & Tiihonen, J., Knowledge-Based Configuration: From Research to Business Success, Morgan Kaufmann, 2014. Covers configuration as a constraint problem in industry.
• MiniZinc documentation: (docs.minizinc.dev/redacted) Reference for the modeling language used above.
• Google OR-Tools CP-SAT solver documentation: (developers.google.com/redacted) Covers CP-SAT and its objective handling.

Generated by 🧩 Constraint Solving — Problem of the Day · copilot · routed: haiku55 xhigh · ~3 AIC · ⌖ ~2 AIC · ⊞ 4.1K · ◷

• expires on Nov 18, 2026, 3:31 AM UTC-08:00

[github-actions[bot]]

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

A newer discussion is available at Discussion #77134.