Optimization vocabulary is most useful when each term answers a concrete question about a decision: What can change? What rules must hold? What makes one answer better than another? This guide introduces the concepts most useful when reading 4colors articles or evaluating solver results.
The model
Decision variable: A quantity the optimizer may choose, such as assigning an employee to a shift or selecting a route. Some variables are binary, others integer or continuous.
Constraint: A rule that a valid solution must satisfy, such as machine capacity or a minimum staffing level. A hard constraint cannot be violated in the model; a soft constraint expresses a preference, often through a penalty or prioritized objective.
A solution may be feasible without being especially good.
Objective function: The quantity minimized or maximized, such as cost, lateness or task coverage. A model can also contain several objectives with explicit priorities or tradeoffs.
Feasible solution: A complete assignment of the decision variables that satisfies all hard constraints. A solution may be feasible without being especially good.
Optimal solution: A feasible solution whose objective cannot be improved within the mathematical model. This does not mean it is best in every practical sense.
Search and quality
Search space: The set of candidate assignments the algorithm could consider. The set can be enormous without requiring exhaustive examination.
Heuristic: A method designed to produce useful answers, often quickly, without a general guarantee of global optimality.
Exact algorithm: A method capable, when successfully completed under its assumptions, of establishing the best solution and proving it is optimal.
Incumbent: The best feasible solution currently known during a search, where that term is used by the solver.
Bound: A mathematical limit on the best objective that might still be achievable. Bounds help estimate the remaining distance to optimality.
This does not mean it is best in every practical sense.
Optimality gap: A measure of the separation between a known feasible result and an applicable mathematical bound. Its formula and interpretation depend on the solver and objective.
Common model families
Mixed-integer programming (MIP): Optimization with variables that include integers and possibly continuous quantities, typically subject to linear constraints in a mixed-integer linear program.
Constraint programming: A family of methods emphasizing flexible constraint modeling and propagation through discrete choices.
QUBO: Quadratic unconstrained binary optimization, a mathematical model with binary variables and a quadratic objective. It can be approached with classical or quantum-related algorithms.
Ising model: A related spin representation using values such as −1 and +1. QUBO and Ising energy functions can be transformed into one another under standard conventions.
Each definition is most useful alongside an example that shows why the distinction matters in an actual decision.