Linear optimization, also called linear programming, is a mathematical method for finding the best possible outcome (like maximum profit or minimum cost) when you’re working with limited resources. It works by expressing your goal and your limitations as simple mathematical relationships where every variable is multiplied by a constant and added together, with no exponents, no curves, and no variables multiplied by each other. It’s one of the most widely used optimization techniques in business, engineering, and logistics.
The Three Building Blocks
Every linear optimization problem has three components: decision variables, an objective function, and constraints. Decision variables are the things you’re trying to determine. If you’re a factory manager deciding how many units of two different products to manufacture, those quantities are your decision variables.
The objective function is what you’re trying to maximize or minimize. It’s a formula that adds up the contribution of each decision variable. For the factory example, it might calculate total profit by multiplying each product’s quantity by its profit margin and summing the results. The key word here is “linear”: every variable is scaled by a fixed number and added together, nothing more complex.
Constraints are the real-world limits you have to respect. You only have so many machine hours, so much raw material, so many workers. Each constraint is also a linear equation or inequality. A solution is considered “feasible” when it satisfies every constraint simultaneously. The optimal solution is the feasible solution that gives you the best value of the objective function.
Four Assumptions That Must Hold
Linear optimization relies on four assumptions about your problem. If any of them breaks down significantly, you may need a different technique.
- Proportionality: Each variable’s contribution to the objective and constraints scales in direct proportion to its value. Doubling production doubles both the profit and the resource consumption for that product.
- Additivity: Each variable contributes independently. The effect of one decision variable doesn’t change depending on the value of another.
- Divisibility: Variables can take fractional values. You can produce 3.7 units of something. When only whole numbers make sense (you can’t hire half a truck), you need a related technique called integer programming.
- Certainty: All the numbers in your model, like costs, capacities, and demands, are known and fixed. There’s no randomness built into a standard linear program.
How Solvers Find the Answer
Two families of algorithms dominate the field. The simplex method, created by George Dantzig in the mid-20th century, is often described as one of the most important algorithms ever developed. It works by moving along the edges of the feasible region, a geometric shape defined by your constraints, jumping from corner to corner until it finds the one with the best objective value. In theory, the simplex method can take an exponential number of steps in the worst case. In practice, it’s remarkably fast on real problems.
Interior point methods take a fundamentally different approach. Instead of walking along the boundary, they cut through the interior of the feasible region, converging toward the optimal point. These methods have polynomial-time guarantees, meaning their worst-case running time grows more predictably with problem size. For very large problems with thousands or millions of variables, interior point methods can outperform the simplex method, though neither approach is universally faster than the other.
What Shadow Prices Tell You
One of the most practical outputs of a linear optimization model isn’t just the optimal solution itself but the information you get about your constraints. A shadow price tells you how much your objective function would improve if you could relax a particular constraint by one unit. If your factory’s machine-hours constraint has a shadow price of $0.80, that means one additional machine-hour would increase your optimal profit by 80 cents.
This is powerful for decision-making. It tells you exactly which constraints are bottlenecks and how much it’s worth paying to loosen them. A constraint that isn’t fully used up in the optimal solution (a “non-binding” constraint) always has a shadow price of zero, because you already have more of that resource than you need. Shadow prices are only valid within a specific range around the current constraint value, so they’re useful for small adjustments, not massive overhauls.
Where Linear Optimization Gets Used
Supply chain and logistics is the classic application. Companies use linear programming to decide how to route shipments, allocate inventory across warehouses, and schedule production across multiple facilities. Many organizations build entire decision support systems around linear programming models, sometimes combined with integer and nonlinear programming for more complex situations. Real industrial problems in sectors like natural gas distribution and metals processing rely on these models daily.
Airlines use it to assign crews to flights. Energy companies use it to determine the cheapest mix of power generation sources that meets demand. Financial firms use it to construct portfolios that minimize risk for a given return target. Agriculture, telecommunications, manufacturing, and healthcare all have well-established linear programming applications. Anywhere you’re allocating limited resources to competing activities, linear optimization is a natural fit.
Major commercial solvers like CPLEX, Gurobi, and XPRESS can handle problems with millions of variables. Open-source alternatives like HiGHS have also become competitive. The availability of fast solvers is a big reason linear optimization remains so widely adopted: formulating the model is often harder than solving it.
How It Differs From Nonlinear Optimization
The distinction is straightforward. If your objective function or any constraint involves a variable raised to a power, a logarithm, a product of two variables, or any curved relationship, the problem is nonlinear. Nonlinear optimization can represent real-world systems more accurately, since many physical and economic relationships aren’t perfectly linear. But that accuracy comes at a cost: nonlinear solvers are slower and less reliable, and they can get stuck at solutions that look optimal locally but aren’t the best overall.
Linear models, by contrast, have a powerful mathematical property: any local optimum is also the global optimum. There’s no risk of finding a “pretty good” answer that hides a better one elsewhere. This reliability, combined with the speed of modern solvers, is why practitioners often prefer to simplify a problem into a linear form whenever the approximation is reasonable. A comparative study on ship machinery optimization found that the linear approach offered faster and more reliable solutions, while the nonlinear approach captured system behavior more accurately but required significantly longer computation times.
Duality: Every Problem Has a Mirror
One of the deeper ideas in linear optimization is that every problem (the “primal”) has a corresponding mirror problem (the “dual”). If the primal minimizes cost subject to meeting certain requirements, the dual maximizes the value of those requirements subject to not exceeding the costs. At the optimal solution, both problems yield the same objective value.
This isn’t just a mathematical curiosity. Duality provides a built-in way to verify solutions and gives economic interpretations of constraints. The dual variables correspond directly to shadow prices. And many practical algorithms, including some of the most efficient interior point methods, exploit the relationship between primal and dual problems to find solutions faster. Understanding duality also helps you recognize when a problem has no feasible solution or when the objective can be improved without bound.