Linear programming (LP)

Linear programming is a mathematical optimization technique for problems where the objective, the quantity being maximized or minimized, and every constraint can be written as a linear combination of decision variables: no squared terms, no products of variables, no thresholds that jump discontinuously. A classic example is deciding how many units of each product to make to maximize profit, given limited machine hours and raw materials.

Because the problem is linear, it can be solved efficiently and exactly, guaranteeing an optimal answer, using well-established algorithms such as the simplex method or interior-point methods, even for problems with thousands of variables. This differs from general optimization modeling, which also covers nonlinear and integer problems that are harder, or in some cases impossible, to solve exactly at scale; when decisions must be whole numbers, such as staff counts, the related technique of integer or mixed-integer programming is used instead.

Linear programming matters in operations and supply chain work, blending, scheduling, transportation, and route optimization, anywhere a resource-allocation problem is genuinely linear or can be reasonably approximated as one. The main pitfall is forcing a fundamentally nonlinear or discrete problem into a linear form for the sake of solvability, which can produce a mathematically optimal but practically unrealistic recommendation.