1 Fundamentals

Linear optimization is a method for choosing the best value of a quantity from among many possibilities when both the goal and the restrictions can be expressed with linear equations or inequalities. It is used to model situations in which each unit of a decision variable contributes proportionally to cost, profit, time, capacity, or another measure of interest. Because linear models are usually easier to analyze than nonlinear ones, the subject has become a central tool in mathematical modeling.

1.1 Definition and terminology

A linear optimization problem asks for the maximum or minimum of a linear objective function over a set of linear constraints. The unknown quantities are called decision variables. The numerical coefficients in the objective and constraints describe how each variable affects the model. A solution is any assignment of values to the variables that satisfies all constraints, while an optimal solution is one that gives the best objective value among all feasible solutions.

1.2 Objective function

The objective function represents the quantity to be optimized. In a profit model, it may measure revenue minus cost; in a logistics model, it may represent total transportation expense; in a scheduling model, it may capture total delay or completion time. Because the function is linear, each variable contributes independently and in direct proportion to its coefficient.

1.3 Constraints

Constraints are the conditions that limit the values of the decision variables. They typically express requirements such as limited labor, finite raw materials, capacity limits, demand levels, or logical relationships. In linear optimization, these restrictions are written as linear equalities or inequalities, which together define the set of admissible solutions.

1.4 Feasible region

The feasible region is the collection of all points that satisfy every constraint simultaneously. In many models, this region forms a convex set, meaning that any line segment joining two feasible points remains entirely within the region. This property is important because it helps explain why local and global optima coincide in linear optimization.

1.5 Optimal solution

An optimal solution is a feasible point at which the objective function attains its best possible value. Depending on the model, there may be a unique optimum, many optimal solutions, or no optimum at all. If the feasible region is empty, the problem is infeasible; if the objective can improve without bound, the problem is unbounded.

2 Mathematical formulation

Linear optimization problems are written in a compact algebraic form so that they can be studied systematically and solved by algorithms. Different formulations are often mathematically equivalent, even when they look different on the page. The choice of formulation may depend on the intended method of solution or on the structure of the application.

2.1 Standard form

A common standard form is to maximize a linear objective subject to equality constraints and nonnegative variables. In matrix notation, this is often written as maximizing cᵀx subject to Ax = b and x ≥ 0. Here A is a matrix of coefficients, b is a vector of right-hand-side values, and c is the objective coefficient vector.

2.2 Canonical form

Canonical form refers to a representation adapted to a particular algorithm or convention. In some contexts it resembles standard form, while in others it places inequalities on one side or isolates one variable as the objective. The term is used somewhat flexibly, but the aim is always to express the problem in a structured linear format.

2.3 General form

The general form allows a mixture of inequalities, equalities, and variable sign conditions. A model may include constraints of the form Ax ≤ b, Ax ≥ b, and Ax = b, along with variables that are unrestricted or bounded in various ways. Any such problem can usually be transformed into an equivalent standard-form model by introducing slack variables, surplus variables, or variable substitutions.

2.4 Variable bounds and sign restrictions

Variables in linear optimization are often constrained to be nonnegative, but other bounds are also common. A variable may be restricted to lie within an interval, or it may be free to take positive and negative values. Sign restrictions are important because they affect both the geometry of the feasible region and the form used by solution algorithms.

3 Geometric interpretation

The geometry of linear optimization provides an intuitive picture of why the theory works. In low dimensions, constraints define half-spaces whose intersection produces a polygon or polyhedron. The objective function then acts like a family of parallel lines or hyperplanes that move across the feasible set until they reach the best attainable point.

3.1 Linear inequalities in two dimensions

In two dimensions, each linear inequality defines a half-plane. The feasible region is the intersection of these half-planes, often forming a polygon or an unbounded region. The optimal solution, when it exists, usually lies on a boundary line or at a corner point of the region.

3.2 Convex polytopes

In higher dimensions, the feasible region is often a convex polytope when it is bounded. Such a set is formed by finitely many linear constraints and has flat faces of various dimensions. Convexity ensures that the region has no holes or inward bends, which simplifies both theory and computation.

3.3 Vertices and extreme points

Vertices, also called extreme points, are corner-like points of a polytope where several constraints meet. A central insight of linear optimization is that optimal solutions can often be found among these points. This fact underlies many algorithms, especially those that move from one vertex to another while improving the objective.

3.4 Supporting hyperplanes

A supporting hyperplane is a flat surface that touches a convex set without cutting through its interior. In linear optimization, the objective function can be visualized as a moving hyperplane. When it first touches the feasible region in the best possible position, it identifies an optimal solution or an optimal face.

4 Theory

The theory of linear optimization explains why the method works and what structural features determine feasibility, boundedness, and optimality. It draws on convex geometry, matrix theory, and duality. These ideas also help characterize the behavior of algorithms and the sensitivity of solutions to changes in the data.

4.1 Existence of optimal solutions

An optimal solution exists when the feasible region is nonempty and the objective is bounded in the desired direction. If the feasible region is closed and bounded, existence is often guaranteed for continuous objectives such as linear functions. However, in unbounded regions, the objective may fail to attain a best value even if it has an infimum or supremum.

4.2 Fundamental theorem of linear programming

A basic theorem of the field states that if a linear optimization problem has an optimal solution, then at least one optimal solution occurs at an extreme point of the feasible region. This result provides the theoretical basis for vertex-based algorithms. It also explains why linear objectives tend to favor corners rather than interior points.

4.3 Convexity and polyhedral theory

The feasible set of a linear program is convex and polyhedral, meaning it is described by finitely many linear constraints. Convexity implies that line segments between feasible points remain feasible, while polyhedral structure makes the region amenable to algebraic and combinatorial analysis. These properties are essential in proving optimality conditions and in designing efficient methods.

4.4 Duality theory

Duality is one of the most powerful ideas in linear optimization. Every problem, called the primal, has an associated dual problem that encodes the same information in a different form. The relationship between the two reveals bounds on the objective, conditions for optimality, and economic interpretations such as shadow prices.

4.4.1 Primal and dual problems

The primal problem is the original optimization model. The dual problem is derived from it by associating dual variables with the constraints of the primal. In many settings, the dual variables measure the marginal value of relaxing each constraint. The two formulations often illuminate different aspects of the same system.

4.4.2 Weak duality

Weak duality states that any feasible solution to the dual provides a bound on any feasible solution to the primal. For maximization problems, a dual feasible solution typically gives an upper bound; for minimization problems, it gives a lower bound. This result holds without requiring optimality and is a key tool for verifying solutions.

4.4.3 Strong duality

Strong duality asserts that, under suitable conditions, the optimal values of the primal and dual problems are equal. When both problems have optimal solutions, this equality connects feasibility, boundedness, and optimality in a precise way. Strong duality is fundamental both theoretically and computationally.

4.4.4 Complementary slackness

Complementary slackness gives a relationship between primal and dual optimal solutions. It states, roughly, that a constraint is either active with zero slack or associated with a zero dual value. This condition is often used to test optimality and to reconstruct one solution from the other.

5 Solution methods

Over the years, a variety of algorithms have been developed to solve linear optimization problems. Some are geometric and intuitive, while others are algebraic and designed for large-scale computation. The best method depends on problem size, sparsity, numerical behavior, and the form of the model.

5.1 Graphical method

The graphical method is used mainly for problems with two decision variables. It involves plotting the constraints, identifying the feasible region, and evaluating the objective function at candidate corner points. Although limited in scope, it is valuable for teaching and for building intuition about the geometry of linear optimization.

5.2 Simplex method

The simplex method is a classical algorithm that moves from one vertex of the feasible region to another, improving the objective at each step when possible. It is widely regarded as one of the most influential algorithms in applied mathematics. In practice, it performs very well on many problems, even though its worst-case complexity can be high.

5.2.1 Pivot operations

Pivot operations update the representation of the current solution by exchanging one basic variable with a nonbasic variable. Each pivot corresponds to moving along an edge of the feasible polytope. Proper pivot selection is crucial for progress and for avoiding pathological behavior.

5.2.2 Basis and basic feasible solutions

A basis is a set of variables chosen to satisfy the equality constraints at a vertex-like point. The corresponding assignment is called a basic feasible solution when it satisfies all restrictions. The simplex method systematically examines these solutions, seeking one with the best objective value.

5.2.3 Degeneracy and cycling

Degeneracy occurs when more constraints are active than are needed to define a vertex, which can cause repeated pivots without objective improvement. In rare cases, this may lead to cycling, where the algorithm revisits the same basis. Special pivot rules and anti-cycling strategies are used to prevent such behavior.

5.3 Interior-point methods

Interior-point methods search through the interior of the feasible region rather than tracing its edges. They use barrier functions and iterative updates to approach an optimal point from within the polytope. These methods are especially effective for very large problems and often have strong polynomial-time guarantees.

5.4 Revised simplex method

The revised simplex method is a computationally efficient version of the simplex algorithm. Instead of manipulating the full tableau, it works with matrix factorizations and updates only the information needed for the current basis. This approach reduces memory use and improves performance on sparse problems.

5.5 Cutting-plane methods

Cutting-plane methods begin with a relaxed model and then add valid inequalities that remove infeasible or suboptimal portions of the search space. Each new cut tightens the formulation without excluding any true optimal solution. These methods are especially useful in integer and mixed-integer settings, where the feasible set has additional combinatorial structure.

6 Special problem types

Many important optimization models extend basic linear optimization by adding integrality requirements, multiple objectives, or special network structure. These variants retain a linear core while introducing new computational and modeling challenges. They are widely studied because they capture realistic decision-making problems.

6.1 Integer linear optimization

Integer linear optimization requires some or all variables to take integer values. This restriction makes the problem significantly harder because the feasible set becomes discrete rather than continuous. Such models are used when decisions are indivisible, such as selecting projects or counting items.

6.2 Mixed-integer linear optimization

Mixed-integer linear optimization allows some variables to be continuous and others integer. This combination is common in planning, design, and scheduling, where certain decisions are binary or count-based while others vary continuously. Mixed-integer models are often solved with branch-and-bound or related techniques.

6.3 Parametric linear optimization

Parametric linear optimization studies how the optimal solution changes as one or more coefficients vary. This includes changes in the objective vector, constraint bounds, or right-hand-side values. The analysis helps identify stability ranges and breakpoints where the optimal basis changes.

6.4 Multiobjective linear optimization

Multiobjective linear optimization involves several objective functions that must be considered simultaneously. Because the objectives may conflict, the goal is often to find Pareto-optimal solutions rather than a single best point. Weighted sums and other scalarization methods are commonly used to explore trade-offs.

6.5 Network flow problems

Network flow problems are a major class of linear optimization models in which variables represent flow through a graph. Examples include transportation, transshipment, assignment, and circulation problems. Their special structure allows for efficient algorithms and a rich combinatorial interpretation.

7 Applications

Linear optimization appears in many practical settings where resources are limited and decisions must be made efficiently. Its flexibility makes it useful in industries that manage production, movement, timing, or allocation. The same mathematical structure can describe a wide variety of real-world processes.

7.1 Production planning

In production planning, linear optimization helps determine how much of each product to manufacture. The objective may be to maximize profit or minimize cost while respecting labor, machine, and material constraints. It is often used to balance capacity against demand.

7.2 Transportation and distribution

Transportation and distribution models allocate goods from sources to destinations at minimum cost or maximum service level. They can account for shipping limits, warehouse capacities, and customer requirements. These models are central to supply chain planning and logistics design.

7.3 Resource allocation

Resource allocation problems distribute scarce resources among competing activities. The goal may be to achieve the highest return, the lowest expense, or the most effective use of time, budget, or materials. Linear optimization provides a systematic way to compare competing uses of limited assets.

7.4 Scheduling

Scheduling applications assign jobs to time periods, machines, or personnel while meeting deadlines and capacity limits. Linear models can represent precedence relations, workload balancing, and completion targets. They are especially useful when exact timing can be approximated by continuous variables.

7.5 Diet and blending problems

Diet and blending models determine combinations of ingredients that satisfy nutritional or quality requirements at minimum cost. These problems are among the classic examples in optimization history. They also apply to fuel mixtures, chemical formulations, and product standardization.

7.6 Finance and portfolio selection

In finance, linear optimization can help allocate capital across assets under budget, risk, or exposure constraints. Portfolio models may seek to maximize expected return or minimize certain costs subject to diversification rules. Linear approximations are often used when the underlying assumptions are simplified for tractability.

8 Computational aspects

Practical linear optimization depends not only on mathematical formulation but also on how algorithms behave on real machines. Large models may contain millions of variables and constraints, making efficiency and reliability important. Numerical issues can influence accuracy, runtime, and the quality of the final answer.

8.1 Algorithm complexity

Theoretical complexity studies how runtime grows with problem size. Some methods have favorable worst-case guarantees, while others are valued for strong practical performance. Complexity analysis helps compare algorithms, but actual running time also depends on structure, sparsity, and data distribution.

8.2 Numerical stability

Numerical stability concerns the effect of rounding errors and finite precision arithmetic. In linear optimization, ill-conditioned matrices or nearly redundant constraints can cause difficulty. Stable preprocessing, scaling, and careful linear algebra are often necessary for dependable results.

8.3 Sensitivity analysis

Sensitivity analysis examines how much the solution changes when coefficients or bounds are modified. It helps identify which parameters are critical and which can vary without altering the optimal basis. This information is valuable in planning because input data are rarely known exactly.

8.4 Post-optimality analysis

Post-optimality analysis extends sensitivity analysis by studying alternative optima, reduced costs, shadow prices, and allowable ranges for coefficients. It helps decision-makers understand the implications of the chosen solution beyond its immediate objective value. Such analysis is especially useful when models support policy or operational decisions.

8.5 Software and solvers

Specialized software packages implement simplex, interior-point, and mixed-integer methods. Modern solvers can exploit sparsity, parallel computation, and preprocessing to handle large instances efficiently. They are commonly integrated into modeling languages and decision-support systems.

Linear optimization is closely connected to several broader areas of optimization. Many of these fields generalize linear models by allowing more complex objectives, uncertainty, or curvature. Others preserve the same geometric intuition while expanding the range of applications.

9.1 Quadratic optimization

Quadratic optimization extends linear programming by allowing a quadratic objective or quadratic constraints. It can model variance, energy, and interaction effects that linear functions cannot capture. Some quadratic problems remain convex and tractable, while others become considerably harder.

9.2 Nonlinear optimization

Nonlinear optimization covers problems in which the objective or constraints are not linear. These models can represent realistic physical, economic, or engineering relationships, but they often require more sophisticated methods. Linear optimization is frequently used as an approximation or subproblem within nonlinear frameworks.

9.3 Stochastic optimization

Stochastic optimization incorporates uncertainty in data such as demand, cost, or supply. Rather than relying on fixed values, it optimizes expected performance or robust outcomes across scenarios. Linear models are often used in two-stage and multistage stochastic formulations.

9.4 Convex optimization

Convex optimization generalizes linear optimization to convex objectives and constraints. It retains many favorable properties, including the absence of false local minima and the availability of efficient algorithms. Linear programs form one of the most important subclasses of convex optimization.

9.5 Robust optimization

Robust optimization seeks solutions that remain effective when model parameters vary within specified uncertainty sets. It is designed for situations in which exact data are unavailable or unreliable. Linear robust models can often be reformulated into tractable optimization problems.