OR POST cheat sheet

A model has decision variables, objective, constraints, and parameters; classify as LP, NLP, IP, or DP by functional forms and integrality.

Feasible region is the set of points satisfying all constraints; a solution is optimal if it minimizes (or maximizes) the objective over that set.

Deterministic vs stochastic: if any parameter is random, the model is stochastic (e.g., queueing, simulation, stochastic DP); otherwise deterministic.

Validation checks whether the model represents the real system for its intended use; verification checks whether the model is implemented correctly.

Sensitivity analysis asks how the optimal solution and objective change with parameter perturbations; it is distinct from post-optimality analysis of constraint status.

A model is ill-conditioned if small input changes cause large output changes; check conditioning before trusting numerical solutions.

Common modeling errors: omitted constraints, wrong units, double-counting costs, and confusing rates with totals.

For multiobjective problems, identify Pareto-efficient solutions where no objective can improve without worsening another.

Standard form: maximize c^T x subject to Ax ≤ b, x ≥ 0; convert ≥ constraints by multiplying by −1 and equalities by adding artificial variables for simplex.

Fundamental theorem: if an LP has an optimal solution, at least one optimal solution is a basic feasible solution (extreme point of the feasible polyhedron).

Weak duality: for primal max and dual min, c^T x ≤ b^T y for any primal feasible x and dual feasible y; strong duality holds when both are feasible and bounded.

Complementary slackness: x_j > 0 implies the j-th dual constraint is tight; slack in a primal constraint implies the corresponding dual variable is zero.

Shadow price (dual variable) is the marginal change in optimal objective per unit increase in the right-hand side, valid within the range of feasibility.

Reduced cost of a nonbasic variable equals its objective coefficient minus the dual value of its column; it is zero for basic variables.

Degeneracy occurs when a basic feasible solution has a zero basic variable; it can cause cycling in simplex, resolved by Bland's rule or lexicographic perturbation.

Dual of max c^T x s.t. Ax ≤ b, x ≥ 0 is min b^T y s.t. A^T y ≥ c, y ≥ 0; equality constraints give free dual variables.

Shortest path: Dijkstra for nonnegative arc lengths; Bellman-Ford handles negative arcs and detects negative cycles.

Minimum spanning tree: Kruskal sorts edges by weight and adds if no cycle; Prim grows a tree from a root; both are greedy and optimal.

Max flow/min cut: the maximum s-t flow equals the minimum s-t cut capacity; Ford-Fulkerson and Edmonds-Karp find augmenting paths.

Transportation problem: northwest-corner or least-cost method gives an initial basic feasible solution; MODI/stepping-stone checks optimality via reduced costs.

Assignment problem: Hungarian algorithm solves the linear assignment problem in polynomial time; it is a special case of min-cost flow.

LP relaxation of an integer program gives a lower bound (minimization) or upper bound (maximization); branch-and-bound prunes nodes using these bounds.

Cutting planes (Gomory, cover) tighten the LP relaxation; branch-and-cut combines branching with cutting planes.

Total unimodularity of the constraint matrix guarantees integer optimal vertices for integer right-hand sides; network flow matrices are totally unimodular.

Poisson process: interarrival times are i.i.d. exponential with rate λ; number of arrivals in time t is Poisson(λt); memoryless property.

M/M/1: utilization ρ = λ/μ < 1; L = ρ/(1−ρ), L_q = ρ²/(1−ρ), W = 1/(μ−λ), W_q = ρ/(μ−λ).

Little's law: L = λW applies to any stable queueing system in steady state, where L is average number in system and W is average time in system.

M/M/c: Erlang C gives probability of waiting; L_q = P_wait · ρ/(1−ρ) for c servers with ρ = λ/(cμ).

Markov chain: stationary distribution π satisfies π = πP and Σπ_i = 1; a finite irreducible aperiodic chain has a unique stationary distribution.

Continuous-time Markov chain: generator matrix Q has off-diagonal rates q_ij and diagonal q_ii = −Σ_{j≠i} q_ij; balance equations πQ = 0.

Renewal reward theorem: long-run average reward per unit time equals expected reward per cycle divided by expected cycle length.

For a random variable X, E[X] = ∫ x f(x) dx (continuous) or Σ x p(x) (discrete); Var(X) = E[X²] − (E[X])².

Expected monetary value (EMV) chooses the alternative with highest expected payoff; expected utility (EU) uses a utility function to encode risk attitude.

Risk-averse utility is concave (diminishing marginal utility); risk-seeking is convex; risk-neutral is linear.

Value of perfect information (EVPI) = expected payoff with perfect information − EMV without it; value of sample information (EVSI) = EV with sample − EV without.

Decision tree: roll back from terminal nodes using expected values at chance nodes and max (or min) at decision nodes.

Nash equilibrium: a strategy profile where no player can improve by unilateral deviation; mixed strategies may be required.

Zero-sum game: maximin equals minimax (von Neumann); the value is the saddle point of the payoff matrix.

Dominant strategy: a strategy that yields at least as good a payoff as any other regardless of opponents' actions; dominated strategies can be eliminated.

Prisoner's dilemma illustrates that individual rationality can lead to Pareto-inefficient outcomes.

Discrete-event simulation advances time from event to event using an event calendar (priority queue); state changes only at event times.

Random number generation: linear congruential generators produce pseudo-random U(0,1) numbers; seeds determine reproducibility.

Input modeling: fit distributions (exponential, normal, triangular) to data; use goodness-of-fit tests (chi-square, Kolmogorov-Smirnov).

Output analysis: for independent replications, use sample mean and t-confidence interval; for one long run, use batch means or spectral methods.

Warm-up (transient) period should be deleted before steady-state analysis; initial conditions bias early observations.

Variance reduction: common random numbers, antithetic variates, control variates, and importance sampling improve precision without more replications.

Verification (debugging the model) vs validation (model represents reality); use face validity, sensitivity analysis, and comparison with real data.

Confidence interval half-width decreases proportionally to 1/√n; to halve it, quadruple the number of replications.

For unconstrained differentiable f, first-order condition ∇f(x*) = 0; second-order condition: Hessian positive definite (min) or negative definite (max).

Convex optimization: any local minimum is global; KKT conditions are necessary and sufficient under constraint qualification (e.g., Slater).

Lagrangian L(x,λ) = f(x) + Σ λ_i g_i(x); KKT: stationarity, primal feasibility, dual feasibility (λ_i ≥ 0 for g_i ≤ 0), complementary slackness.

Dynamic programming principle of optimality: an optimal policy has the property that remaining decisions are optimal for the state resulting from the first decision.

Bellman equation: V(s) = max_a { r(s,a) + γ Σ_{s'} P(s'|s,a) V(s') } for discounted infinite-horizon problems.

For deterministic finite-horizon DP, compute backward from terminal stage: V_t(s) = max_a { r_t(s,a) + V_{t+1}(s') }.

Curse of dimensionality: state space grows exponentially; approximate DP and reinforcement learning mitigate.

Quadratic programming: minimize ½x^TQx + c^Tx subject to Ax ≤ b; if Q positive semidefinite, problem is convex.

OR code of ethics (INFORMS): practice competently, avoid conflicts of interest, protect confidentiality, report results honestly, and do not misrepresent qualifications.

Model documentation should state assumptions, data sources, validation evidence, and limitations so decision makers can judge applicability.

When presenting results, distinguish model outputs from real-world outcomes; quantify uncertainty with intervals or scenarios.

Sensitivity analysis is essential when data are uncertain; report how optimal decisions change across plausible parameter ranges.

Stakeholder analysis: identify decision makers, affected parties, and constraints; ensure the model addresses the actual decision.

Data privacy and security: anonymize sensitive data, obtain consent where required, and follow organizational and legal policies.

Avoid scope creep by defining the problem statement and success criteria before model building; revisit with clients as needed.

Professional responsibility includes disclosing model limitations and refusing to use models to mislead or cause harm.