1 Problem formulation
Linear programming (LP) models decisions where both the performance goal and the resource usage change linearly with the decision quantities. The task is to optimize a linear objective while obeying linear constraints that describe limits and requirements.
1.1 Decision variables and constraints
1.1.1 Equality vs. inequality constraints
Constraints in LP are expressed either as equalities (exact requirements) or inequalities (allowed ranges). An equality might represent a conservation rule or a fixed total, while inequalities typically encode capacity limits, budget ceilings, minimum service levels, or tolerance bands. In practice, both types are handled within the same mathematical framework by converting them to equivalent forms used by standard LP algorithms.
1.1.2 Feasible region as a convex polyhedron
All points that satisfy every constraint form the feasible region. Because each constraint is linear, the feasible region is a convex polyhedron (or a related convex set, depending on degeneracies and unbounded directions). The convexity implies that any line segment between two feasible solutions remains feasible, which is central to why LP algorithms can search efficiently.
1.1.3 Objective function: maximize or minimize
The objective function is a linear expression in the decision variables. Models may seek a maximum (e.g., profit, throughput) or a minimum (e.g., cost, risk, waste). The objective coefficients represent how strongly each decision variable contributes to the goal, and they become important in duality and sensitivity analysis.
1.2 Standard forms of LP
1.2.1 Canonical and standard representations
To apply generic solvers, LPs are often rewritten in standard or canonical forms that standardize constraint directions and variable types. While different textbooks use different conventions, the key idea is to express every model using a consistent set of building blocks, such as a mix of nonnegativity variables and inequality constraints with uniform orientation.
1.2.2 Variable sign restrictions and transformations
Many algorithms assume variables are nonnegative. When a variable is free to take positive or negative values, it can be represented as the difference of two nonnegative variables. When a variable has an upper or lower bound, it can be shifted and/or decomposed into nonnegative components so that the solver can work within its expected form.
1.2.3 Handling free variables and slack variables
Slack variables measure how much inequality constraints are not tight. Introducing slack turns a “less-than-or-equal” constraint into an equality by adding an extra nonnegative quantity. Conversely, surplus variables can handle constraints of the opposite direction. Free variables and sign-restricted variables are handled via transformations that preserve the original model’s meaning.
1.3 Examples from applied settings
1.3.1 Diet and mix problems
Diet and ingredient-mix LPs aim to choose quantities of items (foods, chemicals, materials) to meet nutritional or composition requirements. Typical constraints include minimum nutrient levels, maximum allowable limits, and sometimes total weight or cost ceilings. The objective often minimizes total cost or minimizes deviation from targets while keeping every ingredient quantity within usable bounds.
1.3.2 Production and capacity planning
Production models use decision variables for how much to produce of each product over a planning horizon. Constraints encode machine time, labor availability, inventory limits, and sometimes demand requirements. The objective may maximize profit or minimize production and holding costs, with coefficients reflecting unit profits or unit costs.
1.3.3 Transportation and logistics basics
Transportation LPs allocate supply from multiple sources to multiple destinations while satisfying demand. Decision variables represent shipped quantities along each route. Constraints ensure each destination’s demand is met and each source’s shipment does not exceed its supply. A linear shipping cost per unit makes the objective straightforward, and the resulting model is closely related to network flow structure.
2 Geometry and fundamental properties
LP’s geometry explains both computational behavior and theoretical guarantees. The feasible region’s shape—convex and piecewise linear—determines where optimal solutions can occur and what kinds of pathologies may arise.
2.1 Convexity and extreme points
2.1.1 Why optimal solutions occur at vertices
Because the objective is linear over a convex polyhedron, an optimum is reached at an extreme point (vertex) of the feasible region, provided the optimum exists and the feasible region is not empty. Intuitively, moving away from a vertex along feasible directions cannot improve the objective indefinitely without crossing into less favorable regions, so the best value is attained at a boundary corner.
2.1.2 Degeneracy and alternate optima
Degeneracy occurs when multiple vertices yield the same objective value or when a vertex can be described with more active constraints than the dimension would normally require. Alternate optima appear when there exists an entire edge or face along which the objective remains constant. In such cases, different bases or solution representations may be equally optimal, even though the objective value is identical.
2.2 Feasibility and unboundedness
2.2.1 Infeasible LPs
An LP is infeasible if no point satisfies all constraints simultaneously. Geometrically, the feasible region is empty. Many solver workflows include feasibility checks or presolve steps that attempt to detect emptiness early, since further optimization is impossible if the feasible set is void.
2.2.2 Unbounded objectives
An LP is unbounded if the objective can be improved without limit while remaining feasible. Geometrically, this means the feasible region extends infinitely in some direction that improves the objective. Detecting unboundedness is a core part of algorithm termination logic, especially in methods that explore edges of the polyhedron.
2.3 Scaling, redundancy, and simplification
2.3.1 Removing redundant constraints
Not every constraint affects the feasible region. Redundant constraints can be removed without changing the set of feasible solutions. Eliminating them can reduce problem size and improve numerical behavior, particularly for large models where many constraints overlap or repeat information.
2.3.2 Interpreting constraint activity
At an optimal solution, some constraints are active (tight), while others are slack. Activity patterns guide the economic meaning of dual variables and influence sensitivity results: constraints that bind at optimum often determine the structure of the best plan.
2.3.3 Numerical stability considerations
Real-world data introduce rounding and scaling effects. If coefficients vary by many orders of magnitude, solvers may suffer numerical difficulties, such as unstable pivot choices or inaccurate constraint satisfaction. Scaling variables and constraints, using consistent units, and relying on solver tolerances are common practices to mitigate these issues.
3 Solving methods
Solving an LP means identifying an optimal feasible solution or certifying infeasibility/unboundedness. Two main algorithm families dominate practice: simplex-type methods and interior-point methods.
3.1 Simplex method (high-level)
3.1.1 Basic feasible solutions
Simplex operates on vertices of the feasible polyhedron by representing solutions in terms of a basis. A basic feasible solution corresponds to choosing a set of constraints (and variables derived from them) that uniquely determine a vertex while maintaining feasibility. The method traverses these basic feasible points toward improvement.
3.1.2 Pivoting and moving along edges
At each iteration, simplex performs a pivot that changes which variables are in the basis. This pivot corresponds to moving along an edge of the feasible region to a neighboring vertex. The choice of entering and leaving variables dictates the direction of movement and is the main customizable aspect of simplex implementations.
3.1.3 Stopping criteria and iteration logic
Simplex terminates when the current basis satisfies optimality conditions, meaning no feasible move can improve the objective. It may also stop early if it detects infeasibility or unboundedness. Iteration logic includes bookkeeping of the basis, objective value, and constraint satisfaction, ensuring that each pivot preserves feasibility.
3.2 Interior-point methods
3.2.1 Barrier formulation intuition
Interior-point methods reformulate the problem by adding a barrier that discourages iterates from approaching the boundary where constraints become tight or violated. For inequality-constrained problems, feasibility requires strict satisfaction, so the algorithm starts in the interior and gradually moves toward the optimum, balancing progress against barrier penalties.
3.2.2 Central path concept
The barrier approach traces a curve of near-optimal solutions called the central path. As the barrier parameter decreases, solutions along this path typically approach an optimal solution of the original LP. This geometric picture helps explain why interior-point methods can converge smoothly even when the optimal face lies on the boundary.
3.2.3 Convergence behavior overview
Interior-point methods often exhibit fast convergence in terms of reducing the duality gap. In practice, they require careful stopping tolerances and feasibility checks, since the method works with “near interior” iterates. Once close to the optimum, postprocessing or crossover may be used to recover a vertex solution when needed.
3.3 Practical algorithm considerations
3.3.1 Initialization strategies
For simplex, an initial feasible basis is needed or an auxiliary phase is used to find feasibility. Interior-point methods require a strictly feasible starting point or a method to construct one via relaxations. Initialization can strongly affect runtime for difficult or ill-scaled instances.
3.3.2 Choosing pivot rules or step sizes
Simplex performance depends on how entering variables and leaving variables are selected; pivot rules aim to reduce unnecessary cycling and improve progress. Interior-point methods require step-size strategies that maintain stability and keep iterates inside the feasible region while still moving effectively toward the central path.
3.3.3 Detecting cycling and degeneracy
Degeneracy can cause simplex to revisit bases without objective improvement. Cycling detection and anti-cycling pivot rules address this issue. Many solver implementations also include perturbation strategies or specialized rules that handle degenerate vertices more robustly.
4 Duality theory
Duality ties together optimization problems in pairs and provides interpretable bounds. It underpins theoretical guarantees, solver diagnostics, and economic meanings such as prices and shadow values.
4.1 Primal–dual relationships
4.1.1 Forming the dual problem
Every LP in primal form has an associated dual LP constructed by systematically swapping roles between constraints and variables. Inequality directions and sign conventions determine whether dual variables are constrained to be nonnegative or free. The dual objective typically uses the right-hand side of primal constraints as coefficients.
4.1.2 Dual variables as prices/sensitivities
Dual variables can be interpreted as marginal values: how the optimal objective would change under small perturbations of the primal constraints. In many resource allocation contexts, they serve as implicit “prices” for tightening or relaxing constraints, giving a compact summary of which limitations govern the optimal solution.
4.2 Weak and strong duality
4.2.1 Upper/lower bounds interpretation
Weak duality states that the dual objective provides a bound on the primal objective: for a maximization primal, the dual value is an upper bound (and for a minimization primal, the dual provides a lower bound). This relationship allows one to certify optimality without fully enumerating vertices in principle.
4.2.2 Optimality connection between primal and dual
Strong duality states that if the primal problem has an optimal solution under standard regularity conditions, then the optimal objective values of the primal and dual coincide. This theorem provides a cornerstone for convergence analysis and for using dual information to validate primal solutions.
4.3 Complementary slackness
4.3.1 Interpreting slack and binding constraints
Complementary slackness connects primal constraint slack with the corresponding dual variable values. If a primal constraint is slack at optimum (not binding), the associated dual variable must be zero. Conversely, if a dual variable is positive, the primal constraint it corresponds to must be binding.
4.3.2 Implications for solution structure
This condition helps explain the structure of optimal bases: only certain constraints carry positive dual prices, and only certain variables become zero/nonzero in compatible ways. It also guides sensitivity interpretations and supports checks during computational verification.
5 Optimality conditions and sensitivity
Beyond finding a single optimum, LP theory provides tools to interpret which decisions matter and how changes in data affect outcomes.
5.1 Reduced costs and marginal values
5.1.1 Nonbasic variables and optimality checks
In simplex terminology, reduced costs quantify how much the objective would improve if a nonbasic variable were increased from zero, while maintaining feasibility to first order. When all reduced costs satisfy optimality conditions (with sign depending on maximize/minimize conventions), the current basic feasible solution is optimal.
5.1.2 Interpreting shadow prices
Shadow prices are dual-variable interpretations attached to constraints. They reflect the objective change for a small increase in a constraint’s right-hand side, assuming the solution basis remains stable. Shadow prices are most meaningful for constraints that are binding in the optimal solution.
5.2 Sensitivity analysis
5.2.1 Changing objective coefficients
If objective coefficients change, the set of optimal solutions may shift. Sensitivity analysis determines a range of coefficient values for which the current basis remains optimal. Outside those ranges, the solution can move to a different vertex or face, changing both decision values and possibly which constraints bind.
5.2.2 Changing right-hand side values
When the right-hand side of constraints changes, feasibility and optimality can respond differently. Feasibility ranges identify how far the data can move before the current basis becomes infeasible, while optimality ranges identify how far until a different basis yields a better objective.
5.2.3 Feasible ranges and solution stability
Together, feasibility and optimality ranges describe stability of the plan. In stable regimes, small perturbations allow rapid re-interpretation without fully re-solving. In unstable regimes, recomputation may be required because the model’s active set changes.
5.3 Post-optimality insights
5.3.1 Identifying alternate optimal bases
If multiple bases correspond to the same objective value, post-optimality analysis can identify them. Alternate optimal bases correspond to faces of the feasible polyhedron where the objective is constant, often revealed through zero reduced costs and compatible dual information.
5.3.2 Re-optimizing after small perturbations
When data shift slightly, the current solution can be used as a warm start. Many solvers reuse basis information (especially in simplex-based methods) and adjust efficiently to reach the new optimum. This approach leverages the fact that optimal bases typically change gradually under small parameter variations.
6 Modeling and computational workflow
Effective LP use involves careful modeling, clean mathematical translation, and reliable interpretation of solver output. The workflow typically moves from real tasks to a linear optimization model, then through implementation checks and result validation.
6.1 From real task to mathematical model
6.1.1 Identifying variables and constraints
Modeling starts by choosing decision variables representing meaningful quantities, such as production amounts, shipped quantities, ingredient amounts, or time allocations. Constraints then encode limits and requirements: resource capacities, demand satisfaction, logical relationships, and any mandatory totals.
6.1.2 Ensuring linearity assumptions
LP requires linear relationships: both objective and constraints must be linear functions of the decision variables. When relationships are inherently nonlinear (e.g., economies of scale, nonlinear costs), they must be approximated or re-expressed using linear surrogates, piecewise-linear constructs, or alternative formulations, depending on modeling goals.
6.1.3 Units, scaling, and bounds
Consistent units prevent distorted coefficient magnitudes. Scaling can improve numerical performance, while variable bounds reflect realistic limits such as nonnegativity, maximum purchase quantities, or capacity caps. Careful bounds also reduce the risk of unbounded or unrealistic solutions.
6.2 Common modeling patterns
6.2.1 Knapsack-style relaxations
Knapsack-inspired structures involve selecting quantities under resource limits to optimize a value measure. In full knapsack problems, variables might be integer; however, LP relaxations allow continuous variables, providing fast lower/upper bounds and guiding subsequent exact methods if integrality is later required.
6.2.2 Blending and assignment formulations
Blending models combine components to achieve target compositions, often with linear constraints on amounts and properties. Assignment-like structures allocate tasks to options subject to capacities or one-to-one rules; LP formulations may represent these allocations directly or use relaxation forms that later motivate rounding or integrality enforcement.
6.2.3 Minimum/maximum flow interpretations
Network flow interpretations represent flows through edges with capacity constraints and node balance equations. While not every LP is literally a flow problem, many logistics and routing models fit the flow structure, enabling specialized modeling intuition and sometimes solver advantages.
6.3 Implementation and verification
6.3.1 Sanity checks and feasibility tests
Before relying on computed results, modelers check that constraints are expressed correctly (signs, directions, units) and that the feasible region is not empty for realistic scenarios. Simple feasibility tests and inspection of constraint tightness help confirm that the formulation matches the intended task.
6.3.2 Interpreting solver output
Solvers report objective value, variable values, and diagnostic information such as feasibility status and iteration counts. Understanding the difference between primal and dual outputs, and recognizing when numerical tolerances might affect “near zero” values, helps interpret whether apparent constraint violations are meaningful.
6.3.3 Validating results against expectations
Validation compares the solution to domain intuition: for example, whether the solution uses resources in plausible proportions, whether costs look reasonable, and whether binding constraints align with the story of the problem. Post-optimality checks, including reduced-cost and sensitivity reasoning, can further verify that the computed plan behaves consistently under small parameter changes.