Optimization matters in AI because most automated decisions, from fitting a model to scheduling a shift, come down to choosing values that make a score as good as possible within limits. How such a problem is solved depends on its shape. For a linear program, a solver can return the best answer together with a proof that nothing better exists, while for whole-number choices and neural networks it usually returns a good answer without that proof.
Key takeaways
- A linear program has a straight-line objective and straight-line limits; Dantzig's simplex method, developed in 1947, and later interior-point methods solve it reliably.
- An answer can be proven best by finding a bound that matches it, as the worked kitchen example below shows with a total of 2,600 servings.
- Requiring whole numbers can break the guarantee: in the second example the relaxed answer scores 21, rounding gives 19, and the true best whole-number answer is 20.
- Richard Karp's 1972 paper listed 0-1 integer programming among 21 problems now known as NP-complete, so no fast general method is known for it.
- When a tool reports a result, the useful question is whether it was proven best or only found good.
Where optimization shows up in AI work
Training a model chooses numerical parameters that minimize an error score. A planner chooses an order of actions that minimizes time or cost. A resource allocator chooses how much of each scarce input goes to each use. In the standard form used by Stephen Boyd and Lieven Vandenberghe in Convex Optimization, all three are written as minimizing an objective over variables subject to constraints. Section 1.2 of that book notes that linear programs have no simple formula for their solution but can be solved by methods including Dantzig's simplex method and interior-point methods, and that problems with hundreds of variables and thousands of constraints can be solved in seconds on a small desktop computer. The authors call solving most linear programs a mature technology.
A linear program with a proof of its answer
An illustrative case: a community kitchen makes trays of soup (x) and stew (y). A soup tray serves 40 people and a stew tray serves 30. Oven time is limited to 100 units, and soup uses two units per tray while stew uses one. Staff time is limited to 80 units, and each tray uses one. The stove allows at most 40 trays of soup. The goal is to maximize servings. The numbers are invented for illustration.
For a linear program, the best answer lies at a corner of the region the constraints allow, so checking the corners is enough in a problem this small.
| Corner (soup, stew) | Servings |
|---|---|
| (0, 0) | 0 |
| (40, 0) | 1,600 |
| (40, 20) | 2,200 |
| (20, 60) | 2,600 |
| (0, 80) | 2,400 |
The best corner is 20 trays of soup and 60 of stew, serving 2,600. A proof does not require checking every corner. Multiply the oven limit by 10 and the staff limit by 20 and add them: 10(2x + y) + 20(x + y) equals 40x + 30y, exactly the servings formula. The two limits add up to 10 times 100 plus 20 times 80, which is 2,600. So no plan allowed by those two limits can serve more than 2,600, and the plan above reaches it. The multipliers 10 and 20 come from matching the coefficients: 2a + b = 40 and a + b = 30. This is the idea behind duality, which Chapter 5 of Boyd and Vandenberghe covers,.
When choices must be whole numbers
Many AI problems require whole numbers: a truck either takes a stop or does not. A second illustrative case shows the cost. Maximize 5x + 4y with the limits 6x + 4y at most 24 and x + 2y at most 6, where x and y must be whole numbers. Without that requirement, the best answer is x = 3 and y = 1.5, scoring 21, and multipliers of 0.75 and 0.5 on the two limits prove no plan can exceed 21. Rounding y down gives (3, 1), which scores 19. Checking the whole-number options finds (4, 0) scoring 20, which beats the rounded plan.
The relaxed score of 21 is still useful, because it caps what any whole-number plan can reach. Solvers for such problems commonly pair that cap with systematic search, and when they stop early they can report the gap between the best plan found and the cap. The difficulty is real: Karp's 1972 paper, "Reducibility Among Combinatorial Problems," placed 0-1 integer programming among its 21 NP-complete problems. In 1979 Leonid Khachiyan showed that the plain, non-integer version is solvable in polynomial time, which marks a sharp line between the two.
Matching the method to the problem
| Problem shape | Typical method | What the result can promise |
|---|---|---|
| Linear objective and limits, continuous variables | Simplex or interior-point solver | Proven best, within numerical tolerance |
| Same, with whole-number variables | Relaxation plus search, or heuristics | A plan and a gap to the cap, if the search finishes or is stopped with a bound |
| Neural network training | Gradient-based methods on a non-convex loss | A good fit, with no guarantee of the lowest possible error |
| Very large routing or scheduling | Heuristics and local search | A good plan, whose distance from best may be unknown |
Reading an optimization claim
A tool that reports "optimal" should say what it optimized and what was left out. The 2,600 above is optimal only for the two limits and the stove cap listed; a kitchen with a volunteer shortage would need another constraint. When a result is labeled feasible or good, no proof comes with it. When the objective is a stand-in, such as clicks for satisfaction, the solver still answers the question it was given. Optimization is a powerful tool for being precise about trade-offs, and it is only as good as the objective and the limits its authors wrote down.
FAQ
Is optimization the same as machine learning?
No. Training a model uses optimization to fit parameters, but optimization also schedules, routes, and allocates without any learning involved. Linear programming predates modern machine learning; Dantzig developed the simplex method in 1947.
What does it mean for a solution to be optimal?
It means no allowed solution scores better on the stated objective. In a linear program, a matching bound like the 2,600 above proves it. Without such a bound, a result is only the best one found.
Why can solvers not always prove their answer is best?
For whole-number problems the general task is NP-complete, so no fast method is known, and proofs can take very long. Solvers then report the best plan found and how far it may be from the bound.
Who won a Nobel Prize for this kind of work?
The 1975 economics prize went to Leonid Kantorovich and Tjalling Koopmans "for their contributions to the theory of optimum allocation of resources." Dantzig's simplex method is the best-known algorithm from the same period.
Related reading
- What an optimization problem is
- The traveling salesman problem and routing
- Writing a problem down for a solver
- Timefold, an open-source planning solver
More in AI Basics.
Last verified: October 2026
Sources
- Boyd S, Vandenberghe L, Convex Optimization, Cambridge University Press, Sections 1.1 and 1.2 and Chapter 5
- Karp RM, Reducibility among Combinatorial Problems, in Complexity of Computer Computations, Plenum Press, 1972
- George Dantzig biography, MacTutor History of Mathematics, University of St Andrews
- The Sveriges Riksbank Prize in Economic Sciences in Memory of Alfred Nobel 1975
- Oracles, Ellipsoid method and their uses in convex optimization, lecture notes, Princeton University COS 521, 2015