Skip to main content

Linear-Programming Model Patterns

Most useful LPs combine a small vocabulary of patterns. The algebra is simple; choosing the correct meaning, unit, and hardness is the difficult part.

Prerequisites​

Complete convexity and local versus global optima.

Learning goals​

  • Recognize capacity, minimum-service, balance, and bound patterns.
  • Convert a soft target into a nonnegative shortfall with a dimensioned penalty.
  • Keep adjusted objectives separate from raw outcomes.
  • Identify patterns that require integer or nonlinear models instead.

Reusable patterns​

  • Capacity: aTx≤ba^Tx\le b, with resource use and capacity in the same unit.
  • Minimum requirement: aTx≥ra^Tx\ge r; negate both sides for a <= solver interface.
  • Balance: inflow minus outflow equals a declared supply or demand.
  • Bounds: li≤xi≤uil_i\le x_i\le u_i, including explicit sign restrictions.
  • Soft target: for xC≥22x_C\ge22, introduce shortfall s≥0s\ge0 and enforce xC+s≥22x_C+s\ge22.

A hard constraint must never be violated in the model. A soft target may be missed at an explicit cost. If ss is clinic batches per week, its penalty must be benefit points per missing clinic batch so the adjusted objective remains benefit points per week.

Worked example​

Compare two stakeholder-chosen shortfall penalties. The resource capacities remain hard constraints in both cases.

import numpy as np
from scipy.optimize import linprog

A = np.array([[2.0, 1.0, 0.0],
[1.0, 2.0, 0.0],
[0.0, -1.0, -1.0]])
b = np.array([40.0, 50.0, -22.0])
for penalty in (2.0, 12.0):
c = np.array([-8.0, -6.0, penalty])
result = linprog(c, A_ub=A, b_ub=b,
bounds=[(0.0, None)] * 3, method="highs")
if result.status != 0:
raise RuntimeError(result.message)
workshop, clinic, shortfall = result.x
raw = 8 * workshop + 6 * clinic
adjusted = raw - penalty * shortfall
print(f"penalty={penalty:.0f} workshop={workshop:.1f} clinic={clinic:.1f} shortfall={shortfall:.1f} raw_points={raw:.1f} adjusted_points={adjusted:.1f}")

Expected output:

penalty=2 workshop=10.0 clinic=20.0 shortfall=2.0 raw_points=200.0 adjusted_points=196.0
penalty=12 workshop=6.0 clinic=22.0 shortfall=0.0 raw_points=180.0 adjusted_points=180.0

The higher penalty makes the target bind but reduces raw predicted benefit. The solver did not discover that 12 is ethically or operationally correct; a stakeholder selected the exchange rate.

Limitations and common mistakes​

  • Never soften legal, safety, or physical requirements merely to obtain feasibility.
  • A huge penalty can create scaling problems and still fails to express lexicographic priority precisely.
  • Ratios, either/or rules, fixed setup costs, and whole-unit choices may need reformulation or discrete variables.
  • Slack and shortfall variables need names, nonnegative bounds, and units.
  • Report both raw outcomes and penalty-adjusted objectives; otherwise readers cannot see the tradeoff.

Practice​

Model a hard minimum of 22 clinic batches and compare it with the penalty-12 soft target. Then propose a case where shortfall is acceptable and a case where it is not.

Next steps​

Interpret resource values without overclaiming in duality and shadow prices.

Primary sources​

Checked 2026-10-18: Stanford EE364A, Linear Programming; Boyd and Vandenberghe, Convex Optimization, linear and vector optimization; SciPy 1.18.1, linprog and linprog(method="highs").