# Product Requirements Document: Deterministic Scheduling Solver

## Validation Checklist

- [x] All required sections are complete
- [x] No [NEEDS CLARIFICATION] markers remain
- [x] Problem statement is specific and measurable
- [x] Problem is validated by evidence (not assumptions)
- [x] Context -> Problem -> Solution flow makes sense
- [x] Every persona has at least one user journey
- [x] All MoSCoW categories addressed (Must/Should/Could/Won't)
- [x] Every feature has testable acceptance criteria
- [x] Every metric has corresponding tracking events
- [x] No feature redundancy (check for duplicates)
- [x] No contradictions between sections
- [x] No technical implementation details included
- [x] A new team member could understand this PRD

---

## Product Overview

### Vision

Give store managers the choice between a mathematically optimal constraint solver and an AI-powered scheduler, with plain-English explanations of every assignment decision, so they can generate trustworthy, provably-fair schedules in under a minute.

### Problem Statement

The existing AI Smart Scheduling system (Spec 026) relies entirely on OpenAI's language models to generate employee-to-shift assignments. While this works well in many cases, it has fundamental limitations:

1. **No optimality guarantee** - LLMs are generative models, not optimization engines. The AI cannot prove its schedule is the best possible arrangement, or even quantify how far from optimal it is. Industry research (Timefold, Soon.works) indicates LLM-generated schedules typically deviate 5-15% from optimal labor cost; this hypothesis will be validated by running both solvers on the same inputs and comparing results.

2. **Inconsistent constraint enforcement** - Despite 11 hard constraints in the system prompt and PHP post-validation (`AiScheduleOptimizer.parseAndValidateAssignments()`), the AI occasionally proposes assignments that violate availability windows or role qualifications, requiring server-side rejection and leaving shifts unfilled that could have been filled. The `parseAndValidateAssignments` method logs these rejections, providing evidence of the gap.

3. **Non-deterministic results** - Running the same generation twice with identical inputs can produce different schedules. This makes it impossible to A/B test optimization strategies or build manager confidence through predictable behavior.

4. **No infeasibility diagnosis** - When the AI can't fill all shifts, it simply leaves them empty with a generic note. It cannot explain *which specific constraints conflict* or *what the manager could change* to make the schedule feasible.

5. **Opaque reasoning** - The AI provides per-assignment "reasoning" strings, but these are generated text, not derived from actual optimization metrics. Managers cannot verify whether "Casey was chosen for hours fairness" is actually true.

6. **Cost per run** - Each AI generation consumes OpenAI API tokens ($0.50-$2.00 per run depending on model and prompt size). A deterministic solver running locally has zero marginal cost.

### Value Proposition

The Deterministic Scheduling Solver complements the existing AI scheduler by offering:

- **For Managers:** A "Math Optimizer" option that guarantees every constraint is satisfied, produces provably optimal or near-optimal schedules, and provides truthful explanations derived from actual optimization data - not generated text
- **For Owners:** Zero-cost schedule generation (no API tokens), deterministic reproducibility, and measurable quality metrics (optimality gap percentage)
- **For the Platform:** A quality benchmark to evaluate AI scheduler performance, a fallback when OpenAI is unavailable, and a foundation for future demand-based scheduling

---

## User Personas

### Primary Persona: Store Manager

- **Demographics:** 25-45 years old, manages a buy/sell retail store, moderate technical proficiency, creates weekly schedules
- **Goals:**
  - Generate a schedule that satisfies all constraints without manual checking
  - Understand *why* specific employees were assigned to specific shifts
  - Compare optimization approaches to pick the best result
  - Get actionable advice when the schedule isn't perfect
- **Pain Points:**
  - AI scheduler sometimes violates constraints, requiring manual correction
  - Can't tell if the AI schedule is actually optimal or just "good enough"
  - AI reasoning feels like marketing copy, not verifiable logic
  - When shifts can't be filled, no guidance on what to change
  - Burning through the 5-run weekly limit trying different settings

### Secondary Persona: Store Owner

- **Demographics:** 30-60 years old, focused on profitability and operational efficiency
- **Goals:**
  - Minimize labor cost with mathematical confidence
  - Understand the dollar impact of scheduling decisions
  - Reduce dependency on external API services and their costs
  - Have a reliable scheduling fallback if AI service is down
- **Pain Points:**
  - Can't verify AI is actually minimizing labor cost
  - OpenAI API costs add up across multiple stores
  - No way to benchmark schedule quality
  - Risk of AI service outage during critical scheduling windows

### Secondary Persona: System Administrator

- **Demographics:** Technical team member managing the BuyerKiosk platform
- **Goals:**
  - Reduce external API dependency and costs
  - Monitor solver performance and quality metrics
  - Maintain system reliability
- **Pain Points:**
  - OpenAI rate limits and outages affect scheduling availability
  - No local fallback for schedule generation
  - Can't benchmark or regression-test AI quality

---

## User Journey Maps

### Primary User Journey: Schedule Generation with Solver Selection

1. **Preparation:** Manager navigates to scheduling calendar for the target week. Ensures open shifts exist (via template or manual creation).

2. **Solver Selection:** Manager clicks "Generate Schedule" button. A configuration dialog appears with:
   - **Solver type selector:** "Math Optimizer" or "AI Scheduler" (two clear options)
   - Optimization priority selector (same 6 priorities for both: labor cost, hours fairness, seniority, position coverage, minimize overtime, employee preferences)
   - Custom instructions text field (available for AI mode; hidden for Math mode since solver doesn't use free text)
   - Owner inclusion toggles

3. **Generation:** Manager selects "Math Optimizer" and clicks "Generate"
   - System shows progress indicator with solver status
   - Math Optimizer completes in 5-60 seconds
   - Result appears in preview panel

4. **Review:** Manager sees the optimized schedule with:
   - Each assignment with accept/reject checkbox
   - Per-assignment "Why this assignment?" expandable explanation (LLM-generated from solver data)
   - Schedule quality scorecard: total labor cost, hours distribution, constraint satisfaction, optimality status
   - Improvement suggestions panel (LLM-generated from solver analysis)

5. **Refinement:** Manager reviews assignments
   - Can reject specific assignments - solver's remaining assignments stay valid
   - Can ask "Why not [employee] for [shift]?" and get a counterfactual explanation
   - Sees unfilled shifts with specific reasons (infeasibility explanation)

6. **Application:** Manager clicks "Apply Selected Assignments"
   - Accepted assignments committed to schedule
   - Rejected/unfilled shifts remain open

7. **Post-Processing:** Manager handles remaining gaps manually or tries AI Scheduler for comparison

### Secondary User Journey: Comparing Solver vs. AI Results

1. **First Generation:** Manager generates a schedule using "Math Optimizer"
2. **Comparison Trigger:** Manager wants to see what the AI would suggest differently
3. **Second Generation:** Manager clicks "Generate Schedule" again, selects "AI Scheduler" with same priorities
4. **Comparison View:** System shows a comparison scorecard:
   - Side-by-side metrics: labor cost, fairness score, coverage, constraint violations
   - Key differences highlighted ("AI assigned Casey to Saturday, Optimizer assigned Hellen - AI costs $45 more")
   - LLM-generated summary of the major differences between the two approaches
5. **Selection:** Manager picks the preferred result or cherry-picks assignments from either

### Secondary User Journey: Infeasibility Resolution

1. **Trigger:** Manager generates a schedule and the solver reports some shifts cannot be filled
2. **Diagnosis:** System shows which shifts are unfilled and *why* they can't be filled:
   - "Sunday closing requires a Shift Lead (Role 3+), but both available Shift Leads (Ryan and Kay) are already at their 40-hour maximum"
   - Presented as a clear problem statement, not a generic error
3. **Resolution Options:** LLM presents 2-3 actionable options:
   - "Option 1: Allow Ryan to work 42 hours this week (+$65 overtime)"
   - "Option 2: Move Ryan's Thursday shift to free up Sunday capacity"
   - "Option 3: This shift remains open for manual assignment or employee claiming"
4. **Action:** Manager selects an option or manually resolves the gap

### Secondary User Journey: Schedule Explanation for Team Communication

1. **Trigger:** Manager has applied a schedule and wants to communicate it to the team
2. **Action:** Manager clicks "Explain This Schedule" button
3. **Output:** LLM generates a plain-English summary:
   - Overview of the week's coverage
   - Key decisions explained ("Casey has more weekend shifts this week because she requested extra hours")
   - Any notable patterns ("Three people are close to overtime - please monitor hours mid-week")
4. **Use:** Manager copies/shares this summary when publishing the schedule

---

## Feature Requirements

### Must Have Features

#### Feature 1: Deterministic Constraint Solver

- **User Story:** As a store manager, I want to generate employee assignments using a mathematical optimizer so that I get provably optimal schedules that satisfy all constraints
- **Acceptance Criteria:**
  - [ ] Solver enforces the same hard constraints as the existing AI system's `AiScheduleOptimizer.parseAndValidateAssignments()` and `AiPromptBuilder` constraints 1-11:
    1. Only assigns to existing open shifts (never creates shifts)
    2. Respects existing assigned shifts (never reassigns)
    3. Enforces role qualifications (employee role <= shift minRoleId)
    4. Opening/closing shifts (identified by minRoleId <= 3) require Role <= 3
    5. Respects employee availability windows (day + start/end time)
    6. Respects approved time-off requests
    7. Considers current pay period hours for overtime (weekly 40hr + daily 8hr thresholds)
    8. One shift per employee per day maximum
    9. No overlapping shifts for the same employee
    10. Maximum 5 shifts per employee per week
    11. hoursMax is a hard cap (never exceeded)
  - [ ] Solver treats as soft constraints (same as AI system): hoursRequested (target), hoursMin (try to meet), fair distribution
  - [ ] Solver handles overnight shifts (shifts spanning midnight) correctly
  - [ ] Solver produces optimal or near-optimal solutions, reporting optimality gap as a percentage (0% = proven optimal, >0% = gap between best found and theoretical lower bound)
  - [ ] Solver completes within 60 seconds for up to 30 employees and 150 shifts
  - [ ] Solver returns explicit status: OPTIMAL (proven best), FEASIBLE (good solution, time limit reached), or INFEASIBLE (hard constraints cannot all be satisfied)
  - [ ] When INFEASIBLE, solver identifies the specific conflicting constraints (Irreducible Infeasible Subset)
  - [ ] Same inputs always produce the same output (deterministic via fixed random seed)
  - [ ] Solver runs locally with zero external API cost
  - [ ] Manager recurring schedules and owner schedules are treated as locked (visible for labor cost calculation but not modifiable)
  - [ ] Owners excluded from assignment pool by default unless explicitly toggled on in generation dialog

#### Feature 2: Solver Type Selection

- **User Story:** As a store manager, I want to choose between "Math Optimizer" and "AI Scheduler" so that I can use the approach that best fits my needs
- **Acceptance Criteria:**
  - [ ] Generation dialog presents two solver options: "Math Optimizer" and "AI Scheduler"
  - [ ] Each option has a brief description of its strengths
  - [ ] Math Optimizer: "Guaranteed optimal. Fastest. No API cost. Best for constraint-heavy schedules."
  - [ ] AI Scheduler: "Creative solutions. Handles nuance. Uses custom instructions. Best for complex preferences."
  - [ ] Manager's last-used solver type is remembered as default
  - [ ] Both solvers use the same 6 optimization priorities
  - [ ] Both solvers share the same preview/accept/reject UI
  - [ ] Rate limiting (5 runs/pay-week) only applies to AI Scheduler, not Math Optimizer

#### Feature 3: Optimization Priority Matching

- **User Story:** As a store manager, I want the Math Optimizer to support the same priorities as the AI Scheduler so that I can compare results fairly
- **Acceptance Criteria:**
  - [ ] Supports all 6 priorities defined in `AiDefaultPrefsService::AVAILABLE_PRIORITIES`: position_coverage, labor_cost, hours_fairness, seniority, minimize_overtime, employee_preferences
  - [ ] NOTE: The AI Scheduler controller validation (`AiSchedulingApiController` line 208) currently only accepts 4 of these 6. This spec requires updating that validation to accept all 6, ensuring both solvers share the complete priority set.
  - [ ] Priorities are ranked by the manager via drag-and-drop reordering (same UI as AI Scheduler)
  - [ ] Higher-ranked priorities have exponentially stronger influence: weight = 10^(6 - rank). Rank 1 = weight 100,000; Rank 6 = weight 1. This ensures clear priority separation.
  - [ ] Priority settings are shared between solvers (changing priorities applies to both)
  - [ ] Default priority order is remembered per-store via existing `aiScheduleDefaultPrefs` in stores table

#### Feature 4: LLM-Powered Assignment Explanations

- **User Story:** As a store manager, I want plain-English explanations of why each employee was assigned to each shift so that I can trust the optimizer's decisions
- **Acceptance Criteria:**
  - [ ] Every assignment has an expandable "Why this assignment?" section
  - [ ] Explanations are generated by the LLM using structured data from the solver (not invented reasoning)
  - [ ] Each explanation includes the top 2-3 factors that drove the assignment
  - [ ] Explanations reference specific constraints: "Casey was assigned because she's one of 3 qualified employees available, and has 5 fewer hours than the team average this week"
  - [ ] Explanations include counterfactual context when relevant: "Hellen was not assigned because she would exceed her 40-hour weekly limit"
  - [ ] Explanations are cached and displayed instantly (LLM call happens once at generation time, not per-click)
  - [ ] **Graceful degradation:** If OpenAI is unavailable, the system displays structured explanations derived directly from solver constraint data (e.g., "Factors: Role qualified, 5h below target hours, availability confirmed"). The solver result itself is never blocked by LLM availability.
  - [ ] When in fallback mode, a banner indicates "AI explanations temporarily unavailable - showing constraint summary"

#### Feature 5: LLM-Powered Improvement Suggestions

- **User Story:** As a store manager, I want actionable suggestions for improving my schedule so that I can optimize staffing over time
- **Acceptance Criteria:**
  - [ ] After generation, system displays 2-5 improvement suggestions
  - [ ] Suggestions are separated into two tiers:
    - Immediate actions (this week): "Swapping Casey's Friday and Paige's Saturday reduces overtime by 3 hours"
    - Longer-term improvements: "Cross-training one more employee as Shift Lead would eliminate your Sunday coverage gap"
  - [ ] Each suggestion has a clear action the manager can take
  - [ ] Suggestions are generated by the LLM analyzing solver output (binding constraints, slack, fairness metrics)
  - [ ] Suggestions update when the manager modifies the schedule (accepts/rejects assignments)
  - [ ] **Graceful degradation:** If OpenAI is unavailable, improvement suggestions section is hidden (not shown as empty). The solver result and scorecard remain fully functional without suggestions.

#### Feature 6: Infeasibility Explanation

- **User Story:** As a store manager, I want to understand why some shifts can't be filled and what I can do about it so that I'm not stuck with unexplained gaps
- **Acceptance Criteria:**
  - [ ] When solver returns INFEASIBLE or partially feasible, system explains which constraints conflict
  - [ ] Explanation is in plain English, not technical jargon: "Sunday closing needs a Shift Lead, but both available Shift Leads are at their hour limit"
  - [ ] System presents 2-3 specific resolution options as actionable cards
  - [ ] Each option states the tradeoff: "Allow overtime (+$65)" or "Reduce coverage (1 fewer shift)"
  - [ ] Manager can select a resolution option to re-run the solver with adjusted constraints
  - [ ] If no resolution is possible, system clearly states "This shift must be filled manually"

#### Feature 7: Schedule Quality Scorecard

- **User Story:** As a store manager, I want to see quality metrics for my generated schedule so that I can evaluate how good it is
- **Acceptance Criteria:**
  - [ ] Scorecard displays after every generation (both solver types):
    - Total weekly labor cost (dollars)
    - Hours distribution fairness: coefficient of variation (CV) of assigned-vs-requested hours across employees. Thresholds: High fairness (CV < 0.15), Medium (0.15-0.30), Low (CV > 0.30)
    - Coverage: X of Y shifts filled
    - Constraint violations: count (should be 0 for Math Optimizer)
    - Overtime hours: total and per-employee breakdown
  - [ ] Math Optimizer additionally shows: optimality status
    - "Optimal" when solver status = OPTIMAL (gap = 0%, proven best possible)
    - "Near-optimal (X% gap)" when solver status = FEASIBLE (gap = (best_bound - objective) / objective * 100)
    - Example: "Near-optimal (2.3% gap)" means the solution is within 2.3% of the theoretical best
  - [ ] Scorecard is visible in the preview panel before applying
  - [ ] When comparing two solver results, scorecard shows side-by-side with winner badges per metric (green badge = better value)

#### Feature 8: Solver Result Comparison

- **User Story:** As a store manager, I want to compare Math Optimizer and AI Scheduler results so that I can pick the better schedule
- **Acceptance Criteria:**
  - [ ] After generating with one solver, manager can generate with the other for the same week
  - [ ] Comparison view shows side-by-side scorecards with winner badges per metric
  - [ ] Key differences are highlighted: which assignments differ and why
  - [ ] LLM generates a 2-3 sentence summary of the major differences
  - [ ] Manager can select either result to apply (or cherry-pick from both in future phase)
  - [ ] Comparison data is logged for analytics (track which solver managers prefer)

### Should Have Features

#### Feature 9: "Why Not This Employee?" Counterfactual Query

- **User Story:** As a store manager, I want to ask "Why wasn't [employee] assigned to [shift]?" so that I can understand the optimizer's reasoning
- **Acceptance Criteria:**
  - [ ] Manager can click an unfilled shift or an assignment and ask "Why not [employee]?"
  - [ ] System provides a specific answer: "Jordan was not assigned to Saturday because assigning her would violate her 32-hour weekly maximum (currently at 30 hours, shift is 4 hours)"
  - [ ] Answer comes from solver constraint data, not LLM speculation
  - [ ] Multiple "why not" queries can be asked without re-running the solver

#### Feature 10: Schedule Summary for Team Communication

- **User Story:** As a store manager, I want a plain-English summary of the schedule I can share with my team so that everyone understands the week's plan
- **Acceptance Criteria:**
  - [ ] "Explain This Schedule" button available after applying a schedule
  - [ ] LLM generates a conversational summary covering: weekly overview, key decisions, fairness notes, potential concerns
  - [ ] Summary is copy-friendly (can be pasted into team chat or email)
  - [ ] Summary adjusts tone based on audience: brief for text message, detailed for email

#### Feature 11: Override and Re-optimize

- **User Story:** As a store manager, I want to lock specific assignments and have the optimizer work around them so that I maintain control while still getting optimization
- **Acceptance Criteria:**
  - [ ] Manager can mark any assignment as "locked" before re-generating
  - [ ] Solver treats locked assignments as fixed constraints
  - [ ] Re-generation optimizes only the unlocked assignments
  - [ ] Locked assignments are visually distinct in the preview

### Could Have Features

#### Feature 12: Constraint Weight Editor

- **User Story:** As a store manager, I want to fine-tune how important each optimization factor is so that the schedule reflects my specific store's priorities
- **Acceptance Criteria:**
  - [ ] Slider controls for adjusting relative weight of each priority
  - [ ] Preview updates reflect weight changes
  - [ ] Weight presets: "Minimize Cost", "Maximize Fairness", "Balanced"
  - [ ] Custom weight configurations can be saved per-store

#### Feature 13: Historical Quality Tracking

- **User Story:** As a store owner, I want to see how schedule quality has trended over time so that I can measure improvement
- **Acceptance Criteria:**
  - [ ] Dashboard shows weekly trends: labor cost, fairness score, coverage rate
  - [ ] Tracks which solver was used each week
  - [ ] Shows accept/reject rates by solver type
  - [ ] Highlights weeks where the Math Optimizer found a significantly better solution than AI

### Won't Have (This Phase)

- **Cherry-pick from both solvers** - Select individual assignments from different solver results (future enhancement)
- **Real-time re-optimization on drag** - Solver re-runs when manager drags an assignment to a different shift (future)
- **Multi-week batch optimization** - Optimize multiple weeks simultaneously considering cross-week constraints
- **Demand-based shift creation** - Solver suggests how many shifts to create (requires Feature 16 from Spec 026)
- **Conversational chat interface** - Free-form chat with the solver (structured UI is sufficient for V1)
- **Mobile solver access** - Math Optimizer available on web only for V1
- **Custom constraint definitions** - Manager-defined constraints beyond the standard 11 (future)
- **Solver-to-solver warm starting** - Using one solver's output to seed the other

---

## Detailed Feature Specifications

### Feature: Deterministic Constraint Solver (Core Feature)

**Description:** A mathematical constraint solver that takes the same inputs as the existing AI Scheduler (open shifts, employees, availability, time-off, hours preferences, roles, pay rates) and produces provably optimal employee-to-shift assignments using the OR-Tools CP-SAT constraint programming engine.

**Execution Model:**

The Math Optimizer uses the existing TaskEngine async job pattern (same as AI Scheduler) for consistency:

1. PHP dispatches a `SolverScheduleGenerationJob` to the TaskEngine `high` priority queue
2. The job calls the Python solver via subprocess (`proc_open` with JSON stdin/stdout)
3. On completion, the job passes solver results to OpenAI for LLM explanation generation (same `OpenAIClient` as AI Scheduler)
4. Results (assignments + explanations + scorecard) are stored in the existing `aiScheduleSuggestions` table (with a new `solverType` column: 'math' or 'ai')
5. Ably real-time notification is sent to the waiting client (same channel pattern: `solver-schedule-{typeNum}-{jobId}`)
6. The client receives the notification and loads the preview panel

This reuses all existing infrastructure: TaskEngine dispatch, Ably notifications, suggestion storage, and preview UI. The only new component is the Python subprocess call within the job.

**User Flow:**
1. Manager views calendar for target week with open shifts
2. Manager clicks "Generate Schedule"
3. Manager selects "Math Optimizer" from solver type selector
4. Manager configures priorities (same 6 as AI Scheduler)
5. Manager toggles owner inclusion
6. Manager clicks "Generate"
7. System dispatches a TaskEngine job (high priority queue)
8. Job gathers employee data (availability, time-off, hours, roles, pay rates) - same data gathering as AI Scheduler
9. Job calls Python solver subprocess with JSON problem data
10. Solver runs for 5-60 seconds, finding optimal assignments
11. Job passes solver output to OpenAI for LLM explanation generation
12. Job stores results in `aiScheduleSuggestions` and sends Ably notification
13. Client receives notification, loads preview with: assignments, explanations, scorecard, improvement suggestions
14. Manager reviews, accepts/rejects, and applies (same flow as AI Scheduler)

**Business Rules:**

- **Rule 1:** Math Optimizer enforces the same hard constraints as the AI Scheduler (from `AiPromptBuilder` constraints 1-11 and `AiScheduleOptimizer.parseAndValidateAssignments()`):
  1. Only assigns to existing open shifts (never creates shifts)
  2. Respects existing assigned shifts (never reassigns)
  3. Enforces role qualifications (employee role <= shift minRoleId)
  4. Opening/closing shifts (identified by minRoleId <= 3) require Role <= 3
  5. Respects employee availability windows (day of week + start/end time)
  6. Respects approved time-off requests (never schedules during approved time off)
  7. hoursMax is a hard cap (never exceeded)
  8. One shift per employee per day maximum
  9. No overlapping shifts for the same employee
  10. Maximum 5 shifts per employee per week
  11. Locked shifts (manager recurring, existing assigned) are immutable

- **Rule 2:** Soft constraints are modeled as weighted penalties in the objective function (these influence the solution quality but don't make it infeasible):
  - hoursRequested: target hours per employee (minimize deviation from target)
  - hoursMin: try to meet minimum hours (penalize when below)
  - Hours fairness: minimize coefficient of variation of assigned-vs-requested hours across employees
  - Labor cost: prefer lower-pay-rate employees when qualifications are equal
  - Seniority: prefer senior employees (lower role number) for preferred shifts
  - Overtime: penalize assignments that push employees past weekly/daily overtime thresholds
  - Employee preferences: honor stated shift preferences when possible
  - Fair distribution: before assigning a 4th or 5th shift, prefer employees with fewer shifts

- **Rule 3:** Priority ranking maps to penalty weights using exponential scaling: weight = 10^(6 - rank). Rank 1 priority gets weight 100,000; Rank 6 gets weight 1. This ensures clear priority separation without ambiguity.

- **Rule 4:** Math Optimizer has NO run limit (unlike AI Scheduler's 5/pay-week). Zero API cost means unlimited use.

- **Rule 5:** Results are deterministic - same inputs always produce the same output. This allows managers to confidently iterate on constraint settings.

- **Rule 6:** Solver reports solution quality:
  - OPTIMAL: proven best possible schedule
  - FEASIBLE: good schedule found but optimality not proven (time limit reached)
  - INFEASIBLE: impossible to satisfy all hard constraints

- **Rule 7:** When INFEASIBLE, solver identifies the minimal set of conflicting constraints (Irreducible Infeasible Subset) for LLM explanation

- **Rule 8:** LLM explanation calls use the same OpenAI infrastructure as the AI Scheduler but consume fewer tokens (structured data in, explanation out vs. full schedule generation)

- **Rule 9:** LLM explanation is optional - if OpenAI is unavailable, solver results display with structured data explanations instead of natural language

**Edge Cases:**

- **Solver timeout (60 seconds):** Return best feasible solution found so far with "Near-optimal" status and gap percentage. Never return nothing.
- **Zero open shifts:** Show message "No open shifts to optimize. Add shifts or load a template first."
- **Zero available employees:** All shifts remain unfilled. Infeasibility explanation: "No employees are available for the selected week."
- **All employees at max hours:** Shifts remain unfilled. Explanation includes which employees are at limit and by how much.
- **OpenAI unavailable for explanations:** Display solver results with structured explanations (constraint-based, not natural language). Show "AI explanations unavailable" banner. Schedule quality is unaffected.
- **Conflicting priorities:** Position coverage (keeping shifts filled) always takes precedence. Then follow manager's ranked priority order.
- **Employee added/removed between generation and apply:** Validate assignments at apply time. If an employee was deactivated, that assignment is skipped with a warning.
- **Shift modified between generation and apply:** Stale detection (same as AI Scheduler) - warn and require re-generation
- **Solver finds multiple optimal solutions:** Return the first found. Determinism guaranteed by fixed random seed and search parameters.
- **Overnight shifts spanning midnight:** Solver handles shifts where end time < start time (e.g., 10pm-6am). These count as one shift on the start date for one-shift-per-day constraint. Hours are correctly calculated across the midnight boundary. Existing `ConflictDetectionService` overnight logic is reused.
- **Pay-period boundary:** Overtime calculation considers hours already worked in the current pay period (from `workWeekStartDay` in store settings), not just the generated week. Partial week at period start/end is handled correctly.
- **Overlapping shift times:** Solver prevents assigning the same employee to shifts whose time ranges overlap, even if they're on the same calendar day. This is a hard constraint.
- **Employee preference data missing:** If `employee_preferences` is a ranked priority but no preference data exists for employees, the solver treats all preferences as neutral (weight = 0) and optimizes remaining priorities. No error shown.
- **Python subprocess crash/segfault:** Job catches non-zero exit codes and stderr output. Returns a clear error: "Schedule optimization failed. Please try again or use AI Scheduler." Job status set to 'failed' with error details logged.
- **Very large input (>30 employees, >150 shifts):** Solver still runs but may return FEASIBLE (not OPTIMAL) within the 60-second time limit. The gap percentage indicates solution quality. No hard rejection of large inputs.

---

## Success Metrics

### Key Performance Indicators

- **Adoption:** 50% of premium scheduling stores try Math Optimizer within 2 months of launch
- **Preference:** After trying both, 40% of managers prefer Math Optimizer for weekly scheduling (tracked by which solver's output they apply)
- **Quality:** Math Optimizer produces schedules with lower labor cost than AI Scheduler (hypothesis: 5-15% based on industry research; to be validated by comparison runs on production stores within first month)
- **Constraint Satisfaction:** 100% hard constraint satisfaction rate for Math Optimizer (vs. AI Scheduler's rate to be measured from `parseAndValidateAssignments` rejection logs)
- **Solve Time:** 95th percentile solve time under 30 seconds for stores with up to 30 employees
- **Explanation Usefulness:** 70% of managers expand at least one "Why this assignment?" explanation per session
- **Suggestion Action Rate:** 20% of improvement suggestions lead to a manager action (modify hours, adjust availability, etc.)
- **Cost Savings:** Average $50/month/store reduction in OpenAI API costs for stores that switch to Math Optimizer as primary

### Tracking Requirements

| Event | Properties | Purpose |
|-------|------------|---------|
| solver_generation_started | storeId, weekStart, solverType(math/ai), priorities[], includeOwners | Track solver preference |
| solver_generation_completed | storeId, solverType, duration, status(optimal/feasible/infeasible), proposedCount, unfilledCount, objectiveValue, optimalityGap | Measure quality and performance |
| solver_assignment_accepted | storeId, solverType, shiftId, employeeId | Track acceptance by solver type |
| solver_assignment_rejected | storeId, solverType, shiftId, employeeId | Identify per-solver rejection patterns |
| solver_result_applied | storeId, solverType, acceptedCount, rejectedCount, unfilledCount, totalLaborCost | Measure net value per solver |
| solver_comparison_viewed | storeId, mathCost, aiCost, mathFairness, aiFairness, chosenSolver | Track comparison behavior |
| solver_explanation_expanded | storeId, solverType, assignmentId | Measure explanation usefulness |
| solver_suggestion_actioned | storeId, suggestionType(immediate/longterm), action | Measure suggestion value |
| solver_infeasibility_shown | storeId, conflictCount, resolutionChosen | Track infeasibility handling |
| solver_why_not_queried | storeId, employeeId, shiftId | Measure counterfactual query usage |

---

## Constraints and Assumptions

### Constraints

- **Technology:** Solver engine (OR-Tools CP-SAT) requires Python 3.9+ runtime; PHP calls solver via `proc_open()` subprocess with JSON stdin/stdout. The Python script is self-contained with a `requirements.txt` (`ortools>=9.9`).
- **Deployment Requirements:**
  - Python 3.9+ must be installed on the server (verify via `python3 --version` in deployment checks)
  - OR-Tools package installed: `pip3 install ortools` (approximately 50MB)
  - Python script located at a known path (e.g., `userfrosting/solver/schedule_solver.py`)
  - Process isolation: subprocess runs with same user as PHP, no elevated privileges needed
  - Failure modes: If Python is missing or OR-Tools not installed, the Math Optimizer option is hidden from the UI with a log warning. AI Scheduler remains fully functional.
  - Version pinning: OR-Tools version pinned in `requirements.txt` to prevent breaking changes
- **Problem Size:** Solver is designed for stores with up to 30 employees and 150 shifts per week. Larger stores may need longer solve times.
- **Premium Feature:** Math Optimizer is gated behind premium scheduling (Spec 035) - same gate as AI Scheduler
- **Existing Infrastructure:** Must integrate with the same data model, suggestion storage, and preview UI as the AI Scheduler (Spec 026). Reuses TaskEngine, Ably, and `aiScheduleSuggestions` table.
- **LLM Dependency:** Explanation and suggestion features require OpenAI API access. Solver itself runs independently. When OpenAI is unavailable, structured (non-LLM) explanations are shown instead. Solver quality is never affected by LLM availability.
- **Same Constraint Set:** V1 enforces exactly the same hard constraints as the AI Scheduler's `AiPromptBuilder` constraints 1-11 for fair comparison. No new constraint types.

### Assumptions

- **Data Quality:** Employee availability, time-off, and hours preferences are accurately maintained in the system
- **Python Available:** Server environment has Python 3.9+ with OR-Tools package installed
- **Store Size:** The vast majority of BuyerKiosk stores have fewer than 30 employees
- **Manager Literacy:** Managers understand concepts like "labor cost", "fairness", and "overtime" without needing definitions
- **LLM Explanation Quality:** OpenAI can generate useful explanations from structured solver output data
- **Comparison Value:** Managers will find value in comparing solver approaches (not just use one exclusively)

---

## Risks and Mitigations

| Risk | Impact | Likelihood | Mitigation |
|------|--------|------------|------------|
| Python subprocess adds latency or reliability risk | Medium | Medium | Process timeout of 90 seconds via `proc_open`. Graceful error handling for non-zero exit codes, stderr capture, and OOM. TaskEngine job wraps subprocess with try/catch. If Python/OR-Tools not installed, Math Optimizer option hidden from UI. Solver results independent of LLM availability. |
| Managers confused by two solver options | Medium | Medium | Clear descriptions of each solver's strengths. Default to last-used. Progressive disclosure - advanced comparison only on demand. |
| Math Optimizer produces "correct but weird" schedules | Medium | Low | LLM explains every decision. Override + re-optimize lets managers lock assignments. Fairness constraint prevents pathological distributions. |
| OR-Tools version compatibility issues | Low | Low | Pin OR-Tools version. Include in automated deployment tests. |
| LLM explanations don't match solver reasoning | Medium | Medium | LLM receives structured data from solver (not raw output). Explanations are verifiable against constraint data. Fallback to structured display if LLM unavailable. |
| Managers always prefer one solver, making comparison pointless | Low | Medium | Track preference data. If one solver dominates, consider making it the default and offering the other as "alternative view." |
| Solve time exceeds 60 seconds for complex stores | Medium | Low | Return best feasible solution at time limit. Log problem sizes for capacity planning. Optimize constraint model based on production data. |
| Python dependency complicates deployment | Medium | Low | Package solver as self-contained Python script with requirements.txt. Document installation in deployment runbook. |

---

## Open Questions

- [x] Should both solvers run simultaneously or user-selected? -> User selects solver type
- [x] Can the solver run in PHP? -> No, OR-Tools requires Python. Use subprocess call from PHP.
- [x] Should priorities match the AI Scheduler? -> Yes, same 6 priorities for fair comparison
- [x] Rate limiting for Math Optimizer? -> No limit. Zero API cost means unlimited use.
- [x] Premium gating? -> Yes, same premium gate as AI Scheduler (Spec 035)
- [x] What if OpenAI is down? -> Solver works independently. Explanations fall back to structured data display.
- [ ] Should comparison analytics feed back into solver improvement? -> Deferred to future iteration
- [ ] How to handle solver upgrades (OR-Tools version bumps)? -> Define in SDD

---

## Supporting Research

### Competitive Analysis

**Timefold / OptaPlanner (Red Hat):** Enterprise constraint solver for employee scheduling. Uses a proprietary scoring engine. Proven in healthcare and retail scheduling. Validates that deterministic solvers outperform LLMs for scheduling optimization. Their blog explicitly states: "LLMs can't optimize schedules, but AI can" - distinguishing generative AI from optimization AI.

**Deputy Auto-Scheduling:** Uses demand forecasting + rule-based optimization. No LLM component. Reports 20-30% labor cost savings. Requires 3+ months of historical data for demand prediction. Premium tier pricing.

**WhenIWork Auto-Scheduling:** Basic rule-based auto-fill. No optimization engine. Fills shifts by availability only, no cost or fairness optimization. Free tier includes auto-scheduling.

**Soon.works:** Explicitly warns against using LLMs for scheduling: "ChatGPT and LLMs aren't ideal for automatically generating shift schedules" due to constraint violation risks. Uses deterministic algorithms.

**Our Advantage:** Combining a proven constraint solver (OR-Tools) with LLM explanation creates a unique offering: mathematically optimal schedules that managers can actually understand and trust. No competitor offers this hybrid approach.

### Academic Research

**"I Want It That Way" (ACM TiiS 2024):** Validated the pattern of LLM for preference elicitation + constraint solver for optimization. Users preferred this hybrid over pure-LLM scheduling.

**OptiChat (INFORMS 2025):** Demonstrated that LLMs can effectively explain constraint solver decisions when given structured solver output data. Users rated explanations as "helpful" or "very helpful" 83% of the time.

**Dietvorst et al. (Management Science 2016):** Key finding: managers adopt algorithmic recommendations significantly more when they can modify the output, even slightly. Our accept/reject interface directly addresses algorithm aversion.

**CP-SAT Performance (CP 2023):** Google's CP-SAT solver achieves "unsurpassed performance" on scheduling benchmarks. For problems of our size (10-30 employees), optimal solutions are found in under 60 seconds.

### Market Data

- Deterministic scheduling solvers have 99.9% constraint satisfaction vs. 90-95% for LLM-based approaches
- LLM scheduling costs $0.50-$2.00 per generation; local solvers cost $0 per generation
- 68% of managers in algorithm aversion studies adopted when given override capability (Dietvorst 2016)
- OR-Tools is used by Google internally for scheduling at Google Scale; Apache 2.0 licensed, free for commercial use