Optimization and Operations Research Methods Questions

Situation: I was responsible for deploying an optimization system that changed procurement ordering policies and shop-floor sequencing—impacting procurement, manufacturing, inventory, and finance.

Plan (high-level):

1. Identify stakeholders & champions

• Primary: Head of Procurement, Plant Manager, Production Planning Lead, Inventory Manager, Finance (costing), IT/ERP, Quality.
• Secondary: Suppliers, Shift Supervisors, Logistics, Legal.
• Champions: Recruit one senior stakeholder in Procurement and one Plant Manager as executive sponsors; identify an operational “power user” in each plant (supervisor) to act as local champions.

2. Engagement & governance

• Set up a steering committee (weekly execs) + working group (bi-weekly: data science, IT, ops reps).
• Run discovery workshops to map current processes, constraints, and integration points (ERP, MES).

3. Pilot design

• Scope: single product family and one plant for 8–12 weeks.
• Phases: baseline (2 wks) → shadow mode (4 wks, model makes recommendations; operators still decide) → controlled rollout (4+ wks, automated recommendations applied for specific SKUs).
• Success gates at each phase requiring sign-off from plant champion and data owners.

4. KPIs & success criteria

• Leading operational KPIs: on-time fulfillment %, schedule attainment, changeover time, WIP levels.
• Financial KPIs: procurement cost savings, working capital reduction, COGS impact.
• Model KPIs: accuracy of demand/consumption forecasts, constraint violation rate, recommendation adoption rate.
• Success criteria: statistically significant improvement over baseline (e.g., 5% reduction in WIP and 3% procurement cost improvement), no negative impact on quality or OT.

5. Training & enablement

• Role-based training: operators (short hands-on modules), planners (scenario workshops), procurement (decision rules), IT (integration, monitoring).
• Create playbooks, quick-reference cards, and video walkthroughs.
• Shadow sessions during pilot and a “buddy” system pairing data scientist with planner for two sprints.

6. Rollback & safety

• Implement feature flags and phased toggles in the system to revert to previous policy per SKU/line.
• Define clear rollback triggers (e.g., KPI breach thresholds, critical production incidents) and runbook for emergency rollback with contact list and 2-hour RTO.
• Keep parallel logging so decisions can be audited post-rollback.

7. Monitoring for model decay after go-live

• Real-time dashboards for operational KPIs and model health: data drift (input distributions), prediction error, constraint violations, recommendation acceptance.
• Automated alerts for drift beyond thresholds; weekly model performance reports.
• Canary deployments for model updates; A/B testing new versions before full promotion.

8. Continuous improvement loop

• Weekly retros with plant champions during pilot, monthly post-rollout reviews with steering committee.
• Capture failure modes, unexpected constraints, and build backlog for feature requests.
• Retraining cadence: trigger-based (data drift) + scheduled monthly light retrain and quarterly full retrain with re-validation.
• Measure business impact continuously and feed results into prioritization (RICE) for further optimization.

Resulting behavior: This approach aligns stakeholders early, limits operational risk via staged pilots and rollback, quantifies success with business-facing KPIs, and embeds monitoring plus a feedback loop so the model and processes evolve with operations.

Assumptions:

• Demand elasticity ε_d = percent change in ride requests per 1% change in price (negative). Example: -0.3.
• Driver elasticity ε_s = percent change in active drivers per 1% change in expected earnings (positive). Example: 0.2.
• Target wait time T_target (minutes) and baseline wait T_base at multiplier=1.
• Arrival process: baseline demand rate λ0 (requests/min). Drivers supply S0 (drivers available).
• Matching model: wait time T = f(λ, S) approximated by queueing / empirical mapping (e.g., T ∝ λ/S).
• Multiplier m ∈ [1, m_max]. Effective price = base_fare * m.

Algorithmic approach:

• Use a simulation that at each time step updates demand and supply given current multiplier:
  demand = λ0 * (m)^{ε_d}
  supply = S0 * (expected_earnings_relative)^{ε_s} ≈ S0 * (m)^{ε_s}
  compute wait T = k * demand / supply
• Objective: choose m to minimize loss = w_wait * |T - T_target| + w_revenue * (-revenue) or maximize utility balancing wait and revenue.
• Optimization: If single-zone and smooth, use continuous optimization (e.g., bounded scalar optimization: golden-section or scipy.optimize.minimize_scalar). For nonconvex/robustness or discrete business constraints, grid search is simpler and interpretable.

Python outline (pseudocode):

import math
from functools import partial
from scipy.optimize import minimize_scalar

# params
lambda0, S0 = 10.0, 50.0
eps_d, eps_s = -0.3, 0.2
k = 1.0
T_target = 5.0
base_fare = 10.0

def simulate_multiplier(m):
    demand = lambda0 * (m ** eps_d)
    supply = S0 * (m ** eps_s)
    # avoid zero
    supply = max(1e-6, supply)
    wait = k * demand / supply
    revenue = base_fare * m * demand
    # loss: penalty on deviation + negative revenue (weights tuned)
    loss = abs(wait - T_target) + 0.001 * (-revenue)
    return loss, {'m': m, 'wait': wait, 'revenue': revenue, 'demand': demand, 'supply': supply}

# continuous optimization
res = minimize_scalar(lambda x: simulate_multiplier(x)[0], bounds=(1, 3), method='bounded')
best = simulate_multiplier(res.x)

Key points:

• Use continuous optimization when objective is smooth; grid search when constraints/monotonicity unknown or need quick interpretability.
• Include stochasticity by simulating Poisson arrivals and Monte Carlo to get distribution of wait times.

Validation vs historical data:

• Fit ε_d and ε_s to historical fare changes using time-series regression (log-log: Δlog(demand) ~ ε_d * Δlog(m)); similarly for supply using driver active minutes vs effective earnings.
• Validate mapping T = f(λ,S) by comparing simulated wait distribution to observed wait times across historical bins.
• Backtest: run simulation with historical multipliers and compare predicted demand, supply, wait, revenue to actuals (MAPE, RMSE).
• Holdout/A-B: run controlled experiments or quasi-experiments (diff-in-diff) when possible to verify causal estimates.
• Monitor calibration: lift charts, residual analysis, and re-estimate elasticities periodically.

Approach: model each task with a start time and end time, create a machine assignment boolean per (task, machine) and an optional interval per (task, machine). Enforce each task assigned to exactly one machine, add precedence constraints, add NoOverlap on intervals per machine, and minimize makespan (max of all end times).

from ortools.sat.python import cp_model

# Problem data
num_machines = 3
durations = [3, 2, 4, 1, 2, 3]  # 6 tasks
precedences = [(0, 2), (1, 2), (2, 5), (3, 4)]  # (before, after)

model = cp_model.CpModel()
horizon = sum(durations)

# Variables
starts = [model.NewIntVar(0, horizon, f'start_{t}') for t in range(len(durations))]
ends = [model.NewIntVar(0, horizon, f'end_{t}') for t in range(len(durations))]
assign = [[model.NewBoolVar(f'ass_t{t}_m{m}') for m in range(num_machines)]
          for t in range(len(durations))]
intervals = [[None]*num_machines for _ in range(len(durations))]

for t, dur in enumerate(durations):
    model.Add(ends[t] == starts[t] + dur)
    # exactly one machine
    model.Add(sum(assign[t]) == 1)
    for m in range(num_machines):
        # optional interval active iff assigned to machine m
        intervals[t][m] = model.NewOptionalIntervalVar(starts[t], dur, ends[t], assign[t][m],
                                                       f'interval_t{t}_m{m}')

# No overlap per machine
for m in range(num_machines):
    machine_intervals = [intervals[t][m] for t in range(len(durations))]
    model.AddNoOverlap(machine_intervals)

# Precedence constraints
for a, b in precedences:
    model.Add(starts[b] >= ends[a])

# Makespan
makespan = model.NewIntVar(0, horizon, 'makespan')
model.AddMaxEquality(makespan, ends)
model.Minimize(makespan)

solver = cp_model.CpSolver()
solver.parameters.max_time_in_seconds = 10
solver.parameters.num_search_workers = 8
res = solver.Solve(model)

if res in (cp_model.OPTIMAL, cp_model.FEASIBLE):
    print("Makespan:", solver.Value(makespan))
    schedule = []
    for t in range(len(durations)):
        m = next(m for m in range(num_machines) if solver.Value(assign[t][m]))
        schedule.append((t, solver.Value(starts[t]), solver.Value(ends[t]), m))
    for rec in sorted(schedule, key=lambda x: x[1]):
        print(f"Task {rec[0]}: start={rec[1]}, end={rec[2]}, machine={rec[3]}")
else:
    print("No solution found")

Key points:

• OptionalIntervalVar ties start/end/duration to assignment bool; allows AddNoOverlap per machine.
• Precedences are simple linear constraints on starts/ends.
• Minimizing makespan via AddMaxEquality.

Complexity: CP-SAT is NP-hard for scheduling but handles small/medium instances efficiently; runtime grows combinatorially with tasks/machines. Edge cases: zero-duration tasks (allowed), impossible precedence cycles (infeasible), very tight horizon (infeasible). Sample output (solver dependent):
Makespan: 8
Task 3: start=0, end=1, machine=0
Task 1: start=0, end=2, machine=1
Task 0: start=1, end=4, machine=0
Task 2: start=4, end=8, machine=2
Task 4: start=1, end=3, machine=1
Task 5: start=8, end=11, machine=0

Approach: generate a calendar of week starts for the last 52 weeks, cross-join distinct sku/store pairs to ensure zero-sales weeks appear, aggregate transactions by week, then flag SKUs/stores as sparse when they have sales in fewer than 5 distinct weeks.

WITH params AS (
  SELECT
    date_trunc('week', current_date) - interval '51 weeks' AS first_week_start,
    date_trunc('week', current_date) AS last_week_start
),
weeks AS (
  SELECT generate_series(first_week_start, last_week_start, interval '1 week')::date AS week_start
  FROM params
),
sku_store AS (
  SELECT DISTINCT sku_id, store_id FROM transactions
),
sales_by_week AS (
  SELECT
    ss.sku_id,
    ss.store_id,
    w.week_start,
    COALESCE(SUM(t.qty_sold), 0) AS weekly_qty
  FROM sku_store ss
  CROSS JOIN weeks w
  LEFT JOIN transactions t
    ON t.sku_id = ss.sku_id
   AND t.store_id = ss.store_id
   AND date_trunc('week', t.sold_at)::date = w.week_start
  GROUP BY ss.sku_id, ss.store_id, w.week_start
),
sparsity AS (
  SELECT
    sku_id,
    store_id,
    COUNT(*) FILTER (WHERE weekly_qty > 0) AS weeks_with_sales
  FROM sales_by_week
  GROUP BY sku_id, store_id
)
SELECT
  s.sku_id,
  s.store_id,
  s.week_start,
  s.weekly_qty,
  (sp.weeks_with_sales < 5) AS is_sparse
FROM sales_by_week s
JOIN sparsity sp USING (sku_id, store_id)
ORDER BY s.sku_id, s.store_id, s.week_start;

Key points:

• date_trunc('week', ...) yields the week's start (Monday); generate_series creates 52 week bins.
• CROSS JOIN ensures every sku/store has every week; LEFT JOIN fills sales if present.
• COALESCE(...,0) produces zero weekly_qty for weeks with no transactions.
• is_sparse uses the count of weeks with positive sales (<5) per sku/store.

Performance tips: for large datasets, pre-filter transactions to the 52-week window, ensure indexes on (sku_id, store_id, sold_at), and consider computing sku_store from a product-store master table instead of transactions if available.

The integrality gap is the difference between the optimal objective of the linear programming (LP) relaxation and the optimal integer (MIP) solution, usually reported as a ratio or absolute gap: (LP_opt − IP_opt)/|IP_opt|. It measures how much looser the continuous relaxation is compared to the true discrete problem.

Business impact in yield optimization (manufacturing):

• A large gap means the LP suggests optimistic yields, capacities, or costs that are not attainable when discrete choices (e.g., batch counts, on/off machine schedules, integer lots) are enforced.
• Decisions based on relaxed solutions can understate required resources, overestimate throughput, or choose infeasible production mixes, leading to missed targets, higher costs, or supply shortfalls.
• It can also slow solver time and reduce confidence in prescriptive recommendations.

Simple modeling changes to reduce the gap:

• Tighter bounds: strengthen variable bounds (e.g., tighter capacity, inventory limits, BOM-derived bounds) to shrink feasible LP region.
• Avoid weak big‑M formulations: replace large big‑M constants with computed tight Ms or use indicator constraints/ SOS constraints where supported.
• Alternative formulations: use flow or disaggregated formulations (e.g., multi-commodity flow, time-indexed models) that have stronger convex hulls.
• Add valid inequalities/cutting planes: knapsack covers, flow cuts, or problem-specific cuts to remove fractional LP solutions.
• Variable fixing and preprocessing: fix obvious integers from heuristics or problem logic to reduce relaxation space.
• Use tighter integrality-preserving modeling: model lot-sizing with (u,y) formulations instead of loose aggregate constraints.

Example: replacing a big‑M constraint that links machine-on binary y and production x (x ≤ M y) with M computed from min(capacity, demand) or time-indexed variables often cuts fractional solutions and yields more realistic, faster-to-solve models.