Linear Programming Interview Questions: Constraints, Duality, and Infeasibility

A solver returns x = 2, y = 2 and an objective value of 10. That answer is useful only if you can explain why the allocation is feasible, why no feasible allocation can do better, and what changes when capacity increases.

Linear programming interview questions test that chain of reasoning. Writing an objective function is one step; interpreting bounds, dual values, and failure statuses completes the decision. A numerically successful solve can still optimize the wrong business problem.

Evidence boundary: SciPy and Google OR-Tools documentation support the implementation facts below; Boyd and Vandenberghe provide the duality reference. Interview recommendations are editorial inference, not candidate reports or employer-specific process claims.

How do you translate a business problem into an LP?

Start with decision variables and units. In an original production example, let x and y be divisible batches of two products. A batch of either product consumes one shared capacity unit. Product X earns three profit units per batch; Y earns two.

Shared capacity is four units, X has a separate limit of two batches, and Y has a separate limit of three. The model is:

maximize 3x + 2y
subject to
    x + y <= 4
    x <= 2
    y <= 3
    x >= 0, y >= 0

“Divisible” is deliberate. If batches must be whole, integrality is part of the model, even if this example happens to have an integer optimum.

Before solving, ask whether profit coefficients include all relevant variable costs, whether capacity is actually interchangeable, and whether unused capacity is allowed. Changing x + y ≤ 4 to equality requires using every capacity unit, which is a different business rule.

Official implementation fact: OR-Tools’ linear optimization example shows continuous decision variables, linear constraints, an objective, and explicit checks on solver status. Use that structure, while validating your own application assumptions independently.

A common modeling error mixes units. If X consumes two labor hours and Y consumes one, the shared constraint must use those coefficients. Profit per item and decision variables measured in thousands of items also need compatible scaling. Annotate units before trusting a matrix of numbers.

Can you solve the allocation and prove the answer?

The feasible allocation (2, 2) uses all four shared units, respects both product limits, and earns 3×2 + 2×2 = 10.

To prove optimality directly, rewrite the objective:

3x + 2y = 2(x + y) + x ≤ 2×4 + 2 = 10.

Every feasible point has profit at most 10. Our feasible point reaches that bound. Therefore it is optimal. This proof is small enough to explain aloud without a solver.

The same calculation produces a dual certificate. Assign nonnegative multipliers lambda_1, lambda_2, and lambda_3 to the three upper-bound constraints. The dual is:

minimize 4 lambda_1 + 2 lambda_2 + 3 lambda_3
subject to
    lambda_1 + lambda_2 >= 3
    lambda_1 + lambda_3 >= 2
    lambda_1, lambda_2, lambda_3 >= 0

Choose multipliers (2, 1, 0). Both dual inequalities hold, and the dual objective is 4×2 + 2×1 + 3×0 = 10.

Certificate component	Original example
Primal feasibility	(x, y) = (2, 2) satisfies every constraint
Primal value	10
Dual feasibility	(2, 1, 0) satisfies both dual inequalities
Dual bound	10
Conclusion	A feasible solution reaches a valid upper bound

Boyd and Vandenberghe’s duality chapter explains weak duality, strong duality, and complementary slackness. Here, the matching feasible values establish the result directly. You do not need to assert that every optimization problem has zero duality gap.

This is also a useful code-review tool. If a solver reports a profit above 10 for the stated model, either the inputs, objective sign, constraints, or interpretation are wrong. A hand-derived bound catches errors that a solver’s success flag cannot.

What does complementary slackness tell you?

At the original optimum, shared capacity and X’s limit are tight. Y’s upper limit has slack one because 3 − 2 = 1. Its multiplier is zero in our certificate.

The products of each multiplier and its associated primal slack are all zero. The dual inequalities are also tight for both positive decision variables. These observations connect the allocation to its certificate.

Do not reverse the implication too strongly. A constraint with positive multiplier must be tight at a compatible optimum, but a tight constraint need not have a positive multiplier. Redundancy or degeneracy can produce a tight constraint with zero marginal value.

For an original follow-up, add the redundant constraint 2x + 2y ≤ 8. It is tight whenever shared capacity is tight, but it does not introduce a new independent resource. Dual attribution can be nonunique. Reporting a unique economic price for every listed constraint would overstate what the model identifies.

Editorial inference: When several constraints describe the same bottleneck, explain the nonuniqueness and test a concrete perturbation. A stakeholder usually needs to know the value of a real capacity change, not the arbitrary allocation of multipliers across redundant rows.

How do you interpret SciPy’s objective and shadow prices?

Official implementation fact: scipy.optimize.linprog minimizes an objective, accepts A_ub @ x ≤ b_ub, and uses nonnegative variable bounds by default. It returns residuals and marginal values; the official API example shows how a right-hand-side perturbation changes the minimized objective.

To maximize our profit, minimize its negative:

from scipy.optimize import linprog

result = linprog(
    c=[-3.0, -2.0],
    A_ub=[[1.0, 1.0], [1.0, 0.0], [0.0, 1.0]],
    b_ub=[4.0, 2.0, 3.0],
    bounds=[(0.0, None), (0.0, None)],
    method="highs",
)
assert result.success
profit = -result.fun

The original numerical fixture yields (2, 2), minimized value −10, and inequality marginals [-2, -1, 0]. Their signs describe sensitivity of the minimized negative-profit objective. The corresponding profit improvements are positive two and one for the first two capacity limits.

Increasing shared capacity from 4 to 4.1 permits (2, 2.1), giving profit 10.2. That matches the local prediction of two additional profit units per shared capacity unit.

Now increase shared capacity to 6. The product limits still cap production at (2, 3), giving profit 12. Extrapolating the old shadow price would predict 14, which is impossible under those limits. The active constraints changed.

Shared capacity	Best allocation	Profit	Meaning
4.0	(2, 2)	10.0	Starting optimum
4.1	(2, 2.1)	10.2	Small perturbation follows local marginal
5.0	(2, 3)	12.0	Y’s limit becomes tight
6.0	(2, 3)	12.0	Extra shared capacity no longer helps

Shadow prices depend on the model, current solution region, and units. They are not universal willingness-to-pay estimates. A real expansion may also change costs or other constraints, in which case you need a new model rather than a longer extrapolation.

How do you distinguish infeasible, unbounded, and unsuccessful solves?

An infeasible model has no point satisfying all constraints. An unbounded objective can improve indefinitely along feasible choices. A time limit or numerical difficulty is neither a proof of infeasibility nor a usable optimality certificate.

Use two original one-variable exercises:

Infeasible: Require x ≥ 3 and x ≤ 2. Convert the first to −x ≤ −3. Adding the two inequalities gives 0 ≤ −1, an explicit contradiction. The objective is irrelevant to this contradiction.

Unbounded: Minimize −x with only x ≥ 0. Larger x remains feasible and drives the objective downward without limit. Adding x ≤ 2 would bound it, but inventing that constraint solely to make the solver happy changes the problem.

Official implementation fact: SciPy documents distinct linprog status codes for a successful solve, an iteration/time limit, infeasibility, unboundedness, and numerical difficulties. Check the message and fields rather than reading result.x indiscriminately. See the API status documentation.

A debugging answer should inspect bounds and inequality directions first. Default nonnegative bounds can create unintended infeasibility if a variable was meant to be free. A missing demand or budget constraint can create unintended unboundedness.

Then inspect coefficient magnitudes, tolerances, and the exact model passed to the solver. Poor scaling can complicate numerical diagnosis. Preserve a reproducible instance so another engineer can distinguish an input bug from a solver issue.

When do integer decisions or nonlinear costs change the problem?

An LP treats variables as continuous unless an appropriate integrality mechanism or different model is specified. Rounding a relaxed solution is not a general feasibility-preserving method.

Consider an original staffing constraint 2x ≥ 3, with x representing an indivisible employee. The continuous minimum is 1.5. Rounding down violates coverage; rounding up changes the objective. Larger allocation models can violate several coupled constraints after independent rounding.

Editorial inference: State whether a relaxation is a bound, a heuristic input, or the final deployable decision. If integrality matters, choose a supported mixed-integer formulation and check that the returned solution meets the operational rules.

Linearization also requires a valid construction. To penalize |z| in a minimized objective, introduce t ≥ z and t ≥ −z with a positive penalty coefficient on t. Minimization then pushes t to the absolute value when other constraints permit it. If you omit the objective pressure or reverse the inequalities, the auxiliary variable may not have the claimed interpretation.

Fixed activation costs, products of decision variables, and arbitrary nonlinear utility require additional modeling work. Do not rename them “linear” because they fit in a spreadsheet. Write the expression, identify the nonlinearity, and explain the transformation or different solver family you propose.

What would you verify before deploying an allocation?

An original release checklist begins with the returned variables in business units. Recompute each constraint from those values, using an explicit tolerance appropriate to the coefficient scale. Recompute the objective independently and confirm that the maximization/minimization sign conversion happened once.

Then check the downstream representation. A feasible fractional batch may become infeasible if an API truncates it to an integer. A quantity expressed in thousands may be transmitted as individual units. Solver validation ends at the model boundary; operational validation must also inspect the translation into actions.

For the worked production case, changing the order of variables from X,Y to Y,X without changing the objective and constraint columns answers a different problem. Preserve named mappings when building arrays, and save a compact instance showing the data used for the decision.

Editorial inference: For repeated optimization, monitor status changes, constraint violations, objective movement, and unexpected shifts in active limits. Retain the previous feasible plan only if it remains valid under current constraints; yesterday's optimum is not automatically today's fallback.

If stakeholders ask why production changed, the dual certificate and perturbation trace provide a concrete explanation. They show which resource constrained the original plan and why additional capacity eventually stopped helping. That is more useful than a statement that the optimizer selected a different answer.

Sources and Further Reading

• SciPy: linprog inputs, bounds, statuses, and marginals
• Google OR-Tools: A linear optimization example
• Boyd and Vandenberghe: Convex Optimization, including duality and sensitivity