| Part II There had been another place I'd saved the company
from going out of business: Our two representatives
from Board Member General Dynamics (GD) had packed
their bags and were on their way back to Texas,
which would have killed the company, when Roger
Frock gave me a call and I went to the Board Meeting
and explained some revenue projections I'd done with
M. Basch. The GD guys were happy; the GD check was
good; and the company was saved again. But my offer letter promised founder's stock, and so
far I had no stock. My wife was still in her Ph.D.
program at Hopkins. Our home was still in Maryland,
and I was flying jump seat home each few weeks.
Also my computer access, PL/I on VM/CMS, no doubt by
a wide margin the best computing then available for
such work, was good in Maryland but sucked in
Memphis so that for the software I had to be in
Maryland which torqued one guy (not Smith) in
Memphis. Also, Smith was not really happy about it. I wanted a piece of paper, stock or Ph.D. On my
last day Smith said "You know if you stay you are in
line for $500,000 in Federal Express stock.". He
wasn't putting that in writing; before I joined I
was told by an SVP that I'd get the stock in "two
weeks", and that was already too optimistic by over
a year; I didn't know how serious Smith was; I
didn't know if the Board would go along; I wasn't
sure how much software I'd have to write for the
optimization I had in mind or how patient Smith
would be as I wrote the software and tried this and
that in the optimization; and I was not sure how
happy Smith would be about the likely considerable
computer charges I'd run up. But there was money to be saved: I'd written the
first version of the software totally ASAP, fingers
flying over the keyboard. There were some simple
tweaks that could have helped save a lot of money,
likely right away enough to pay for the computing I
needed for the optimization. And in the
optimization work, some early results, e.g., just
the careful cost calculations, could have saved much
more money than I needed for the optimization. And
I believe that there was a fairly easy way to do the
fuel buying problem to get it saving money quickly.
The money to be saved just from my typing in some
software was astounding. Actually, from what I
learned later in graduate school, the optimization
should have been not too difficult and saved a
bundle, enough to make a major difference in the
bottom line of FedEx. But Smith wasn't putting the stock in writing, and
my wife was in Maryland. So, I left and got a Ph.D.
in optimization. > I'm not sure exactly what you don't like about the
class I watched the preview lecture. (1) The emphasis on the knapsack problem is
misleading for practice -- really mostly contrived.
For practical problems that really are knapsack
problems, the technical fact that the problem is in
NP-complete is not very important; among the
NP-complete problems, in practice knapsack problems
are among the easiest to solve; the usual
recommended approach is via dynamic programming.
The claim that knapsack problems encounter
exponential running time is over emphasized to
unrealistic. The professor was over hyping the material in ways
that are misleading. Bummer. This stuff about NP-completeness is too often used in
ways that are totally misleading in practice.
Basically some professors are 'bloviating', trying
to impress people with how difficult their work is. Such hype can be seen as an attempt to intimidate
others, and one cost can be that others get
resentful and just decline to get involved with
optimization. Related is the long, common emphasis
on 'optimal' as if saving the last penny was some
high moral objective worth much more than one penny;
that emphasis was, again, a way to intimidate others
and, thus, cause optimization projects to be
neglected. The OP is falling into those old traps.
Bummer. Such nonsense goes back to the cartoon early in Michael R. Garey and David S. Johnson, 'Computers
and Intractability: A Guide to the Theory of
NP-Completeness', ISBN 0-7167-1045-5, W. H. Freeman,
San Francisco, 1979. where the optimization guy says to the business
manager that he (the optimization guy) can't solve
the manager's problem but neither can a long line of
other optimization experts. Nonsense, 99 44/100%
total, made up, flim-flam, fraud nonsense. Why?
The business manager likely cared essentially only
about saving the first 90% of the cost savings from
an 'optimal' solution, nearly always in practice,
and for the rest was quite willing to f'get about
it; what he wanted was likely quite doable; and
nearly all the difficulty the optimization guy was
talking about was for the parts the business manager
was willing to f'get about. Really, the
optimization guy was not looking to solve the
business manager's problem but looking for a
lifetime job pursuing academic prestige at the
business manager's expense. The OPs emphasis on the
difficulty of his work is coming way too close to
this old mistake. E.g., at a start up in Texas, I mentioned, as in my
first post in this thread, I'd gotten a feasible
solution within 0.025% of optimality for a 0-1
integer linear program with 40,000 constraints and
600,000 variables in 905 seconds on a 90 MHz
computer. Then the group of people I was talking
to, heavily from SMU, flatly refused to believe my
statement; they were convinced that due to
NP-completeness theory I had to be lying. I was
telling the exact truth, and NP-completeness theory
in no way contradicts what I said. NP-completeness
theory is about exact optimality, down to the last
tiny fraction of the last penny for worst case
problems, the worst case that can exist even in
principle, and that context is a very long way from
using optimization to save money in practice. Sure,
it might be super nice and valuable to have a fast,
low degree polynomial algorithm that shows that P =
NP, but lack of such an algorithm does not say that
our optimization problems are too difficult in
practice, especially if all we want to do is save
millions of dollars and are willing to sacrifice the
last 10% of the savings. I remember when I was at FedEx and thinking of going
to Brown for my Ph.D. I visited the campus and ate
lunch with two professors, one who was eager for me
to come and the other just the author of a text I'd
long since read carefully. When asked what I was
doing at FedEx and explained the fleet scheduling,
the text author responded with contempt "the
traveling salesman problem" as if the work was
hopeless. No, not in any very meaningful sense.
The goal was to save money, and that was quite
doable, NP-completeness theory or not. That he
wanted to use some tricky point about
NP-completeness theory as an excuse not to save a
significant fraction of the FedEx costs, millions a
year, was a major factor in my not going to Brown.
We have to wonder how that professor even tried to
get from home to lunch that day since he believed
that to do so he had to solve the traveling salesman
problem. The OP's emphasis on NP-completeness to claim how
difficult were the problems he was solving was
nearly as objectionable. He was being misleading.
Bummer. Again, nearly always (sure, if the problem is SAT,
then an approximate solution may be of no interest)
the goal in practice is to save money; the
difficulty of saving the last penny, always, worst
case, guaranteed, is no reason not to save the
millions that can be saved in nearly all practical
cases for likely quite reasonable effort and
possibly some astounding ROI. Net, the NP-completeness theory is far too often used to
claim that such optimization is "hard", but for
saving a lot of money in practice that's often just
wildly false. Indeed, as I mentioned in my first post in this
thread, we are not afraid to use algorithms that are
worst case exponential because simplex is worst case
exponential. To show just how far from reality
NP-completeness theory is, as I mentioned, on
average in practice simplex is low order polynomial. (2) The claim by the OP that if can solve one
NP-complete problem with a 'good' algorithm, then
can solve them all is, sure, true in principle and
nice to know but not very important in practice and
nothing to emphasize in that introductory video.
Here the OP was hyping his work in a misleading way.
Bummer. (3) The OP's claims that optimization is a big deal
in practice are hype and misleading. Bummer. The problem with optimization playing a big role in
practice was illustrated there at FedEx: Smith had
some huge reasons to have me pursue the
optimization. He didn't support my work nearly well
enough, and the main reason was that he just didn't
have faith that he should make that part of his
company the work of some technical experts doing
work he didn't understand (read that statement
several more times and fill in with what we can
expect from emotions, ego, sense of control, Smith's
pride in the paper he wrote at Yale, possibly some
resentment for academics, his family fortune he'd
invested, his long time associates he'd wanted to
count on, promises he'd made to various people, his
image before the 'suits' on his Board, etc.). Law
and medicine have such professional respect;
optimization does not. |
In the end, it's super important to be the guy who OWNS a business and SELLS the results. E.g., for optimization, maybe develop the software for free, show the results and the savings, and then ask to get paid a fraction of the savings. Let's see, long ago one commercial airline was spending $89 million a month on jet fuel. I can believe $200 million a month now, also for FedEx. From a fast Google, get to
with data for US airlines or 847.5 million gallons costing $2,432.4 million dollars in April, 2013.Save 15% of $200 million a month and get paid 20% of the savings and get paid $6 million a month, from just one customer. And it's an easy sale: Take case A, what they are doing now, and cost it out. Then take case B, from optimization. Then compare costs. Simple. Compelling. Maybe not still compelling now, but would have been for much of the history of FedEx.
But, for my doing an in-house effort, Smith didn't take the work very seriously. Right, in the next year I might have burned off $50,000 in VM/CMS time sharing computer charges. Right. But jet fuel is expensive, too.
> it does appear that Simplex is covered
Yes, of course, the course will have to, but the introductory lecture didn't emphasize that.
In a sense, simplex is dirt simple -- just elementary row operations very much like in Gaussian elimination but, using the 'reduced costs', selected to make money at each iteration in, if you wish, a 'greedy' way. But there's more, e.g., some surprising points about moving along edges of a closed convex set, from an intersection of finitely many closed half spaces, from extreme point to extreme point. For the course, discrete and combinatorial optimization, really should know simplex quite well; it promises to be the core of the course. Also, again, simplex is worst case exponential!
For the career prospects of the course, only a tiny fraction of college courses have good, immediate, direct career contributions. So, I can't be offended that the OP's course does not have really good career contributions. But I am offended that the OP tried to claim that his optimization was so important that there would be good career prospects. Sure, Bixby (of C-PLEX) bought a nice house in Houston, but mostly I'm still looking for the yachts, or even the nice houses, of optimization experts. Heck, even job ads would be reassuring.
I have one of the best Ph.D. degrees in optimization, and it has been essentially useless for my career. The core reason is, the business guys with the projects and budgets don't understand optimization, have no respect for it, and don't want to bet part of their careers on it. There's usually little or no downside for ignoring optimization. For pushing a project in optimization and failing, there's a lot of downside. For being successful, there will likely be resentment, attacks from other managers who feel threatened, etc. and otherwise no great upside. So optimization projects are about as popular as a skunk at a garden party.
One final war story: Long the dean of engineering at MIT was T. Magnanti, an expert in optimization. Once he gave a Goldman Lecture at Hopkins on optimization of the design of large IP networks. From some old Bell Labs data (from some work likely close to the book with the cartoon), optimization should be able to save ballpark 15% of network capital expense; worthwhile money if can get it.
So, at one time there was a start up in Plano, TX attacking this problem. At the time, so was I. So, the TX people flew me down for an interview. They had some venture funding, and it may be that some of the people who met me were the venture partners. The company's main optimization guy from SMU had just bowed out. The CEO was a former IBM guy, and they flew me down partly because of my role at FedEx and also because I'd been at IBM's Watson lab.
So, I arrive. I'm met at the door by the CEO, the IBM guy. Right away he scowls, and I never see him again. Why? Because I didn't know his name (I'd had no communications with him), and my handshake was not impressive enough. He desperately needed some good expertise in optimization, e.g., in a back room had a high end PC with a copy of C-PLEX gathering dust while his people were trying total enumeration, but he wanted nothing to do with me. I'm not that hard to take, not even while tired from a plane trip and driving from the Dallas airport to Plano.
The point was, he was convinced that his IBM white shirt and IBM salesman handshake were what were crucial for his company and that my background in optimization was, well, whatever but likely not really good like a handshake. He had no respect for optimization. Soon he was 'promoted' to just a Board slot.
My background in optimization? Did I mention Goldman? He was the Chair of the committee that approved my Ph.D. research. On the committee was C. ReVelle, world expert in optimization for facility location (mentioned by the OP). Also on the committee was J. Cohon, world expert in multi-objective optimization and long President at CMU. My research was from a suggestion in three words by G. Nemhauser, world expert in optimization. One paper I'd published solved some long outstanding questions in the Kuhn-Tucker conditions in optimization and solved a problem stated in the famous paper by Arrow, Hurwicz, and Uzawa. I went through one of the best Ph.D. programs in optimization on the planet. Still, the CEO in TX wanted nothing to do with me. And, really, after my Ph.D., neither did FedEx.
When I left FedEx, I'd saved the company twice and for more had identified, formulated, done good first-cut progress on, and presented the three optimization problems, fleet scheduling, fuel buying, and vertical flight planning. All I needed was a little consulting money and a good VM/CMS time sharing account from my home in Maryland, but that was not enough to get Smith impressed. So, I lost, and so did Smith and FedEx.
In business, optimization is a Rodney Dangerfield field -- it "don't get no respect". So, if exploit optimization, then do it for your own company or sell just the results based on the savings obtained: Since the 'suits' are convinced that optimization can't save much, when the contract is signed they will believe that they won't have to pay much. When they have to pay $6 million a month, they will be surprised and pleased by how much they are saving but bitter and furious at the $6 million a month they are signed up to pay.
There is a secret in business: To get paid well without too much resentment, jealousy, etc. from others, get paid in ways that others don't really know how much you are making. So, if some big company has to pay you $6 million a month, even if you are saving them $30 million a month, they likely will be torqued; but if can get the $6 million a month from several ad networks from running many millions of ads, then no one will get torqued.