Basically it solves NP-complete problems that are solvable because of small set size and some clever constant optimizations. There are industries where it's a useful thing for scheduling, for example. Or you may want to solve travelling salesman when planning a trip.

Some real-world examples with a little more flavour:

* designing utility networks (e.g. energy / telecommunications) to be cheap / robust

* routing vehicles / ships / parcels to serve all customers cheaply

* dispatching and arranging emergency services vehicles (e.g. ambulances) to best cover anticipated future demand

* managing inventory levels in blood banks. it goes off after a while! there are different types, some are substitutable. which types are better to keep in stock?

* figuring out the most profitable way to chop animals into different cuts of meat

It's for operations research stuff (like logistics, scheduling etc.), not software optimization.

Lots of crazy image processing and computational photography techniques use linear programming and variants on all of these graph algorithms.

Numerical optimization of discrete/combinatorial problems.