Part I > Having started working mathematically recently it seems to me that even though I can propose a solution which isn't the best, they are usually better

Part I > Having started working mathematically recently it seems to me that even though I can propose a solution which isn't the best, they are usually better than what is currently available. Is that a common experience as a working mathematician. Sure. For the politics, just report the savings. The stuff about the optimal solution, that is, its, say, moral or ethical value, is lost on business people. With some good common sense, the business people just want to know how much has been saved (or extra earned). If you can also have, say, a lower bound on the possible savings and get close to that, then you have in practice a stopping criterion. Or, what in practice is really difficult about the NP-hard problems is usually saving the very last possible tiny fraction of one penny and proving that did that. Instead, just concentrate on saving, say, the first $5 million a month on, say, the $100 million a month of jet fuel for an airline. For a while in optimization, having the optimal solution was made a moral objective with anything that wasted even 0.0001 pennies regarded as a sin. Religious nonsense. Really sloppy work is not good, but close approximation usually is plenty good. For not the best, that's the other time I kept FedEx from going out of business: The founder, Fred W. Smith, spent the afternoon in his office trying to schedule the fleet, staggered out exhausted, said "We need a computer", and a college friend of mine heard that plea and called me. Sure, digging in, I heard a lot about optimal solutions. But I knew that first just get something that helps, say, so can type in a schedule, have the software check it out for, say, planes being over loaded or having to fly too far, get the arrival times, etc., and print out all the details. So, I typed in 6000 lines of code to do that. Right, great circle distances are from just the law of cosines for spherical triangles! Soon the Board wanted a schedule; biggie Board members doubted that the scheduling could even be done; biggie funding was being held up; the company was at risk. So, I got a call from the same guy who called me to the Board meeting for the revenue projections, Roger Frock (he wrote a book about FedEx), and he and one short, easy evening he and I used my software to develop a schedule for the whole planned system of 90 cities and 33 airplanes. It printed out and looked nice. At the next senior staff meeting, Fred's reaction to the printout was "Amazing document -- solved the most important problem facing Federal Express". Our same two guys from General Dynamics went over the schedule carefully and announced "It's a little tight in a few places but it's flyable". The Board was pleased; the funding was enabled. That was the first time I saved FedEx. So, I got into how to do better scheduling. So, for one period from, say, 5 PM to midnight (again from 1 AM to, say, 8 AM) set up a table with one row for each city to be served, 90 cities, and one column for each candidate airplane tour from Memphis and back. So, may have some thousands of columns. Considering all fine details want to account for, and take expectations for random costs, find for each of the candidate tours the cost (first cut, assume that if a plane goes to a city, then it completely serves that city). Then for the schedule, want to pick no more than 33 columns from the 1000s so that all 90 cities are served and total cost is minimized. So, each column covers some cities, and want to pick columns that cover all 90 cities -- so have a set covering problem. Right, it's in NP-complete. Well, that table is essentially the matrix in a 0-1 integer linear programming least cost optimization problem. There have one unknown variable for each of the columns, and the variable is 1 if use that column and 0 otherwise. If relax the 0-1 constraint, then have a fairly routine linear programming problem but will likely end up with some fractional airplanes allocated. Could use branch and bound to get to a good or optimal 0-1 solution. Should have saved FedEx a huge bundle. Now, with software such as the IBM Optimization Subroutine Library (OSL), C-PLEX (now owned by IBM but from Robert Bixby at Rice in Dallas), etc., that would be a fun and likely fairly easy problem. Alas, for proposing that work as my project, I got too much guff and flack back from too much of the top of FedEx, wasn't getting much thanks for the two times I'd saved the company, was not seeing the promised stock, was away from my home and wife, was in a company close to going belly up, saw a lot of dumb work, so went for my Ph.D.