Linear Programming

Linear programming (LP) answers a precise question: among all vectors satisfying linear equalities and inequalities, which minimizes or maximizes a linear score? The word programming here means planning or allocation, not source code. LP is valuable because its restricted form gives unusually strong structure: local and global optima coincide, infeasibility and optimality have checkable certificates, and very large sparse models can be solved reliably.

The hard part in practice is usually not selecting a solver. It is constructing a model whose variables, units, constraints, objective, and tolerances mean what the real decision requires.

The model and its three possible outcomes #

A common standard form is

$$\begin{aligned} \text{minimize}\quad & c^T x\\ \text{subject to}\quad & Ax=b,\\ & x\ge 0, \end{aligned}$$

where $x\in\mathbb R^n$ contains the decision variables, $c\in\mathbb R^n$ contains per-unit objective coefficients, $A\in\mathbb R^{m\times n}$ contains constraint coefficients, and $b\in\mathbb R^m$ contains right-hand sides. Other forms with inequalities, upper bounds, free variables, or maximization are equivalent after mechanical transformations, but the transformation must preserve units and meaning.

An LP does not always have an optimum. A solver must distinguish three mathematical outcomes:

Geometry explains why LP is tractable #

Each linear inequality describes a half-space. Their intersection is a convex polyhedron: for any feasible $x$ and $y$, every point $(1-\lambda)x+\lambda y$ with $0\le\lambda\le1$ is also feasible. The objective's level sets $c^Tx=\alpha$ are parallel hyperplanes. Optimizing moves such a hyperplane in the improving direction until it last touches the feasible set.

If a finite optimum exists and the feasible polyhedron has extreme points, at least one optimum occurs at an extreme point. An entire edge or face may also be optimal. This is why simplex methods can search basic feasible solutions rather than every point, but it does not mean every optimum is unique.

For two decision variables the geometry can be drawn. Consider a workshop choosing quantities $x$ and $y$:

$$\begin{aligned} \text{maximize}\quad & 3x+2y\\ \text{subject to}\quad & x+y\le4,\\ & 2x+y\le5,\\ & x,y\ge0. \end{aligned}$$

The boundary intersections give candidate vertices $(0,0)$, $(0,4)$, $(1,3)$, and $(2.5,0)$. Evaluating the objective gives $0$, $8$, $9$, and $7.5$, so $(1,3)$ is optimal with value $9$. The calculation is small, but it exposes the general logic: constraints define a polyhedron, and the linear objective selects a supporting face.

Slack, basis, and the simplex mechanism #

An inequality $a_i^Tx\le b_i$ can gain a nonnegative slack variable $s_i$:

$$a_i^Tx+s_i=b_i,\qquad s_i\ge0.$$

The slack measures unused capacity in the constraint's own units. After conversion to equalities, a basis selects $m$ linearly independent columns of the constraint matrix. Setting nonbasic variables to zero and solving for the basic variables produces a basic solution; it is feasible when every required bound is satisfied.

The primal simplex method repeatedly:

1. starts from a basic feasible solution;
2. uses reduced costs to identify a nonbasic variable that can improve the objective;
3. uses a ratio test to determine which basic variable reaches a bound first;
4. pivots—exchanges one entering and one leaving column in the basis;
5. stops when reduced costs certify that no adjacent feasible direction improves the objective.

The tableau taught in textbooks is an explanatory representation of these updates. Production revised simplex implementations normally factor and update the basis matrix rather than materializing one giant tableau. Sparse linear algebra, presolve, scaling, crash strategies, basis repair, and anti-degeneracy rules are part of the actual algorithm.

Degeneracy is not a corner case #

A basic feasible solution is degenerate when a basic variable is at a bound, often zero. Then a pivot may change the basis without changing the represented point or objective. Repeated zero-progress pivots can cause stalling, and careless pivot rules can cycle. Perturbation, lexicographic ideas, steepest-edge pricing, and practical anti-degeneracy strategies manage this without changing the model's intended feasible set.

Multiple optima are different: they occur when the objective is parallel to an optimal edge or face. Degeneracy concerns representation; multiplicity concerns the set of optimal decisions. Either can occur without the other.

Interior-point methods take another path #

Simplex moves between boundary bases. Interior-point methods instead follow points in the interior of the feasible region while driving a barrier parameter toward zero. Karmarkar's 1984 projective method established an influential polynomial-time route; modern primal-dual interior-point solvers use a different but related barrier framework and solve large sparse linear systems at each iteration.

Neither family dominates every model:

Current solvers commonly provide both. HiGHS, for example, exposes dual revised simplex and an interior-point LP solver; algorithm choice should follow the model, reuse pattern, and certificate needs rather than textbook allegiance.

Duality turns an answer into a certificate #

For the standard-form minimization problem, one dual form is

$$\begin{aligned} \text{maximize}\quad & b^Ty\\ \text{subject to}\quad & A^Ty\le c. \end{aligned}$$

For any primal-feasible $x$ and dual-feasible $y$,

$$b^Ty=(Ax)^Ty=x^TA^Ty\le x^Tc=c^Tx.$$

This is weak duality: every dual feasible value is a lower bound on every primal feasible value. If a feasible pair has equal objectives, each proves the other optimal. Under the ordinary finite LP conditions, strong duality says an optimum has such a matching certificate.

Dual variables also act as local sensitivity values. If a right-hand side changes slightly while the active basis remains valid, the corresponding dual variable gives the objective's marginal response. This interpretation has a validity range: after a basis or active set changes, the marginal value can change abruptly.

Complementary slackness connects the two sides. In one common sign convention,

$$x_j\bigl(c_j-(A^Ty)_j\bigr)=0.$$

A positive primal variable can coexist only with zero dual slack. A constraint with nonzero dual price must be tight on the primal side. This is an economical way to diagnose why a resource matters at the optimum.

Infeasibility also needs evidence #

When constraints conflict, removing constraints until the model solves may locate a symptom but can destroy the intended problem. Solvers can instead return an infeasibility certificate or an irreducible infeasible subsystem (IIS): a subset that is infeasible but becomes feasible if any member is removed. It need not be the only IIS or the smallest one.

Typical modeling failures include:

• mixing hours and minutes or kilograms and tonnes;
• reversing a demand or capacity inequality;
• forgetting that a variable is nonnegative;
• applying one aggregate limit and also incompatible per-period minima;
• binding two datasets through mismatched identifiers;
• using a tight “big M” constraint with an unjustified value.

The dual alternative behind Farkas-type certificates is the deep reason infeasibility can be proved by a finite vector rather than reported as an unexplained search failure.

Continuous LP is not integer programming #

An LP permits real-valued decisions. If $x=2.4$ means 2.4 tonnes, that may be correct; if it means 2.4 servers or 2.4 people, it is not. Declaring integrality produces a mixed-integer linear program (MILP), whose feasible set is no longer convex and whose worst-case computational character is fundamentally harder.

A MILP solver commonly uses the LP relaxation inside branch and bound. The relaxation supplies optimistic bounds; branching restores discrete choices; cuts tighten the relaxation. Rounding an LP solution afterward is not a general solution: it can violate constraints or be arbitrarily far from the integer optimum.

Numerical correctness is a tolerance contract #

Solvers use floating-point arithmetic. “Feasible” normally means that scaled residuals and bound violations lie within configured tolerances, not that symbolic equalities hold bit-for-bit. Poor scaling—coefficients spanning many orders of magnitude—can make a mathematically simple model numerically fragile.

After solving, inspect at least:

1. the termination status, not only the objective value;
2. primal constraint and bound residuals in original units;
3. dual feasibility and the primal-dual objective gap;
4. complementarity or reduced-cost conditions relevant to the chosen form;
5. sensitivity to plausible data changes and tolerances;
6. whether the returned decision remains valid in the real domain.

A modeling workflow that survives review #

1. Name the decisions. State what each variable represents, including index sets and units.
2. Write constraints in words first. Preserve the operational reason for every row.
3. Check dimensional consistency. Terms added in one equation need compatible units.
4. Construct tiny hand-solvable cases. Include an optimal, infeasible, unbounded, and multiple-optimum case.
5. Solve and inspect certificates. Residuals, dual values, reduced costs, and IIS data are part of the result.
6. Perturb inputs. A plan that changes violently under harmless measurement noise is operationally fragile even when mathematically optimal.
7. Validate downstream use. Confirm rounding, execution constraints, and data freshness outside the solver.

The lasting mental model is simple: an LP solver searches a convex polyhedron, but a trustworthy optimization system must also prove what the polyhedron means.