Optimization and Operations Research Methods Questions

Linear Programming (LP) optimizes a linear objective subject to linear constraints with continuous decision variables. Integer Programming (IP) adds the requirement that some or all variables must take integer values (often binary). That integrality makes problems NP-hard in general but necessary when decisions are discrete and must map to real-world actions.

Two concrete production-line decision examples requiring integer variables:

1. Number of batches to run per shift (x_b ∈ Z≥0). You can’t run 3.7 batches; fractional batches are infeasible operationally. Integrality ensures schedules and material usage align with batch sizes, inventory, and downstream processing.
2. Number of machines to switch on (m_i ∈ {0,1} for each machine i). A machine is either on or off; fractional values have no physical meaning. Binary variables also capture fixed startup costs and minimum-run constraints.

Why integrality matters:

• Implementability: Only integer solutions map to executable actions (you can’t staff 2.4 operators or start 0.6 machines).
• Schedule feasibility: Integer schedules respect discrete time slots, batch counts, and sequence constraints; fractional results can violate capacity or synchronization with downstream steps.
• Business interpretation: Integer variables allow correct accounting of costs (startup, maintenance), service-level commitments, and profitability; fractional decisions can mislead stakeholders and produce infeasible cost estimates.

As a data scientist modeling yield optimization, start with an LP relaxation for bounds and sensitivity, then add integer constraints where decisions are discrete to ensure solutions are actionable and correctly interpreted by operations and finance.

Reward function (per time step t, for dispatch action a_t in state s_t):
r_t = α * R_immediate(t) - β * W_avg(t) + γ * RetentionBonus(t) - δ * C_poach(t)

Where:

• R_immediate(t) = sum of fares accepted from rides started within this step.
• W_avg(t) = average passenger wait time (mins) for dispatched/queued riders this step.
• RetentionBonus(t) = E[Δ_retention | drivers affected by action] approximated as sigmoid(η * (idle_time_change)) giving positive credit when driver utilization improves and negative when utilization drops. This term can be propagated over longer horizons (see credit assignment).
• C_poach(t) penalizes churn/driver cancellations or incentives paid.
• α,β,γ,δ,η are tunable scalars to set scale and business priorities.

Credit assignment across multi-step episodes:

• Use n-step returns or lambda-returns (TD(λ)) to blend immediate reward with multi-step outcomes; this balances variance and bias.
• Augment state with per-driver satisfaction features and use per-driver eligibility traces so actions affecting a driver get credit when that driver's long-term outcomes change (retention/churn) — e.g., assign delayed retention reward to past actions weighted by decay factor λ and proximity in time.
• For policy gradient methods, use advantage estimation with GAE (Generalized Advantage Estimation) to reduce variance and capture long-term effects.

Non-stationarity challenges:

• Supply/demand, driver behavior, and pricing change over time. Mitigations:
  • Train using continual learning with online fine-tuning and replay buffers prioritized by recency.
  • Use domain randomization in simulation (vary demand patterns, acceptance rates, traffic) to create robust policies.
  • Maintain ensemble of policies and A/B test with safe rollout (canary) and fallback rule-based policy.
  • Include covariates encoding time-of-day, seasonality, and recent trends to help the policy condition on non-stationary context.

Simulation approaches for training & validation:

• Build a modular simulator: demand generator (Poisson/hawkes processes + spatial patterns), driver agent models (utility-based acceptance, fatigue/churn dynamics), routing/travel-time model (realistic ETA distributions), and marketplace pricing/incentives.
• Calibrate simulator to historical logs via inverse problem: fit demand rates, acceptance probabilities, and churn models using MLE or probabilistic programming.
• Train RL policy in sim with curriculum learning: start simple, increase complexity (traffic, surge, adversarial demand).
• Validate with off-policy evaluation (IPS, MAGIC) using logged data, counterfactual policy evaluation, and shadow deployments (offline scoring live traffic) before gradual live rollouts. Monitor key metrics: revenue per-hour, average wait, driver retention rate, cancellations, and fairness across regions.
• Safety: constrain policy with hard business rules (e.g., never increase wait > threshold) and use constrained RL (Lagrangian) if needed.

This structure yields a tractable, tunable reward that balances short-term revenue, customer experience, and long-term driver health while supporting principled credit assignment and robust simulation-driven development.

Requirements & constraints:

• Inputs: SKU-level demand forecasts with uncertainty (prediction intervals / full predictive distribution), lead times, BOM, capacities, changeover costs, on-hand inventory, supplier reliability, service-level targets, holding/shortage costs.
• Non-functional: daily decisions for short horizon, weekly/monthly for medium/long horizon, fast solve time (<1 hour) for tactical runs.

High-level architecture:

• Data layer: ETL pulls forecasts (ML model outputs + covariates), ERP (inventory/orders), MRP/BOM, vendor SLAs into a warehouse; store distributions (quantiles or parametric params).
• Modeling layer: two-tier approach:
  1. Tactical (weekly/monthly): stochastic optimization (two-stage stochastic MIP with scenario sampling or sample-average approximation) for master production schedule. Uses sampled demand scenarios from forecast distributions; recourse decisions for overtime/expedite.
  2. Operational (daily/short-horizon): robust/deterministic MIP with safety buffers derived from forecast quantiles (e.g., demand at 95% quantile => safety stock) for fast re-planning.
• Orchestrator: pipeline triggers re-optimization cadence, manages scenario generation, solver runs (CPLEX/Gurobi), caching.
• Serving/API: pushes plans back to ERP and dashboards.

How forecast errors propagate:

• Safety stock: compute per-SKU safety stock = z * sigma_leadtime where sigma derived from forecast variance over lead time; used as minimum inventory constraints.
• Chance constraints: in stochastic MIP, impose P(backorder ≤ threshold) ≥ target by sampling scenarios; convert to deterministic equivalents or use sample-average constraints.
• Penalty terms: include expected stockout cost across scenarios to internalize forecast uncertainty.
• Supplier uncertainty: model lead time as random variable in scenarios.

Re-optimization cadence:

• Real-time alerts for exceptions (stockouts, supplier failures)
• Daily short-horizon deterministic replan (fast solve)
• Weekly stochastic tactical re-opt with refreshed forecasts
• Monthly strategic capacity review

Monitoring & KPIs:

• Forecast metrics: RMSE, MAPE, pinball loss for distributional quality, calibration (coverage of prediction intervals).
• Optimization metrics: service level achieved vs target, fill rate, average days of supply, expected vs realized cost, solver success/failure rate, solve time.
• Drift detection: monitor increases in residual error or interval miss-rate to trigger model retraining or scenario adjustments.
• A/B testing: compare deterministic vs stochastic policies on historical replay.

Trade-offs & reasoning:

• Stochastic MIP better captures uncertainty but is computationally heavier—use for tactical decisions where value outweighs compute.
• Deterministic with safety buffers gives speed and interpretability for operational runs.
• Regular monitoring of interval calibration ensures safety stock and chance constraints remain meaningful.

Implementation tips:

• Store full predictive distributions (or sufficient stats) so downstream optimization can resample.
• Start with quantile-driven safety stocks, then graduate to sampled stochastic runs as tooling/maturity grows.
• Automate pipelines and include human-in-loop override for critical SKUs.

Branch-and-cut is the dominant method for solving mixed-integer programs (MIPs). It interleaves branch-and-bound (partitioning the integer-feasible space into subproblems) with the dynamic generation of cutting planes (valid linear inequalities) to tighten the LP relaxation at nodes so fewer branches are needed.

How it works (high level)

• Start from LP relaxation. If solution is fractional, generate cuts that remove the fractional solution but keep all integer-feasible points.
• Re-solve tightened LP; branch when no useful cuts remain or LP solution still fractional.
• Continue cutting and branching recursively; prune nodes by bounds or infeasibility.

Role of cutting planes

• Reduce LP gap quickly, lower tree size, and improve bound quality.
• Useful early to avoid exploring large parts of tree; later cuts can reduce node LP times by simplifying subproblems.
• Poor cuts (numerically weak or dense) can slow solves — quality matters more than quantity.

Common cuts (what they are and when they help)

• Gomory fractional cuts: General-purpose cuts derived from simplex tableau. Good as a baseline; can be numerous and numerically unstable for large/degenerate LPs.
• Cover cuts: For 0-1 knapsack-type constraints, a cover is a set of variables whose sum exceeds capacity; corresponding cuts exclude fractional packings. Very effective for packing/lot-sizing/yield constraints.
• Clique cuts: From conflict graphs of binary variables; when variables are mutually exclusive, clique inequalities eliminate infeasible fractional combinations. Strong for scheduling and mutually-exclusive selection problems.

Custom problem-specific cuts for yield-optimization

• Yield-optimization often has domain structure: capacity limits, degradation interactions, or logical sequencing. Custom cuts (e.g., aggregated resource bounds, logical implication cuts, or surrogate capacity cuts) capture these structures more tightly than generic cuts.
• Example: If yield depends on combinations of process settings, derive cuts that exclude fractional mixes that are physically impossible or that bound combined yield loss—this reduces symmetry and fractional LP artifacts.
• Custom cuts are most valuable when LP relaxation is weak and when domain rules produce sparse, strong inequalities; test them offline for validity and strength before enabling broadly.

Practical tuning tips (Gurobi / CPLEX)

• Cut emphasis: Use moderate cut generation initially. In Gurobi, set Cuts (e.g., Cuts=2) or Heuristics/CutFocus; in CPLEX, set MIPEmphasis/CPX_PARAM_CUTLOOSE. Aggressive cuts improve bounds but increase LP time—use when tree is huge or root gap is large.
• Node selection: Best-bound (default) focuses on improving global bound; depth-first can find incumbents quickly (useful to get feasible solutions for pruning). In Gurobi, set NodeSel to DepthFirst or BestBound; in CPLEX, set MIPStrat or NodeSel param.
• Heuristic frequency: Heuristics find incumbents early; increase frequency if feasible solutions are scarce. In Gurobi, adjust Heuristics parameter (0–1); in CPLEX, set MIPEmphasis or WorkMem for heuristics. If many good incumbents already exist, reduce heuristic aggressive settings to save time.
• Root node strategy: Spend more time at root (more cuts, presolve) when LP relaxation is weak; lower node presolve if root is expensive but tree exploration is cheap.
• Numerical stability: Turn off/limit cuts that create dense rows; enable scaling and numeric emphasis (Gurobi NumericFocus, CPLEX NumericEmphasis) if instability occurs.
• Logging and incremental changes: Use solver logs, node/cut/heuristic statistics to identify bottlenecks. Tune one parameter at a time and benchmark on representative instances.
• Hybrid approach: Implement problem-specific cuts in a callback (Gurobi/Cplex lazy/cut callbacks). Validate correctness and add only strong cuts to avoid callback overhead.

Final practical workflow

1. Solve with default settings, collect root gap, tree size, time profile.
2. Add targeted custom cuts or enable specific cut families that address model structure.
3. Adjust cut/heuristic/node selection trade-offs based on whether you need feasible solutions fast (increase heuristics, depth focus) or tight bounds (increase cuts, best-bound).
4. Profile and iterate; always verify custom cuts’ correctness and measure their impact on both root gap and total run time.

This combination of strong problem-specific cuts, measured use of generic cuts, and careful solver parameter tuning typically yields the biggest runtime improvements for yield-optimization MIPs.

Model (integer program)
Objective: maximize total expected revenue across all stores.
Decision variables:

• x_{s,i} ∈ {0,1} whether SKU i is carried in store s (or integer x_{s,i} ≥0 for unit facings if multiple facings allowed).
• f_{s,i} ∈ Z+ number of facings for SKU i in store s (if modeling facings).
  Constraints:
• Shelf-space per store: Σ_i (width_i * f_{s,i}) ≤ ShelfCap_s for each store s.
• Per-store capacity (SKU count): Σ_i x_{s,i} ≤ K_s.
• Linking facings and carry decision: f_{s,i} ≤ M * x_{s,i}.
• Supply constraints: Σ_s f_{s,i} ≤ Supply_i (or flow constraints per DC).
• Business rules: mandatory SKUs, regional exclusives, min/max facings.
  Objective detail: expected_revenue_{s,i}(f_{s,i}, context) can incorporate price, promotion lift, and cannibalization (cross-term approximations or linearized pairwise penalties).

Required data & features

• Historical per-store SKU sales (units, revenue) by time period.
• Price, promo history, and elasticity estimates.
• SKU physical attributes (width, depth).
• Local demand signals: demographics, foot traffic, competitors, seasonality.
• Cannibalization matrix or estimated cross-elasticities between SKUs.
• Lead times, inventory/SKU-level supply constraints.
• Assortment rules, labor/planogram constraints.

Validation approaches

• Holdout stores: reserve a representative subset (by size/region) to compare predicted vs realized revenue after deployment.
• A/B test: randomize stores into control (current assortment) and treatment (optimized) groups; measure revenue, units, margins, and stockouts over test window.
• Offline backtest: simulate past periods using historical demand with the optimizer and compare to actual outcomes.
• Sensitivity analysis: vary demand elasticities and supply limits to test robustness.

Deployment considerations

• Integration with merchandising/planogram systems and replenishment pipelines.
• Operational constraints: change frequency limits, planogram execution cost, store labor.
• Rollout strategy: pilot in few representative stores, iterate models, then phased scaling.
• Monitoring: dashboards for sales lift, stockouts, execution adherence; retrain periodically.
• Governance: human-in-the-loop approvals, override rules, explainability for buyers.
• Performance: use decomposition (per-region or Lagrangian relaxation) or heuristics for scale; store-level parallelization and warm starts for frequent re-optimization.