story
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.
