Constraint Solver Research

Status

Research completed 2026-04-10. Recommendation: opt-rb with HiGHS backend for MVP, upgrade path to or-tools CP-SAT if needed.

Problem Summary

The Meal Plan Generator describes a constraint satisfaction + optimization problem:

• Variables: Binary assignments — does food F go in slot S? (5–15 foods × 42–90 slots = 750–1,350 variables)
• Hard constraints: Per-category washout windows (2–4 days between same-category foods)
• Soft constraints: ≥5 exposures per food, pairwise decorrelation, temporal distribution across the plan window
• Multi-category foods create overlapping washout windows that interact non-obviously

This is a small problem by optimization standards. Modern solvers handle it in under a second.

Approaches Evaluated

1. Greedy Heuristic + Simulated Annealing (Pure Ruby)

Iterate chronologically, assign foods that don’t violate washouts, prioritize under-exposed foods. Then run SA swaps to optimize soft constraints.

• Pros: Zero dependencies, ~300 lines of Ruby, always returns something
• Cons: No optimality guarantee, can’t tell you which constraints to relax when they conflict
• Verdict: Viable for a throwaway POC, but opt-rb is barely more work and gives better results

2. opt-rb with HiGHS Backend ⭐ Recommended for MVP

opt-rb is Andrew Kane’s solver-agnostic convex optimization gem. Clean Ruby DSL for variables, constraints, and objectives. Delegates to pluggable backends.

HiGHS is the recommended backend — MIT licensed, handles LP/QP/MIP, actively maintained. The meal plan problem formulates naturally as a Mixed Integer Program (MIP) with binary decision variables.

# Example: binary variable per food-slot assignment
x = {}
foods.each do |food|
  slots.each do |slot|
    x[[food, slot]] = Opt::Binary.new("#{food}_#{slot}")
  end
end
 
prob = Opt::Problem.new
 
# Hard constraint: at most 1 food from category in any washout window
categories.each do |cat|
  window = cat.washout_days * 3
  (0..total_slots - window).each do |start|
    cat_vars = cat.foods.flat_map { |f|
      (start...start + window).map { |s| x[[f, s]] }
    }
    prob.add(cat_vars.sum <= 1)
  end
end
 
# Soft constraint: minimize exposure shortfall
shortfall_vars = foods.map do |food|
  slots.map { |s| x[[food, s]] }.sum
end
# ... add penalty terms to objective
 
prob.minimize(total_penalty)
prob.solve(solver: :highs, time_limit: 2)

• Pros: Clean Ruby API, MIT license (HiGHS), provably optimal solutions, time-limit support, same author as or-tools gem so consistent ergonomics
• Cons: MIP requires linearizing logical constraints (more verbose than CP-SAT). No anytime behavior — returns optimal or infeasible, not “best found so far.” No built-in solution enumeration (can’t easily get top-3 plans).
• Verdict: Best balance of simplicity, correctness, and dependency weight for MVP

3. or-tools CP-SAT

or-tools exposes Google’s CP-SAT solver — a hybrid combining SAT, constraint propagation, LP relaxation, and large neighborhood search. ~195K downloads, 538 commits, actively maintained.

CP-SAT’s sliding-window constraints and interval variables are more natural for scheduling than MIP linearizations.

model = ORTools::CpModel.new
# Boolean variables, direct constraint syntax
model.add(ORTools::LinearExpr.sum(window_vars) <= 1)
# Anytime: returns best-so-far even if time limit hit

• Pros: Provably optimal, anytime behavior (always returns best-so-far), solution callbacks for enumerating alternatives, built-in scheduling primitives (add_no_overlap, interval variables)
• Cons: Heavier native extension (longer compile on install), larger dependency footprint. Overkill for MVP problem size.
• Verdict: Clear upgrade path if opt-rb hits limitations. Same author — migration is straightforward.

4. ILP via ruby-cbc

Wrapper around COIN-OR CBC solver. Known crash when called from web servers on macOS. EPL-2.0 license (copyleft-adjacent). No advantage over opt-rb + HiGHS.

Verdict: Skip.

5. Backtracking + Constraint Propagation (AC-3, MAC)

Feasibility-only — finds a solution but doesn’t optimize. Ruby CSP gems (csp-solver, winston) are abandoned since ~2014. Would need to hand-roll.

Verdict: Wrong paradigm. We need optimization, not just satisfiability.

6. Z3 Ruby Bindings

Memory leaks, explicitly warns against long-running processes. Dealbreaker for Rails.

Verdict: Skip.

Comparison Table

Approach	Code complexity	Solution quality	Soft constraints	Graceful degradation	Dependencies
Greedy + SA	~300 LOC	Good, no guarantee	Penalty function	Always returns something	None
opt-rb + HiGHS	~250 LOC	Provably optimal	Weighted objective	Optimal or infeasible	opt-rb, highs
or-tools CP-SAT	~250 LOC	Provably optimal	Weighted objective	Anytime best-so-far	or-tools (heavy)
ruby-cbc	~400 LOC	Provably optimal	Needs linearization	Optimal or infeasible	ruby-cbc (buggy)
Backtracking	~600 LOC	Feasible only	Poor	Fails on infeasible	None

Competitive Landscape

No existing app automates food sensitivity reintroduction scheduling with temporal washout constraints:

• Eat This Much — constraint satisfaction for calorie/macro targets, no temporal dimension, no washout awareness
• Monash FODMAP app — gold standard for FODMAP guidance, reintroduction module used by thousands of users, but scheduling is entirely manual
• Clinical protocols (FODMAP, AIP, Six-Food Elimination) define precise temporal structures (3-day challenges, 3–5 day washouts) that map perfectly to constraint programming, but no tool automates the scheduling
• Open-source meal planners — several use LP for single-day nutritional optimization or genetic algorithms for multi-day plans, but none handle multi-category washout periods

This is a genuine product gap.

Implementation Roadmap

Phase 1: MVP with opt-rb + HiGHS

Build a MealPlanSolver service object behind the same interface as Meal Plan Generator. Model as MIP with binary variables. Use time_limit: 2 so the endpoint never blocks.

Key modeling decision: represent meal slots as integers (day * 3 + meal_index) rather than nested day/meal structures. This linearizes the time dimension, making washout constraints simple arithmetic. Convert back to dates at the presentation layer.

Handle infeasibility gracefully: if prob.solve returns infeasible, relax soft constraints iteratively (reduce MIN_EXPOSURES from 5 → 4 → 3) until a solution is found. Report which constraints were relaxed.

Phase 2: Upgrade to CP-SAT (if needed)

Add gem 'or-tools' alongside opt-rb. Build CpSatMealPlanSolver implementing the same interface. Benefits: anytime behavior, solution enumeration (top 3–5 plans for user choice), warm-starting from previous plan when suspects change.

Phase 3: Conditional branching

If a user reports symptoms after a challenge, re-solve the remaining schedule with the triggering food’s washout period extended. CP-SAT’s add_hint can seed with the existing plan for faster convergence.

References

• opt-rb gem — solver-agnostic optimization DSL
• highs-ruby gem — HiGHS solver bindings
• or-tools-ruby gem — Google OR-Tools bindings (CP-SAT, GLOP, routing)
• Meal Plan Generator — the spec this solver implements
• Washout Windows — washout duration rationale
• Issue 1 Meal Plan Generator Constraint Solver Complexity — issue tracking