Operations Research Glossary

A combinatorial optimization problem of assigning agents to tasks on a one-to-one basis to minimize total cost.

A technique in LP for handling artificial variables in the simplex method by assigning a very large penalty coefficient.

An algorithmic framework for solving integer programming problems by exploring and pruning a tree of subproblems.

Finding an optimal solution from a finite but very large set of discrete alternatives.

A mathematical condition that restricts the set of feasible solutions in an optimization problem.

Optimization of a convex objective function over a convex feasible set, guaranteeing that any local optimum is global.

A variable whose value is determined by the optimization model, representing a choice to be made.

A graph algorithm for finding the shortest path from a source node to all other nodes with non-negative weights.

A companion optimization problem derived from the primal LP that provides bounds and economic interpretation of constraints.

A method of solving problems by breaking them into overlapping subproblems and storing their solutions.

A solution that satisfies all the constraints of an optimization problem.

A practical method for finding good-enough solutions to problems where exact methods are too slow or impractical.

An optimization problem in which some or all decision variables are restricted to integer values.

Optimization of a linear objective function subject to linear equality and inequality constraints.

A stochastic process satisfying the memoryless property where the future depends only on the present state.

A high-level algorithmic framework for solving hard optimization problems that guides subordinate heuristics.

A computational technique using repeated random sampling to estimate the behavior of complex systems.

A class of optimization problems involving the movement of commodities through a network of nodes and arcs.

A class of problems for which no known polynomial-time algorithm exists; solutions cannot be efficiently computed as problem size grows.

The mathematical function to be maximized or minimized in an optimization problem.

The mathematical study of waiting lines, analyzing arrival processes, service mechanisms, and performance metrics.

The study of how changes in input parameters affect the optimal solution and objective value.

The rate of change of the optimal objective value with respect to a unit increase in a constraint's right-hand side.

Dantzig's algorithm for solving linear programming problems by moving between vertices of the feasible polytope.

Optimization under uncertainty, where some parameters are modeled as random variables with known distributions.