Linear Programming

Imagine a small workshop that builds tables and chairs. Each table earns more profit than a chair, but it also hogs more wood and more hours at the saw. You have a fixed amount of wood and a fixed number of work hours each week. How many of each should you build to make the most money?

This is a linear program. There is a goal you want to push as high as possible (profit), and that goal grows in a straight line with how much you make. There are limits — wood, hours — and each limit is also a straight line: use too much and you cross it.

Almost every "do the best you can within the rules" question has this shape: cheapest diet that still meets your vitamins, the airline schedule that burns the least fuel, the blend of crude oils that yields the most gasoline. They all boil down to pushing one linear goal as far as it will go inside a region carved out by linear constraints.

Below is the workshop problem drawn as a picture. The shaded polygon is every plan that respects your wood and hours; any point inside is allowed. The dashed line is your profit — all the plans that earn the same amount sit on it.

<p class="hint">{{hint}}</p>
<canvas id="lp" width="360" height="320"></canvas>
<div class="row">
  <label for="slider">{{label_profit_line}}</label>
  <input id="slider" type="range" min="0" max="100" value="30" />
</div>
<div class="status" id="status">{{status_initial}}</div>
<div class="btns">
  <button id="solve" type="button">{{btn_solve}}</button>
  <button id="reset" type="button" class="ghost">{{btn_reset}}</button>
</div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .9rem; color: #444; margin: 0 0 .7rem; line-height: 1.45; }
canvas { background: #fff; border: 1px solid #cdd9e3; border-radius: 8px; display: block; max-width: 100%; }
.row { display: flex; align-items: center; gap: .6rem; margin: .7rem 0 .3rem; }
.row label { font-size: .85rem; font-weight: 600; color: #1d3557; }
input[type=range] { flex: 1; accent-color: #1d3557; }
.status { font-size: 1rem; font-weight: 600; margin: .5rem 0; min-height: 1.4em; }
.status.ok { color: #0a7d33; }
.btns { display: flex; gap: .5rem; flex-wrap: wrap; }
button { font: 600 14px system-ui, sans-serif; padding: .45rem .9rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }

// Code not found

Push the profit line outward with the slider. As long as it still touches the polygon you can earn that much; the best plan is the last point it touches before leaving — and that point is always a corner. Press Solve to jump straight there. Notice the asymmetry: once a corner is proposed, checking that it beats its neighbors is instant, and unlike many puzzles on this site, finding it is fast too.

Here is the surprise that makes linear programming special among optimization problems: it is genuinely easy. It lives in the class P — solvable in time polynomial in the size of the input.

• The geometry helps. The optimum of a linear goal over a polygon (or its higher-dimensional version, a polytope) always sits at a corner. So you never search the whole region — only the corners.
• Simplex (George Dantzig, 1947) walks corner to corner, always uphill, and in practice reaches the answer astonishingly fast. But in the worst case it can visit exponentially many corners — the famous Klee–Minty cube (1972) forces it through all $2^{n}$ of them.
• It's in P. In 1979 Leonid Khachiyan proved linear programming polynomial with the ellipsoid method, and in 1984 Narendra Karmarkar gave a fast interior-point method that cuts through the polygon instead of crawling its edges. Modern solvers use both ideas.
• The integer twist. Demand that the answer be whole numbers — 3 tables, not 3.5 — and the problem becomes integer programming, which is NP-hard. The same rules, one extra word, and easy turns into intractable.

That last jump is the heart of the matter: continuous optimization slides smoothly to a corner, but forcing the answer onto a grid of whole numbers drops you straight into the world of P vs NP.

Linear programming is one of the most quietly profitable inventions in all of computing. Whenever an organization squeezes the most out of limited resources, an LP is usually running underneath:

• Airlines schedule crews and routes to burn the least fuel and pay the least overtime.
• Refineries blend crude oils into fuels to maximize the value of every barrel.
• Supply chains decide what to ship from which warehouse to meet demand at the lowest cost.
• Diet and nutrition find the cheapest food basket that still hits every nutrient target — the original "diet problem" from the 1940s.
• Machine learning uses LP at the core of support vector machines and many robust-fitting methods.

It also serves as a relaxation: hard problems like integer programming or the traveling salesman tour are often attacked by first solving an easy LP, then nudging the fractional answer toward a whole-number one.

Linear programming is the rare optimization problem that is both wildly useful and provably easy. Draw your goal and your limits as straight lines, and the best plan is guaranteed to sit at a corner of the region they enclose — a corner that the ellipsoid and interior-point methods reach in polynomial time.

But the moment you insist the answer come in whole units, the smooth slide to a corner is gone and you fall into the NP-hard world of integer programming. That clean break is one of the sharpest illustrations of P vs NP we have: the same picture, a single extra rule, and the difference between minutes and millennia.