mathematics//optimization//linear programming
Linear programming is optimization with a linear cost and linear equality and inequality constraints over continuous variables, solved in polynomial time by interior-point methods and, in practice just as well, by the simplex method; it is used to plan blends and production, route flows through networks, dispatch generators at least cost, and as the relaxation inside every integer programming solver.
Linear programming is optimization with a linear cost and linear equality and inequality constraints over continuous variables, solved in polynomial time by interior-point methods and, in practice just as well, by the simplex method; it is used to plan blends and production, route flows through networks, dispatch generators at least cost, and as the relaxation inside every integer programming solver.
minx c⊤xsubject toAx≤b,x≥0\min_{x}\; c^{\top}x\quad\text{subject to}\quad Ax\le b,\qquad x\ge0xminc⊤xsubject toAx≤b,x≥0
The constraints carve out a polytope, a region with flat faces, and a linear cost always reaches its optimum at a vertex of it (or along a whole edge or face, when the cost runs parallel to one). The simplex method walks from vertex to vertex, each step lowering the cost; interior-point methods cut through the middle. Take a refinery blending two crudes to meet a demand for fuel under a sulfur specification: two variables, a handful of constraints, and the cheapest blend sits on the sulfur limit, because the cheap crude is the sour one. The profit leans on a constraint, the situation the book also describes for MPC in process plants.
An LP solves fast and big, millions of variables on modern solvers, and reports exactly whether it is feasible, unbounded or optimal. Its continuity is what makes it easy; requiring some variables to be integers turns it into an integer linear program, and dropping that requirement again (the LP relaxation) is how integer solvers get their bounds.
Each constraint of the optimum carries a price, the change in cost per unit of relaxation (duality): in the refinery, what one more part per million of allowed sulfur is worth per tonne. That number often matters more to the plant than the blend itself.
It reaches across the book. The value of a zero-sum game and the optimal mixed strategy come out of one LP (minimax theorem); a fit minimizing absolute errors instead of squares is an LP and is robust to outliers; the economic dispatch of a grid, in its linearized form, is one.
Numerics still matter. Badly scaled rows (megawatts beside kilowatts, costs in euros beside cents) slow solvers and trigger tolerance failures, so variables are scaled before solving (variable scaling). In Python, scipy.optimize.linprog calls the HiGHS solver; cvxpy states the problem in mathematical form.