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.