🧩 Constraint Solving POTD:Problem of the Day: Constraint-Based Recommendation Systems

[github-actions[bot]]

Problem Statement

A constraint-based recommendation system aims to recommend personalized product configurations or service bundles that satisfy both customer preferences and system constraints. Given a customer profile with desired features, budget, and compatibility requirements, find a feasible recommendation that optimizes user satisfaction.

Concrete Instance

Imagine a streaming service customer wants to build their "perfect subscription bundle":

• Features available: Basic Plan, Premium Add-on, Sports Add-on, Documentaries Add-on, Simultaneous Streams (1, 2, or 4), Offline Download Support
• Constraints:
  • Premium Add-on requires at least the Basic Plan ($9.99/month)
  • Sports Add-on incompatible with Basic Plan alone; requires Premium ($5/month extra)
  • 4 Simultaneous Streams requires Premium Add-on ($3/month extra)
  • Total monthly budget: $18 max
  • Must include at least one add-on
• Customer preferences (ranked):
  1. Support 2+ simultaneous streams
  2. Watch sports content
  3. Save cost (prefer lower budget)
  4. Offline capability

Goal: Find a configuration that respects constraints and maximizes preference satisfaction.

Input/Output Specification

• Input:
  • Feature catalog (features, costs, compatibility rules, conflicts)
  • Customer budget and preference weights
  • Business constraints (availability, mutual exclusions, bundle requirements)
• Output:
  • A feasible configuration (subset of features satisfying all hard constraints)
  • Optimality score (satisfaction with respect to preferences)

Why It Matters

E-commerce Product Bundling: Online retailers use constraint-based recommendation to suggest product bundles (laptops with matching peripherals, software with required licenses) that fit customer budgets and compatibility rules.

Telecommunications: Telecom providers must recommend network plans, add-ons, and devices respecting service area availability, compatibility (e.g., phone ↔ SIM card ↔ network type), and subscriber financial limits.

Healthcare & Insurance: Configuration of insurance plans and add-ons must obey coverage policies, regulatory constraints, and pre-existing conditions while optimizing benefit fit and cost.

Manufacturing & Engineering: Configuration of customizable products (cars, computers, industrial systems) demands satisfaction of technical compatibility constraints alongside customer budget and performance preferences.

Modeling Approaches

Approach 1: Constraint Programming (CP)

Key idea: Model feature selection and constraints explicitly using binary variables.

Decision Variables:
  feature[i] ∈ {0, 1}   for each available feature i
  satisfaction ∈ R       aggregated preference score

Constraints (Hard):
  ∀ compatibility rule (f1, f2): 
    if incompatible(f1, f2) then feature[f1] + feature[f2] ≤ 1
  
  ∀ prerequisite (child, parent):
    if required(child, parent) then feature[child] ≤ feature[parent]
  
  cost(configuration) = Σ cost[i] × feature[i] ≤ budget
  
  min_addons: Σ feature[add-on] ≥ 1

Objective (Soft):
  maximize Σ preference_weight[i] × feature[i]

Trade-offs: Direct, intuitive encoding; strong propagation via arc consistency; scales well for moderate feature sets (50–100 features) but exponential in worst case. Propagation rules can detect infeasibility early.

Approach 2: Integer Linear Programming (MIP)

Key idea: Model recommendation as a 0–1 integer program with linear constraints and objective.

Maximize:
  Σ w[i] × x[i]  (preference satisfaction)

Subject to:
  Σ cost[i] × x[i] ≤ Budget
  
  x[i] + x[j] ≤ 1  for all incompatible pairs (i, j)
  
  x[child] ≤ x[parent] for all prerequisites
  
  x[i] ∈ {0, 1} for all features

Trade-offs: Easily handled by commercial solvers (CPLEX, Gurobi) with branch-and-cut; linear relaxation provides dual bounds; scales to hundreds of features. Requires encoding preferences as scalar weights, less flexible for complex preference logic.

Approach 3: Local Search / Meta-heuristic

Key idea: Start with a feasible random configuration; iteratively swap or toggle features to improve satisfaction while maintaining feasibility.

procedure LocalSearchRecommendation(budget, preferences):
  current ← randomFeasibleConfiguration()
  best ← current
  
  repeat for max_iterations:
    neighbor ← current
    for each feature not in neighbor:
      if canAdd(feature, neighbor, budget):
        neighbor ← add(feature)
        break  // single-move neighborhood
    
    if satisfaction(neighbor) > satisfaction(best):
      best ← neighbor
      current ← neighbor
    else if random() < acceptance_prob:
      current ← neighbor  // diversify
    
  return best

Trade-offs: Fast, practical for large feature sets; no optimality guarantee; sensitive to initialization and parameter tuning; good for interactive applications where response time matters.

Key Techniques

1. Global Constraints for Compatibility

Rather than encoding all pairwise incompatibilities, use higher-level constraints:

• atmost_one(S): At most one feature from set S can be selected (models mutual exclusion groups).
• cumulative: For feature bundles with capacity constraints (e.g., simultaneous streams).
• element / table: Hard-code valid configurations as allowed tuples, prune infeasible combinations early.

2. Symmetry Breaking & Redundant Constraints

• Order features in a canonical way to eliminate symmetric solutions.
• Add redundant constraints that tighten the relaxation and aid propagation. E.g., if features form a preference hierarchy, add implied inequalities: x_premium ≥ x_sports_addon.

3. Variable & Value Ordering

• Most Constrained Variable (MCV): Branch first on features that appear in many compatibility rules.
• Least Constraining Value (LCV): Try assigning features that maximize remaining flexibility.
• Preference Ordering: Prioritize high-weight features; prune dominated branches early.

Challenge Corner

Question 1: How would you encode a soft constraint like "prefer to bundle feature A with feature B, but it's not required" into a CP model? What happens if you use a weighted cost in the objective instead of a hard constraint?

Question 2: Real recommendation systems often involve optional and recommended add-ons with variable discounts. How would you extend the model to handle:

• Dynamic pricing (bundle discounts: "any 3 add-ons → 15% off")?
• Temporal constraints ("Sports Add-on only available during sports season")?

Question 3: Suppose you need to recommend bundles to 10,000 users per day. Would CP, MIP, or local search scale better? What hybrid approach would combine strength of multiple paradigms?

References

1. van Beek, P., & Walsh, T. (2006). "Constraint Satisfaction and Constraint Logic Programming." In Handbook of Knowledge Representation, pp. 167–207. Covers CSP modeling and propagation fundamentals.

2. Régin, J.-C. (1994). "A Filtering Algorithm for Global Cardinality Constraint." In CP'94. Classic paper on global constraint propagation; atmost_one and cumulative constraints derive from this work.

3. Gurobi or CPLEX Documentation: "Mixed Integer Linear Programming for Recommendation and Configuration." Practical solver guides with real product-configuration examples.

4. Hooker, J. N. (2012). Integrated Methods for Optimization (2nd ed.). Chapter on constraint programming + integer programming hybrids; excellent for understanding when each paradigm shines in recommendation scenarios.

---

Next challenge: Can you model a sports league scheduling problem with fairness and broadcast constraints?

Generated by 🧩 Constraint Solving — Problem of the Day · haiku45 · 10 AIC · ⌖ 20 AIC · ⊞ 5.5K · ◷

• expires on Aug 4, 2026, 4:09 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 #48869.