Linear programming (source code)

= Linear programming
{wiki}

= Linear program
{synonym}

<Linear programming> optimizes a <linear function> over finitely many linear equalities and inequalities. A common convention is
$$
\max c^Tx\quad\hbox{subject to }Ax\le b,\quad x\ge0.
$$
The <feasible region> is a <linear polyhedron>, so the problem has convex geometry even when it represents a discrete-looking allocation. A <linear programming relaxation> drops integrality requirements and supplies bounds for an <integer program>.

For a concrete example, maximize $3x+2y$ subject to $x+y\le4$, $x\le2$, $y\le3$, and $x,y\ge0$. The point $(2,2)$ is feasible and has value ten. Multiplying the first inequality by two and adding the second gives
$$
3x+2y\le2\cdot4+2=10.
$$
Thus this point is globally optimal. The multipliers $(2,1,0)$ form a <dual linear program> certificate; the unused third constraint has zero multiplier. This small calculation captures the purpose of <linear programming duality>: a feasible solution gives a value, while a feasible dual combination proves that no better value is possible.<Convex Optimization by Stephen Boyd and Lieven Vandenberghe>[§4.3.1, linear programs; §5.1, Lagrange dual lower bounds]{ref}

A model can instead be infeasible or unbounded. The <simplex method> uses changing bases, while <interior-point methods> approach the optimum through the feasible interior when suitable initialization or embedding is supplied. A chosen numerical algorithm must report which case occurred and respect the input's sign and standard-form conventions.