OR POST flashcards
OR POST · Build recall with a focused review session.
32 cards. Read the term and the definition here. The deck at the top of this page is optional.
- Basic feasible solution
- A feasible solution of an LP that is also a basic solution, corresponding to a vertex (extreme point) of the feasible polyhedron when the matrix has full row rank.
- Shadow price
- The dual variable associated with a constraint; it gives the marginal change in the optimal objective value per unit increase in the right-hand side, within the range of feasibility.
- Complementary slackness
- In LP duality, for optimal primal x and dual y: x_j > 0 implies the j-th dual constraint is tight, and slack in a primal constraint implies the corresponding dual variable is zero.
- Weak duality
- For a primal maximization LP and its dual minimization, any primal feasible objective value is at most any dual feasible objective value; equality holds at optimality under strong duality.
- Degeneracy in LP
- A basic feasible solution is degenerate if at least one basic variable equals zero; degeneracy can cause simplex cycling, which Bland's rule or perturbation resolves.
- Total unimodularity
- A matrix property where every square submatrix has determinant 0, +1, or −1; it guarantees integer optimal vertices for LPs with integer right-hand sides.
- Branch and bound
- An exact algorithm for integer programming that partitions the feasible region and prunes nodes using bounds from LP relaxations, terminating when no better solution can exist.
- Max-flow min-cut theorem
- In a capacitated network, the maximum flow from source to sink equals the minimum capacity of an s-t cut; this is a fundamental result in network optimization.
- Dijkstra's algorithm
- A label-setting algorithm that finds shortest paths from a source to all nodes in a graph with nonnegative arc lengths by repeatedly selecting the closest unvisited node.
- Little's law
- For a stable queueing system in steady state, L = λW, where L is the average number in system, λ is the arrival rate, and W is the average time in system.
- M/M/1 queue
- A single-server queue with Poisson arrivals and exponential service times; utilization ρ = λ/μ < 1, and average number in system L = ρ/(1−ρ).
- Poisson process
- A counting process with independent stationary increments; the number of arrivals in an interval of length t is Poisson with mean λt, and interarrival times are exponential.
- Stationary distribution
- A probability distribution π over states of a Markov chain such that π = πP; if the chain is irreducible and aperiodic, it converges to this distribution.
- Erlang C formula
- Gives the probability that an arrival waits in an M/M/c queue; it is used to compute waiting-time performance and staffing levels in multi-server systems.
- Expected monetary value
- The probability-weighted average of monetary payoffs for a decision alternative; EMV is used in decision trees under risk neutrality.
- Risk aversion
- A preference for a certain outcome over a gamble with equal or higher expected value; represented by a concave utility function.
- Value of perfect information
- The expected increase in payoff from obtaining perfect information before deciding, equal to the expected payoff with perfect information minus the EMV without it.
- Nash equilibrium
- A strategy profile in a game where no player can improve their payoff by unilaterally changing strategy, holding others' strategies fixed.
- Maximin criterion
- A conservative decision rule that selects the alternative whose worst-case payoff is best; used under uncertainty when probabilities are unknown.
- Discrete-event simulation
- A simulation where system state changes only at discrete event times, advanced by an event calendar; used to model queues, inventories, and production systems.
- Warm-up period
- The initial transient phase of a simulation that is deleted before steady-state analysis to reduce bias from initial conditions.
- Common random numbers
- A variance reduction technique that uses the same random number streams for different system configurations to induce positive correlation and sharpen comparisons.
- Batch means
- A method for estimating confidence intervals from a single long simulation run by dividing it into approximately independent batches and treating batch means as i.i.d.
- Verification and validation
- Verification checks that the model is implemented correctly; validation checks that the model adequately represents the real system for its intended purpose.
- KKT conditions
- First-order necessary conditions for nonlinear programming: stationarity, primal feasibility, dual feasibility, and complementary slackness; sufficient under convexity and constraint qualification.
- Bellman equation
- A recursive equation expressing the optimal value of a dynamic programming problem in terms of the current reward and the optimal value of the next state.
- Convex optimization
- A minimization problem with a convex objective and convex feasible set; any local minimum is global, and KKT conditions are sufficient under constraint qualification.
- Principle of optimality
- In dynamic programming, an optimal policy has the property that remaining decisions are optimal for the state resulting from the first decision.
- Curse of dimensionality
- The exponential growth in state space and computational effort as the number of state variables increases in dynamic programming.
- Model validation
- The process of determining whether a model is an adequate representation of the real system for the intended decision, often using historical data and expert review.
- Sensitivity analysis
- The study of how changes in model parameters affect the optimal solution or objective; it identifies which inputs most influence decisions and where more data are needed.
- Pareto efficiency
- A solution is Pareto efficient if no objective can be improved without worsening at least one other objective; used in multiobjective optimization and game theory.