Linear Programming
Overview
Linear programming (LP) is a mathematical optimization technique for maximizing or minimizing a linear objective function subject to linear equality and inequality constraints. First formalized by George Dantzig in 1947, LP has become one of the most widely applied mathematical methods in operations research, economics, engineering, and management science. Its power lies in a remarkable property: the feasible region defined by linear constraints forms a convex polyhedron, and the optimal solution always occurs at a vertex of this polyhedron. This geometric insight enables highly efficient algorithms that solve problems with thousands or even millions of variables.
Mathematical Foundation: The standard form of a linear program is:
\begin{aligned} \text{minimize} \quad & c^T x \\ \text{subject to} \quad & Ax \leq b \\ & x \geq 0 \end{aligned}
where x \in \mathbb{R}^n is the vector of decision variables, c \in \mathbb{R}^n defines the objective coefficients, A \in \mathbb{R}^{m \times n} is the constraint matrix, and b \in \mathbb{R}^m specifies the constraint bounds. Any LP can be transformed to this standard form through algebraic manipulation.
Practical Applications: Linear programming is the foundation for solving a diverse range of real-world optimization problems. Supply chain optimization uses LP to minimize transportation costs while satisfying demand constraints. Portfolio optimization applies LP to balance investment returns against risk. Production planning determines optimal product mix to maximize profit subject to resource limits. Network flow problems, scheduling problems, and resource allocation in manufacturing all reduce to linear programs. The remarkable breadth of applications stems from the fact that many practical constraints and objectives are naturally linear or can be well-approximated as linear.
Implementation: These tools leverage powerful optimization libraries including SciPy, which provides the linprog solver based on interior-point and simplex algorithms, and CasADi, a specialized tool for automatic differentiation and optimization that handles more complex nonlinear problems. Both libraries implement state-of-the-art algorithms refined over decades of research.
Solution Approaches: The simplex algorithm, developed by Dantzig, moves from vertex to vertex along the edges of the feasible polytope, monotonically improving the objective. While worst-case complexity is exponential, the simplex method works efficiently in practice on real-world problems. More modern interior-point methods traverse through the interior of the feasible region and scale better to very large problems. The choice between methods depends on problem structure and size—simplex excels for sparse problems with special structure, while interior-point dominates for dense, large-scale problems.
Linear vs. Quadratic Programming: The LINEAR_PROG tool handles the standard linear case where both the objective and all constraints are linear. When the objective function becomes quadratic (like minimizing \frac{1}{2}x^T Q x + c^T x), the problem becomes quadratic programming (QP). The CA_QUAD_PROG tool addresses quadratic objectives using CasADi’s specialized solver. Quadratic objectives naturally arise in least-squares problems, risk-sensitive optimization, and control applications.
Integer Constraints: Real-world optimization often requires discrete decisions—a factory either runs or it doesn’t, an item is selected or it isn’t. The mixed-integer linear program (MILP) extends LP by allowing some variables to take only integer values. This dramatically increases computational complexity (NP-hard in general), but the MILP tool provides access to advanced branch-and-cut algorithms that solve moderately-sized integer programs efficiently. Use MILP when your problem fundamentally involves binary choices or discrete quantities that cannot be relaxed to continuous variables.
Figure 1 illustrates the geometric intuition behind linear programming and shows how the solution landscape differs between linear, quadratic, and integer programs.
Tools
| Tool | Description |
|---|---|
| CA_QUAD_PROG | Solve a quadratic programming problem using CasADi’s qpsol solver. |
| LINEAR_PROG | Solve a linear programming problem using SciPy’s linprog function. |
| MILP | Solve a mixed-integer linear program using scipy.optimize.milp. |