Yield Optimization & Constraint-Based Modeling Questions

Techniques for optimizing yield and performance under constraints using constraint-based modeling, including linear programming, integer programming, and related optimization methods, applied to operations, manufacturing, supply chain, and product optimization.

MediumTechnical

86 practiced

You solved the LP relaxation for a production scheduling problem but the optimal solution contains fractional production quantities for product batches that must be integer. List and discuss practical approaches to obtain implementable integer schedules while preserving overall yield: naive rounding, greedy repair procedures, re-optimization with integer heuristics, using MIP solver time-limited runs, and local search improvements.

Sample Answer

When an LP relaxation gives fractional batch quantities but batches must be integer, you need practical ways to convert the solution while keeping yield (throughput/coverage/cost) close to optimal. Below are five approaches, each with rationale, pros/cons, and when to use.

1) Naive rounding- What: Round each fractional variable up or down (floor/ceil or nearest).- Pros: Fast, trivial to implement.- Cons: Can violate capacity/precedence constraints or degrade yield substantially.- Use when: Quick feasibility check or when fractions are tiny and constraints are loose.- Tip: Prefer floor for resource-limited problems then fix deficits.

2) Greedy repair procedures- What: Start from rounded solution, iteratively fix infeasibilities (e.g., if capacity violated, reduce least-cost batches) or add batches where demand shortfalls occur.- Pros: Fast, often produces feasible solution with small loss.- Cons: Heuristic; quality depends on repair rules.- Example rule: while capacity>limit, remove batch with smallest marginal yield-per-resource.

3) Re-optimization with integer heuristics- What: Use MIP heuristics like diving, rounding, or fix-and-optimize on subsets of variables: fix many integer variables to LP values (rounded) and optimize remaining ones.- Pros: Exploits LP guidance; good trade-off of speed and quality.- Cons: Requires solver or heuristic implementation.

4) MIP solver time-limited runs- What: Feed full MIP to solver but limit solve time or node count, use LP solution as start (warm start).- Pros: Solver heuristics + cuts can quickly find high-quality integer feasible solutions close to LP bound.- Cons: Might still be slow for large instances; needs solver licenses.

5) Local search improvements- What: Apply neighborhood searches (swap, add/remove batches, pattern-based moves), simulated annealing, or tabu search to improve an initial feasible schedule.- Pros: Flexible, often finds significant local gains while preserving feasibility and yield.- Cons: Needs tuning; may stall in local optima without diversification.

Practical workflow recommendation:1. Use LP solution as guidance.2. Apply rounding + greedy repair to get a fast feasible baseline.3. Run solver heuristics or time-limited MIP using LP start.4. Apply local search/fix-and-optimize on promising areas to recover yield lost from rounding.Track objective gap and constraint violations; iterate until acceptable trade-off between runtime and yield is reached.

HardTechnical

91 practiced

Outline and implement (pseudocode or illustrative Python modules) an end-to-end pipeline that: ingests hourly demand forecasts, runs a constrained production optimization (MIP) hourly with re-optimization, logs inputs/outputs for audit, handles infeasible solves by auto-relaxation or heuristic fallback, and exposes a REST API for downstream consumers. Describe module responsibilities, error handling, unit/integration testing, and operational monitoring.

Sample Answer

Approach summary: build modular Python pipeline with (1) Ingest, (2) Preprocess & Validate, (3) Optimizer (MIP + re-optimization + auto-relax/heuristic), (4) Audit Logger, (5) API, (6) Orchestration & Monitoring. Each module has clear responsibilities, retries, and tests.

Modules and responsibilities- ingest.py: fetch hourly forecasts (Kafka/S3/API), validate schema, backfill logic, idempotency keys.- preprocess.py: clean, feature-engineer, convert to optimization inputs (dictionaries/matrices).- optimizer.py: build and solve MIP via solver SDK (Gurobi/PuLP/CBC). Implements warm-start/re-optimization using previous solution, infeasibility handlers (auto-relaxation via soft constraints + penalty, and greedy heuristic fallback).- audit.py: atomic logging to durable store (Parquet on S3 + metadata DB entry), record inputs, solver status, constraints relaxed, solution hash, timestamps, versioned model spec.- api.py: FastAPI exposing GET /latest-solution, POST /solve-now, streaming endpoints, auth.- orchestrator.py: hourly scheduler (Airflow/Cron), concurrency guard, metric emission.- monitoring.py: Prometheus metrics, Sentry for exceptions, alerting rules.

Illustrative code (simplified)

python

# optimizer.py (illustrative)
from gurobipy import Model, GRB
def solve_mip(data, warm_start=None, time_limit=30):
    m=Model()
    # build vars and constraints from data...
    # ex: x_t = m.addVars(T, vtype=GRB.CONTINUOUS, lb=0)
    if warm_start:
        # set start values
        pass
    m.Params.TimeLimit = time_limit
    m.optimize()
    status = m.Status
    if status==GRB.INFEASIBLE:
        # try feasibility relaxation (penalize violations)
        relax = m.relax()  # pseudocode; implement via feasibility relaxation API
        relax.optimize()
        if relax.Status==GRB.OPTIMAL:
            return {"solution": extract(relax),"relaxed":True}
        # fallback heuristic: greedy fill
        return {"solution": greedy_fallback(data),"relaxed":False,"heuristic":True}
    elif status==GRB.OPTIMAL:
        return {"solution": extract(m),"relaxed":False}
    else:
        raise RuntimeError(f"Solver failed status={status}")

Error handling- Input validation errors -> reject with 4xx in API, log audit and metrics.- Transient ingestion/solver errors -> exponential backoff retries, circuit breaker after N failures.- Fatal errors -> create incident via PagerDuty/Sentry; degrade to read-only API serving last validated solution.

Testing strategy- Unit tests: ingest/parsing mocks, preprocess transformations, optimizer building pieces using small deterministic instances; use hypothesis for edge cases.- Integration tests: orchestrator runs a short DAG with test Kafka/S3 and a free solver backend; assert audit logs written, API endpoints return expected schema.- End-to-end staging: full pipeline with synthetic forecasts for 24h, assert feasibility rates, performance SLA.

Operational monitoring & SLOs- Metrics: solve_time_seconds, solve_status{optimal,infeasible,relaxed,heuristic}, inputs_processed, api_latency.- Dashboards: Grafana showing hourly success rate, tail solve times, constraint relaxation rate.- Alerts: high infeasibility rate (>3%/hour), solver timeouts > threshold, audit write failures.- Tracing: request IDs propagated across modules; store solution hashes for replayability and reproducibility.

Audit & reproducibility- Store: input payload, model version, solver params, random seed, solution, logs. Use immutable storage (S3 + metadata DB) with retention policy and GDPR controls.

Notes on re-optimization- Warm-start with previous x to accelerate solves.- Use rolling-horizon: optimize for 24h but apply only first hour; on each hour re-solve with updated forecasts to reduce churn.- Add stability penalty to objective to avoid large changes between successive solutions.

This design balances correctness, observability, and resilience: deterministic logging for audits, automated handling of infeasibility, and a REST API for downstream consumers.

MediumTechnical

130 practiced

Explain methods to model cardinality constraints (limiting the number of selected items) in optimization. Provide at least two formulations: a linear MIP formulation using binaries and big-M linkage, and a continuous surrogate such as l1 regularization for relaxed problems. Discuss pros/cons and numeric stability issues (e.g., choice of big-M).

Sample Answer

Short answer: cardinality (||x||0 ≤ k) is nonconvex. Two common modeling approaches are (1) exact MIP with binaries and big‑M linkage, and (2) continuous relaxations / surrogates such as ℓ1 regularization. Below are formulations, pros/cons, and numerical caveats.

1) Linear MIP (exact)- Variables: continuous x_i (decision or coefficients) and binaries z_i ∈ {0,1} indicating selection.- Constraints: - sum_i z_i ≤ k - -M_i z_i ≤ x_i ≤ M_i z_i (or x_i ≤ M_i z_i, x_i ≥ m_i z_i if sign known)This forces x_i = 0 when z_i = 0 and allows x_i free (within bounds) when z_i = 1.

Pros:- Exact enforcement of cardinality.- Can incorporate other linear constraints, objective can be convex (QPs) or linear.

Cons / stability:- Choice of M_i critical. If M_i too large → very weak LP relaxation, slow solves, numerical instability. If too small → may cut feasible optimal solutions.- Mitigate by computing tight variable-specific bounds (data-driven bounds, presolve), using solver indicator constraints (no big‑M), or SOS constraints, or warm-start heuristics.

2) Continuous surrogate: ℓ1 regularization (LASSO)- Replace hard constraint by penalty: minimize f(x) + λ ||x||1, or solve minimize f(x) s.t. ||x||1 ≤ t.Pros:- Convex, scalable, well-supported (glmnet, scikit-learn). Yields sparse solutions and can be tuned via cross-validation.- No binaries → much faster for high-dimensional problems.

Cons:- Not exact: ℓ1 approximates sparsity but may select more/less features; bias on large coefficients.- Choice of λ (or t) controls sparsity indirectly; requires CV or path algorithms.- If problem structure demands exact k nonzeros, ℓ1 may not satisfy that.

Other options and trade-offs:- Nonconvex continuous penalties (SCAD, MCP) reduce bias and get closer to ℓ0 but complicate optimization (local minima).- Greedy algorithms (OMP, forward selection) are fast and interpretable but not globally optimal.- For MIP, prefer tightened M, use presolve bound propagation, or modern solver indicator constraints to avoid big‑M issues.

Numeric notes:- Compute M_i from domain knowledge or from solving relaxed problems (e.g., bound on coefficients from duals).- Avoid uniform huge M; use per-variable bounds.- Monitor LP relaxation gap: large gap signals weak M; consider reformulation.

Recommendation for a data scientist:- Start with ℓ1 for exploration and scalability. If you need exact k or must satisfy combinatorial constraints, use MIP with carefully tightened M or solver-supported indicator constraints.

MediumTechnical

82 practiced

You're optimizing conversion yield but must reserve traffic capacity and budget for ongoing experiments. How would you design an optimization framework that allocates budget among channels while guaranteeing sufficient power for planned experiments and still maximizing expected conversions? Discuss decision variables, constraints, and possible use of bandit or constrained optimization approaches.

Sample Answer

Situation: We want to maximize expected conversions across channels while reserving traffic and budget to ensure planned experiments achieve required statistical power.

Approach (high-level):- Formulate as a constrained optimization problem that jointly allocates traffic/budget to channels (for buying users, ads, or treatments) and to experiments.- Optionally use a contextual constrained bandit to adapt allocations online while respecting hard constraints.

Decision variables:- x_i: fraction of total traffic/budget allocated to channel i for optimization (production / serving).- e_j: fraction reserved for experiment j (could be per-channel: e_{i,j}).- u_i(t): dynamic allocation policy (if online/adaptive).

Objective:Maximize sum_i x_i * conv_rate_i (or predicted conv_i(x_i)) + sum_experiment expected uplift (if experiments will roll out).Formally: maximize Σ_i f_i(x_i) subject to constraints below.

Constraints:- Σ_i x_i + Σ_j Σ_i e_{i,j} ≤ 1 (total traffic/budget)- For each planned experiment j and channel i: e_{i,j} ≥ min_needed_{i,j} to achieve power (sample size constraint derived from power analysis: n = (Z_{1-α/2}+Z_{1-β})^2 * (σ^2)/(Δ^2))- Budget/CPA caps: Σ_i cost_i(x_i) ≤ Budget- Business rules (min/max share per channel), risk limits (max downside).- Latency of rollout: minimum duration to collect stable metrics.

Methodology choices:- Offline constrained optimizer: estimate f_i(x) (response curves) via historical data / uplift models, then solve nonlinear program (e.g., convex optimization or global search) subject to power and budget constraints.- Online: Use a constrained contextual bandit (e.g., Constrained Thompson Sampling or UCB with knapsack constraints) that maximizes reward while ensuring cumulative resource consumption respects experiment-reservation budgets. Enforce reservation by treating experiments as immovable allocations or via dual variables (Lagrangian) that penalize constraint violation.- Hybrid: Solve periodically with updated response curve estimates; use bandit inside non-reserved capacity to explore/exploit.

Practical steps:1. Power analysis per experiment to compute min e_{i,j} (convert to traffic fractions).2. Fit channel response curves and cost-per-conversion models; quantify uncertainty.3. Solve optimization (Lagrangian dual if uncertain) to get x_i and e_{i,j}.4. Deploy online allocation with monitoring; use safe-exploration bandit for remaining capacity; re-run optimization as new data arrives.5. Monitor power attainment, regret, and conversion lift; adjust reserves and priors.

Trade-offs:- Reserving too much reduces short-term conversions; too little undermines experiment validity.- Conservative power estimates require more reserved traffic; consider sequential testing or adaptive designs (group sequential, Bayesian tests) to reduce required sample sizes.

This framework balances guaranteed experiment power with maximizing expected conversions via constrained optimization and adaptive bandit techniques.

EasyTechnical

82 practiced

In Python using PuLP (or another Python LP library), write code that solves this LP: maximize 3*x + 5*y subject to 2*x + y <= 100, x + 2*y <= 80, x >= 0, y >= 0. Provide the code, solver call, and report the optimal x, y values and the objective value. Also mention how you'd change the model to require integer solutions for x and y.

Sample Answer

Approach: Formulate the LP with PuLP, define variables x,y >= 0, objective maximize 3*x + 5*y, add the two linear constraints, solve, and print results. To force integer solutions set variable categories to LpInteger.

python

import pulp

# Define problem
prob = pulp.LpProblem("SimpleLP", pulp.LpMaximize)

# Decision variables (continuous by default)
x = pulp.LpVariable('x', lowBound=0)
y = pulp.LpVariable('y', lowBound=0)

# Objective
prob += 3*x + 5*y, "Maximize_profit"

# Constraints
prob += 2*x + y <= 100, "C1"
prob += x + 2*y <= 80,  "C2"

# Solve (uses default solver — CBC if installed)
prob.solve()

# Report
print("Status:", pulp.LpStatus[prob.status])
print("x =", pulp.value(x))
print("y =", pulp.value(y))
print("Objective =", pulp.value(prob.objective))

Expected solver output:- Status: Optimal- x = 40.0- y = 20.0- Objective = 220.0

To require integer solutions for x and y, create integer variables instead:

python

x = pulp.LpVariable('x', lowBound=0, cat='Integer')
y = pulp.LpVariable('y', lowBound=0, cat='Integer')

or use cat=pulp.LpInteger. Note: solving an integer program is slower (MIP) and may require a suitable solver for large problems.

Unlock Full Question Bank

Get access to hundreds of Yield Optimization & Constraint-Based Modeling interview questions and detailed answers.

Join thousands of developers preparing for their dream job.