I read your whole post but I'm not sure exactly what you don't like about the class other than you seem to think learning Discrete Optimization in general is a waste of time because theres more lucrative problems much easier to solve.
Care to briefly elaborate on what you dislike about this course specifically (it does appear that Simplex is covered)?
I wrote quickly and was not very clear for people
without good backgrounds in optimization.
> You really wrote the algorithm for FedEx? Thats
In the sense of business, it actually was "amazing":
Likely it saved the company from going out of
business. Too many Members of the Board of
Directors were concerned that there could be no
suitable schedule. So, one evening Roger Frock and
I used my software to develop a schedule for all
planned 33 airplanes and all planned 90 US cities.
Printed out, FedEx founder, COB, CEO F. Smith said
at the next senior staff meeting "Amazing document.
Solved the most important problem facing Federal
Two guys representing Board Member General Dynamics
went over the schedule and announced "It's a little
tight in a few places, but it's flyable.". Then the
Board was happy. As I recall, $55 million in
funding was enabled, not all equity.
So, the software was "amazing" just as business.
But as applied math, the software was junk! Work
for the real, pressing, short term business problem?
Yes. Really optimization? No!
But I did continue and saw that what I should do was
(1) generate some thousands of 'feasible' trips from
Memphis and back and for each carefully add up the
direct costs, (2) set up a 0-1 integer linear
programming problem with one row for each of the 90
cities and one column for each of the thousands of
feasible trips. Then each row says to serve some
one city. Each variable, 1 or 0, one for each
column, says to use that trip or not. Right: It's
0-1 integer linear programming set covering, yes, in
So, that's a linear program with only 90 rows. Just
as a linear program, that's promising, likely easy.
Make money? My only competition was a guy with a
map of the US on a sheet of 8 1/2 x 11" paper. He
didn't have a reasonable way even to add the costs
of a candidate schedule or print it out. So, yes,
my work should have saved a bundle.
If nothing else, just solve the LP without the 0-1
constraints (with only 90 rows, that should be
easy), look at the results, and see if have an easy,
not very expensive way to patch up the fractions to
0-1 by hand. Else do a little branch and bound. If
attacking the whole problem for the whole country is
too difficult, then attack it for parts of the
country separately; e.g., what do in the East has
next to nothing to do with what do in the West; the
goal is not to announce that have the 'optimal'
solution down to the last fraction of the last
penny; instead, the goal is to save money. Don't be
embarrassed about not guaranteeing to save the last
$1000 or the last $1,000,000 a month; instead be
just horrified about not saving the first $10
million a month.
Also do a little duality theory to get a bound on
how much more money might be saved. When have saved
the first $10 million and have no more than another
$1,000 to save, take the best feasible solution so
far and quit.
About then I'd gotten on an airplane and run off to
chat about optimization with G. Nemhauser, then
still at Cornell, J. Elzinga, then still at Hopkins,
and J. Pierce, then in Cincinnati, got a stack of
books and papers, etc.
There was also another problem: Our fuel prices and
availabilities varied widely by airport. So, a
question was, how much fuel to buy at each stop?
So, buy extra fuel where it is cheap and available.
This is called 'fuel tankering'. But, yes, will
burn off some of the extra fuel carrying it.
How much extra fuel is burned off is fairly
sensitive to the vertical flight plan used; so also
need to select vertical flight plan in a coordinated
way. The problem is also complicated by the fact
that package pickup loads are not known until the
plane arrives for the pickup, and those loads will
affect the fuel burned for each candidate vertical
flight plan. Then those loads will also affect how
much fuel can be carried. Also relevant is that the
fuel burned and flight time for a vertical flight
plan and a load are affected by essentially random
winds, air traffic control, and flying around summer
thunder storms. Also really get charged not just
for fuel but also time on the engines. So, it was
Now, try to find a way in practice to advise the
pilot on what to do? So, right, it's another
optimization problem -- partly discrete, nonlinear,
sequential, stochastic. So, right, stochastic
dynamic programming. Doable? Actually, yes, quite
doable. On a computer today, could solve the
problem for, say, five stops, with weight
discretized at 100 pounds in about the time it takes
to get a finger off the Enter key or the mouse button.
Also for the vertical flight plans, I went to MIT
and chatted with M. Athans about deterministic
optimal control theory.
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.
> I'm not sure exactly what you don't like about the
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
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.
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
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.
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
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.
(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
2013 April 847.5 2,432.4
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
> 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
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
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
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.
I agree with you that many managers haven't a clue what to do with an OR graduate. So it does depend on how you position yourself. One reason for taking the course is to be able to promote your skills passionately (try making a video of your skills in every day parlance like the introductory video to this lecture) using current terminology - which as Prof Van Hentenryck says are in demand at INFORMS conferences (go to the analytics conference - rather than the main conference which is more academic).
I agree with you that many execs haven't a clue what optimization can do - or care - in fact most managers satisfice. That's why it's important to find the right boss who does value your accomplishments. It's also important to update how you state your value to others - which is one reason I'm doing the course.
I hope you stick with it - and I'd be interested to know what you think at the end of it.
Is the point of your argument that the leaderboard ranking forces people to try for an optimal solution, when in a business situation a solution at 99% of the value might be good enough?
> it's also important to update how you state your value to others
On this, I outlined my suggestion: Own a little
company and sell results based on how much money
they save the customer. Make the sale about
saving the customers money in ways that even
an auditor can confirm are correct.
INFORMS is clearly an echo chamber,
people in optimization looking for
work and talking to themselves.
Broadly for optimization in business, there is
a very serious problem: Optimization is not
a 'profession' like law, medicine, or major
parts of engineering. So, there is no licensing,
certification such as the CPA,
peer-review of practice, legal liability,
etc. So, as I said, the field "don't
get no respect".
Also missing is a point the legal profession
has: Any working lawyer must report only to
a lawyer; the interface between the optimization
guy and the business guy is nearly impossible.
> Is the point of your argument ...
I tried to make several points. One of the
points was about 'optimal'. The mathematical
definition is fine, but long that definition
was taken as suggesting that what we should
do in practice is look for such solutions,
then strain to find them, etc. That turned
out to be a grand mistake.
Why? Because maybe there is, compared with
what the customers is doing now, $10 million
to be saved with an optimal solution. But
too commonly saving all $10 million is too
difficult for the algorithms and computing.
So, straining to save all the $10 million
converts an important business problem into
a much more difficult mathematical problem.
It also turns out that commonly it's fairly
easy to save, say, $9 million. The difficulty is
saving the last of the money, and the
most difficult money to save is the last,
say, the last 10 cents.
'Optimal' was taken as a moral objective,
as I said, as if saving the last 10 cents
was worth much more than 10 cents.
Struggling over 'optimal' taken literally
and, thus, making real problems much more
difficult than necessary, was several torpedoes
below the waterline of the ship of optimization.
Part of this mistake was the simplistic and excessive
emphasis on NP-completeness -- for real
problems the whole P versus NP question is
next to irrelevant. One way to see this is
the simplex algorithm -- it's the core of
optimization and astoundingly fast in practice
but worst case exponential. There is a
polynomial algorithm for linear programming,
but it's way too slow in practice. In
practice, that an algorithm is worst case
exponential is commonly just irrelevant.
I had to conclude that for business, optimization
is a dead field. It got started due to WWII
and US DoD funding, and maybe in places there
is still some interest for US DoD problems.
Here is a little: A post above, in response to
a post of mine, claimed that IBM had a good
optimization group. If so, then good for IBM.
But I was at IBM's Watson lab, published a paper
and off and on
considered joining the optimization group there.
Phil Wolfe, William Pulleyblank,
Ellis Johnson. and others were in that group.
At one point, Roger Wets was visiting.
The group did the IBM Optimization
Subroutine Library (OSL).
Then in 3 years near 1994, IBM lost
$16 billion. Johnson joined
George Nemhauser at Georgia Tech.
Pulleyblank became a professor at
West Point. Basically the optimization
group fell apart. Maybe they put
a group back together, but
losing Johnson and Pulleyblank were
E.g., again, with Pulleyblank at West Point,
the US DoD remains interested in
Heck, I supported myself and my wife
through our Ph.D. degrees by working in
optimization for the US DoD.
In academics, the professors were to do research
to get the field going, e.g., research in
'systems analysis', 'mathematical sciences',
'civil engineering', 'production', etc. Yes,
if optimization problems were easy to solve,
then optimization would have central roles
in those fields. Alas, mostly important
are not so easy to solve, even approximately. So, the professors
are still doing research -- maybe in some
decades or centuries they will have something
of serious importance for those fields. I doubt
that the research is very well supported.
I tried to give a summary of essentially a
'cultural contradiction' expecting optimization
to be a popular field in business: By the
time computing is ready to make optimization
easy enough, there are other things to do with
the computing making much more money than with
It's not that optimization can't save money
in business; there is money to be saved;
in a lot of stable businesses, optimization
can provide some of the highest ROI available
to the business. So, there is some ground available
there, what is in principle some fertile ground.
So, there can be some optimization groups
here and there. If the course prof has such
a group in Australia, good for him. With
some really impressive 'cases' published in, say,
INFORMS, maybe mainline business will try
optimization again. I doubt it, but maybe.
Don't hold your breath waiting; there are lots
of impressive cases long since published in
INFORMS, and ORSA, Mangement Science,
etc. The optimization literature is huge
going back to the late 1940s, e.g.,
for Dantzig at Rand and Berkeley.
Here's a little on the difficulty: In the US
there are college accrediting groups, and
for some years they said that an undergraduate
degree in business should have courses
in optimization and statistics. So, for
years each business school student, undergraduate
or MBA, got a course in optimization. For
some years, I taught such courses.
field didn't take off.
I can't recommend that anyone try to have
a career in optimization in business.
You stand to have an easier time supporting
a family with a career as a plumber, literally.
With software, do an information technology
start up, sell out, and pocket, say, $10 million --
knocks the socks off optimization. With irony,
if interested in 'optimization' of your career
and financial security, then avoid optimization!
Optimization is like some item at Dunkin Donuts
that doesn't sell. Lots of other stuff at
Dunkin Donuts sells really well, but that one
item just doesn't. They can do a good job
getting the item ready to eat, put it out
in the display cases, and wait, and what happens
is the item just sits there and goes stale.
Then they throw away the stale, unsold items.
It was a waste. Finally, Dunkin Donuts just
quits offering the item.
Dunkin Donuts doesn't go on and on about
why the item really should sell.
Instead, they just listen to the clear
message they've gotten from the market
and, thus, save having to figure out
solid reasons it doesn't sell.
Similarly all across
business -- some stuff doesn't sell or
doesn't sell very well or sells only a little
and then only into a tiny market. Optimization
in business is like that -- at best, it's a
super tough sale; usually it just doesn't sell.
Optimization, as a field, in business, is a dead
duck. F'get about it and pursue something else.
It's about the course and optimization as
a field, especially in business.
So, I contributed.
Since I've been there, done that, got the
T-shirt, I'm able to make some contributions
few others can, but to make these contributions
I have to draw on some of my personal
experiences. It's not about me or
And, it's not "babble": Instead, in some situations
valuable information, that I very much wish
I'd had long ago. With that information,
I would have avoided trying to have a
career in optimization. Much of my
Ph.D. is in optimization; some of the
rest of my Ph.D. may yet prove to be
valuable, but the optimization part
was essentially a waste. Yes, we
expect some useless chaff in with the
good wheat, but still we don't like it.
Optimization cost me a lot.
Broadly optimization is a siren song, especially
for people with at least one foot in computing.
Since in principle and sometimes in pracitice
the field can save money, enough to give
quite high ROI,
sounds good. Alas, mostly the song is not
good but an invitation to disaster, to taking
a career into a swamp.
I gave you some rare and good insight
that could be quite valuable;
ignore it if you wish.
"Experience is the great teacher,
and some will learn from no other".
I learned about optimization from
experience; it's the very expensive
way to learn; if you throw away what
I reported from my experience, then
you get to take the expensive