OR POST key terms

A corner-point solution of a linear program in standard form where the nonbasic variables are set to zero and the remaining system yields a unique feasible value for each basic variable.

An iterative algorithm that moves from one basic feasible solution to an adjacent improving one along edges of the feasible polyhedron until no improving adjacent vertex exists, certifying optimality.

The rate of change in the optimal objective value per unit increase in a constraint's right-hand side, valid within the current basis; it equals the corresponding optimal dual variable.

The rate at which the objective changes if a nonbasic variable is forced to increase from zero; it is negative for an entering variable in a minimization problem and zero at alternate optima.

A companion problem assigning a variable to each primal constraint and a constraint to each primal variable, whose optimal value equals the primal optimum under strong duality.

An optimality condition stating that a primal variable and its associated dual slack cannot both be strictly positive, and likewise a primal slack and its dual variable.

A basic feasible solution in which at least one basic variable equals zero; it can cause the simplex method to stall or cycle because a pivot may not improve the objective.

The study of how the optimal solution and objective value respond to changes in coefficients, right-hand sides, or bounds, often reported as allowable ranges for each parameter.

A linear program whose objective can be improved without limit while remaining feasible, typically detected when an entering variable has no positive pivot column entries.

The condition in which no assignment of decision variables satisfies all constraints simultaneously; detected in phase one of the two-phase simplex method by a positive artificial-variable sum.

A network flow model that ships a homogeneous good from supply nodes to demand nodes at minimum cost, solvable by specialized simplex variants or as a min-cost flow.

A special transportation model matching each worker to exactly one job and each job to exactly one worker at minimum total cost, solvable by the Hungarian method.

A network model choosing flows on arcs to satisfy node balance and capacity limits at least total cost; its constraint matrix is totally unimodular, so LP solutions are integral.

A result stating the maximum flow from source to sink in a capacitated network equals the minimum capacity of an s-t cut, providing both an optimality certificate and a bound.

A property of a matrix whose every square submatrix has determinant 0, 1, or -1; it guarantees that LP vertices are integral whenever the right-hand side is integral.

An exact search that partitions an integer program into subproblems and prunes those whose LP relaxation bound cannot beat the best known feasible solution.

The linear program obtained by dropping integrality restrictions from an integer program; its optimal value gives a bound used to prune search or assess the integrality gap.

A valid inequality added to an integer program that excludes fractional LP optima without removing any integer feasible point, progressively tightening the relaxation toward the integer hull.

The difference or ratio between the optimal value of an integer program and that of its LP relaxation, measuring how much the relaxation overstates achievable performance.

For a stable system in steady state, the average number of customers in the system equals the arrival rate multiplied by the average time each customer spends there.

The fraction of time a server is busy, equal to arrival rate divided by service rate for a single server; values at or above one make the queue grow without bound.

A single-server queue with Poisson arrivals, exponential service times, and unlimited waiting room, whose steady-state number in system follows a geometric distribution.

A counting process with independent, stationary increments in which the number of events in an interval of length t is Poisson distributed with mean equal to the rate times t.

A continuous distribution of waiting times until the next event in a Poisson process, characterized by the memoryless property that past waiting carries no information about remaining wait.

A stochastic process whose future depends on the present state only, described by a transition matrix; long-run behavior is given by its stationary distribution when it is irreducible and aperiodic.

A limiting regime in which the probability distribution of a stochastic system stops changing over time, permitting time-average performance measures to be computed independent of initial conditions.

The increase in expected payoff obtained by learning the true state before deciding, computed as the expected payoff with perfect foresight minus the best expected payoff without it.

The expected improvement in payoff from conducting a test or survey before deciding; it equals the expected value with the added information minus the value without it.

A graphical model of sequential decisions under uncertainty with decision nodes, chance nodes, and terminal payoffs, evaluated by backward induction using expected values.

A preference pattern in which a decision maker prefers a certain outcome to a gamble with equal expected value, reflected in a concave utility function over wealth.

The guaranteed amount that makes a decision maker indifferent between receiving it and facing a given gamble; it lies below the gamble's expected value for a risk-averse person.

A decision criterion ranking lotteries by the probability-weighted average of a utility function over outcomes, consistent with a set of rationality axioms for choice under risk.

A strategy profile in which no player can gain by unilaterally changing strategy, given the strategies of the others; it need not be unique or socially efficient.

A strategy that yields a payoff at least as good as any alternative regardless of what opponents do, allowing it to be chosen without predicting others' play.

A two-player competitive setting in which one player's gain exactly equals the other's loss, so mixed-strategy equilibria can be found by linear programming.

The initial segment of a simulation run excluded from statistics so that transient startup conditions do not bias estimates of steady-state performance.

An independent repetition of a simulation from fresh random-number streams, used to obtain sample observations whose variability supports statistical estimation of performance measures.

A variance-reduction technique that drives alternative system configurations with identical random streams so that differences between them are estimated more precisely.

A range of plausible values for a performance measure constructed from sample data at a stated coverage probability, reflecting sampling error rather than model error.

A function whose graph lies below the chord connecting any two of its points; for such functions any local minimum is global, which underlies reliable nonlinear optimization algorithms.

First-order necessary conditions for a constrained optimum involving stationarity of the Lagrangian, primal feasibility, dual feasibility, and complementary slackness; sufficient under convexity.

A technique that moves hard constraints into the objective with penalty multipliers, yielding a bound on the original problem and often decomposing it into easier subproblems.

The observation that an optimal policy for a sequential decision problem has the property that remaining decisions are optimal for the state reached, enabling recursive solution by dynamic programming.

A solution method that decomposes a multistage problem into overlapping subproblems, computes each state's optimal value once, and combines them through a recursion.

The process of establishing that a model represents the real system accurately enough for its intended purpose, typically by comparing outputs with historical data and reviewing assumptions with stakeholders.

The process of confirming that a model is implemented correctly and behaves as its conceptual specification intends, distinct from asking whether the specification matches reality.

The tendency to seek and favor evidence supporting existing beliefs; in modeling practice it argues for pre-specifying assumptions, testing alternatives, and independent review.