Optimization and Operations Research Methods Questions

We can implement the classical O(n^3) Hungarian algorithm (a.k.a. Kuhn–Munkres for square cost matrix) suitable for n ≤ 50. The core step maintains potentials (u, v), an augmenting path via min-slack, and builds a matching p (column→row). This implementation finds minimum-cost assignment.

def hungarian(cost):
    # cost: n x n matrix (list of lists)
    n = len(cost)
    INF = 10**12
    u = [0]*(n+1)    # potentials for rows (1..n)
    v = [0]*(n+1)    # potentials for cols (1..n)
    p = [0]*(n+1)    # matching: p[j]=i (row assigned to col j)
    way = [0]*(n+1)

    for i in range(1, n+1):
        p[0] = i
        minv = [INF]*(n+1)
        used = [False]*(n+1)
        j0 = 0
        while True:
            used[j0] = True
            i0 = p[j0]
            delta = INF
            j1 = 0
            for j in range(1, n+1):
                if not used[j]:
                    cur = cost[i0-1][j-1] - u[i0] - v[j]
                    if cur < minv[j]:
                        minv[j] = cur
                        way[j] = j0
                    if minv[j] < delta:
                        delta = minv[j]; j1 = j
            for j in range(0, n+1):
                if used[j]:
                    u[p[j]] += delta
                    v[j] -= delta
                else:
                    minv[j] -= delta
            j0 = j1
            if p[j0] == 0:
                break
        # augment
        while True:
            j1 = way[j0]
            p[j0] = p[j1]
            j0 = j1
            if j0 == 0:
                break

    # build result: row -> col
    assign = [-1]*n
    for j in range(1, n+1):
        if p[j] != 0:
            assign[p[j]-1] = j-1
    total_cost = sum(cost[i][assign[i]] for i in range(n))
    return assign, total_cost

Key points:

• Time: O(n^3) — loop over n rows, each augmentation scans n columns and updates slacks.
• Space: O(n^2) for cost input, O(n) for auxiliary arrays.
• Robust for n ≤ 50 (fast, exact optimality).
• Not ideal for high-frequency real-time at scale: cubic runtime and memory copying overhead. For streaming/real-time, prefer incremental/approximate or greedy matching, or specialized online algorithms (e.g., auction algorithm with warm starts, or locality-sensitive heuristics) to reduce latency. Edge cases: non-square cost (pad with large costs), negative costs are supported by potentials logic, but ensure numeric INF >> magnitude of costs.

Requirements & success criteria:

• Functional: reduce average delivery time and per-order wait while maintaining or increasing driver earnings and batching rate; preserve service level (on-time %) and customer satisfaction.
• Non-functional: no >5% increase in canceled orders or driver churn.

Offline simulation design:

• Data: 3–6 months of historical events (order placements, pickup/drop locations, time windows, driver shifts, travel-time matrices, cancellations). Augment with synthetic stress scenarios (peak demand, sparse drivers, traffic incidents).
• Simulator: event-driven discrete simulator that replays timestamps and injects the new matching algorithm vs. baseline. Maintain realistic driver behavior model (accept/reject probability conditioned on earnings, detour, preferences) and route ETA estimation (learned travel-time model).
• Experiments: run paired simulations on identical seed streams for baseline and graph-augmented method; sweep hyperparameters (batch size cap, graph connectivity threshold).
• Warm-start: initialize driver states from historical snapshot.

Metrics & instrumentation:

• Primary: Average delivery time per order, average pickup wait, batching rate (fraction of multi-order batches), mean batch size, driver earnings per hour, orders-per-driver-hour.
• Secondary: On-time delivery %, cancellations rate, driver acceptance rate, extra detour time, customer NPS proxy (refunds/complaints).
• Distributional metrics: percentiles (50/90/95) for delivery time and earnings; per-segment (city, time-of-day).

Significance testing:

• Use paired-sample tests since simulations are paired: compute per-seed differences and apply paired t-test (if approx normal) or Wilcoxon signed-rank test otherwise; bootstrap confidence intervals for medians and percentiles.
• Control for multiple comparisons (Bonferroni or Benjamini-Hochberg) across metrics.
• Define minimum detectable effect (MDE) and required number of simulation seeds to achieve power 80% at alpha=0.05 for key metrics (e.g., 5% reduction in avg delivery time).

Checks & robustness:

• Sensitivity analysis over demand, driver supply, and travel-time noise.
• Ablation studies: disable graph components to attribute gains.
• Fairness checks: ensure improvements don’t harm specific geographies or driver cohorts.

Pre-online rollout steps:

1. Shadow mode: run algorithm in production without impacting routing; log decisions, predicted gains, and counterfactual baseline.
2. Small controlled A/B test: start with low-traffic regions/time windows; randomized at driver or order level; monitor real-time safety metrics (cancellations, complaints).
3. Progressive rollout: increase traffic with checkpoints and rollback thresholds.
4. Monitoring & KPI dashboard: near-real-time metrics, alerts for regressions, and drift detection on acceptance behavior.
5. Post-deploy analyses: causal attribution, long-term retention effects, and operational adjustments.

Why this works:

• Paired sims + shadowing provide low-risk, high-confidence estimates; significance tests and power calculations ensure observed differences are real; staged rollout protects operations while enabling measurable improvement.

Requirements & approach:

• Multi-objective problem: minimize customer ETA (T), maximize driver earnings fairness across neighborhoods (F), maximize platform revenue (R).
• Use a weighted-sum formulation for practicality and a constrained variant for regulatory safety-critical guarantees. Combine with simulation & ML-based tuning of weights.

Weighted-sum formulation (decision variables x_{i,j} = assign driver i to request j):
Minimize: L(x) = w_T * (sum_j ETA_j(x))/N_req - w_R * (sum_{i,j} revenue_{i,j} x_{i,j}) + w_F * FairnessPenalty(x)
where

• ETA_j(x) computed from dispatch distances and expected congestion,
• revenue_{i,j} = fare_{j} - cost_share,
• FairnessPenalty(x) = g(Gini({earnings_n(x)})) or sum_n max(0, μ - earnings_n(x))^2 for neighborhoods n,
• weights w_T, w_R, w_F >=0.

Constrained formulation:
Minimize: (sum_j ETA_j(x))/N_req - α * (sum_{i,j} revenue_{i,j} x_{i,j})
subject to:

• Fairness constraint: Gini({earnings_n(x)}) <= g_max OR earnings_n(x) >= (1 - ε) * μ_global for all n
• Capacity: each driver assigned at most 1 active job, request served by one driver
• Service-level: P(ETA_j <= ETA_target) >= p_min (stochastic constraint)
• Operational: driver eligibility, geo-feasibility, shift constraints

Why use both forms:

• Weighted-sum allows continuous trade-offs and easy integration into real-time MPC/ILP solvers.
• Constrained form enforces hard fairness or SLA requirements.

Choosing weights/constraints in practice:

1. Stakeholder-driven anchors: set ranges from business KPIs (target avg ETA, min neighborhood earnings uplift, revenue floor).
2. Pareto front estimation: run offline simulations across grid of weights to build Pareto surface; choose operating points balancing business & fairness.
3. Data-driven automatic tuning: use bilevel optimization or reinforcement learning (policy param θ mapping state→assignment) where outer loop optimizes weights/constraint thresholds to maximize long-run reward subject to fairness/SLA through simulation.
4. Risk-sensitivity: treat fairness constraint as hard for legal/regulatory needs; otherwise tune w_F via policy-gradient on historical simulator optimizing reward+regularized fairness.
5. Monitoring & feedback: continuous A/B tests, metrics (avg ETA, revenue, neighborhood Gini), and periodic re-tuning.

Implementation notes:

• Use mixed-integer programming or relaxation + rounding for batching; warm-start with greedy heuristics for latency.
• Model uncertainty with chance constraints or robust optimization.
• Fairness metric choice matters (Gini vs. CV vs. lower quantile); pick interpretable metric for stakeholders.

Trade-offs:

• Higher w_F increases local earnings equity but can raise ETA or reduce revenue; constraints ensure minimum fairness while preserving business-critical KPIs.

Approach: For each incoming order, greedily select the best available driver within max_pickup_time_seconds who has spare capacity and whose acceptance probability ≥ threshold. Score drivers by a weighted function (ETA, remaining capacity, acceptance probability). Assign immediately (online). This is simple, low-latency, and practical for dispatch.

# Pseudocode / Python-like
def greedy_dispatch(order_stream, drivers, max_pickup_time_seconds, driver_capacity, accept_prob_threshold):
    # drivers: dict driver_id -> {location, capacity_used, accept_prob, available:bool}
    # order_stream: yields orders with {order_id, location, time_received}
    for order in order_stream:
        candidates = []
        for d_id, d in drivers.items():
            if not d['available']:
                continue
            remaining = driver_capacity - d['capacity_used']
            if remaining <= 0:
                continue
            eta = estimate_travel_time(d['location'], order['location'])
            if eta > max_pickup_time_seconds:
                continue
            if d['accept_prob'] < accept_prob_threshold:
                continue
            # score: lower is better
            score = alpha*eta - beta*remaining - gamma*d['accept_prob']
            candidates.append((score, d_id, eta))
        if not candidates:
            handle_unassigned(order)  # e.g., queue, expand radius, or notify customer
            continue
        # pick best (min score)
        candidates.sort()
        best_score, best_driver_id, best_eta = candidates[0]
        assign_order_to_driver(order['order_id'], best_driver_id)
        drivers[best_driver_id]['capacity_used'] += 1
        if drivers[best_driver_id]['capacity_used'] >= driver_capacity:
            drivers[best_driver_id]['available'] = False

Key concepts:

• Online decision: immediate assignment without future knowledge.
• Scoring balances ETA, remaining capacity, and acceptance probability.
• Parameters alpha/beta/gamma tune policy.

Time/Space complexity:

• Per order: O(D log D) if sorting candidates, or O(D) with single-pass min; D = #drivers. Space O(D) for candidate list.

Edge cases:

• No candidate within threshold: implement fallback (wait queue, increase radius, guaranteed dispatch with surge).
• Rapid driver state changes (concurrency): require atomic updates / optimistic locking.
• Acceptance probabilities can be stale—update with live signals.

When greedy fails / better algorithms:

• High contention: greedy can block better future matchings (e.g., using capacity for low-value order). Use batched matching (periodic windowed optimization) solved via max-weight bipartite matching or min-cost flow to global-optimize assignments.
• Stochastic arrivals / uncertainty: use online stochastic optimization or prophet/secretary algorithms with learned thresholds.
• Strategic objectives (latency + fairness + revenue): use integer programming / constrained MDP, or RL-based dispatch policies trained in simulation to trade off long-term metrics.
• Scalability with complex constraints (multi-stop routes, time windows): use route-aware assignment (VRP heuristics) rather than per-order greedy.

Recommendation: Start with greedy for low latency; monitor regret metrics (missed high-value matches). If regret grows or KPIs suffer, migrate to hybrid: short batching windows + fast solver or learned policy (RL/heuristic) for near-optimal online matching.

Approach overview: treat accuracy and latency as competing objectives and produce a set of candidate models/configurations, measure both under realistic conditions, build the Pareto frontier, then pick solutions via constrained optimization (maximize accuracy subject to latency ≤ X ms) or Lagrangian scalarization. Finally evaluate candidates with rigorous experiments and present clear trade-offs to stakeholders.

Constructing Pareto frontiers:

• Generate candidates by varying architectures (depth, width), input pipelines, quantization/INT8, pruning, distillation, caching, ensemble vs single-model, and hardware choices.
• For each candidate, measure: offline accuracy (e.g., NDCG@k, MRR), p95 latency and throughput under production-like load, and resource cost.
• Plot points (latency on x, accuracy on y). The Pareto frontier is the set where no other point has both lower latency and higher accuracy.

Constrained optimization methods:

• Simple: filter candidates with latency ≤ X and pick highest accuracy.
• Search-based: use Bayesian optimization or multi-objective evolutionary algorithms to find Pareto set under latency constraint.
• Lagrangian scalarization: maximize Accuracy - λ * Latency; sweep λ to recover frontier.
• Practical: incorporate latency as hard constraint during architecture search (e.g., latency predictor in NAS) so candidate generation respects SLA.

Evaluating candidate models:

• Measure latency in conditions matching production: same hardware, batching, warm cache, concurrency. Report p50/p95/p99 and tail sources.
• Validate accuracy on temporally-split holdout sets and online A/B tests measuring business KPIs (engagement, CTR, revenue).
• Use statistical significance tests and minimum detectable effects for A/B.
• Evaluate cost (inference cost per request) and operational factors (reliability, ease of deployment).

Communicating trade-offs to stakeholders:

• Visuals: Pareto curve annotated with representative candidates (include cost and resource footprint).
• Decision criteria to present: SLA compliance (latency), accuracy uplift vs baseline, expected business impact (lift in KPI), cost delta, implementation risk, and rollback plan.
• Provide 2–3 recommended options: conservative (meets latency with modest accuracy gain), aggressive (best accuracy on edge of SLA), and experimental (needs infra changes).
• Offer quantitative ROI: project KPI improvement × user base × cost change, plus risk/effort estimate.

Example decision rule:

• If latency SLA X is strict → choose highest-accuracy candidate with p95 ≤ X and statistically significant KPI improvement in A/B.
• If SLA flexible → evaluate marginal accuracy gain per additional ms and choose point where marginal business value < incremental infra/maintenance cost.

This method gives reproducible technical evaluation, aligns with SLAs and business goals, and makes trade-offs transparent for cross-functional decision-making.