[FredPret]

Knapsack problems, some simple scheduling problems, even the travelling salesman problem.

Many problems in business and manufacturing fit this bill. Optimal product mix, optimal routing, choosing the best spot for a warehouse, scheduling employees, constructing an investment protfolio, coming up with a diet that fits certain criteria, etc.

I even remember a practice problem from uni where we had to optimally distribute songs on two sides of a tape album (it was an old professor), satisfying constraints such as “each side should have a ballad” and “each side has at most x minutes of running time”.

You can do this with regular coding too, but if you can easily construct a certain kind of mathematical model of your problem, you can easily solve it with linear programming.