I've watched the preliminary videos and I've got to say this seems like some really good stuff. If you like programming challenges, you should definitely sign up for this course. All the assignments and video lecturers are available from the start so you can study at your own pace but you need to submit your assignments on time to receive credit.
Also look out for:
- Algorithms: Design and Analysis, Part 1[1]
- Coding the Matrix: Linear Algebra through Computer Science Applications[2]
They're both starting in 12 days on July 1st.
[0, You may need to be enrolled and logged in to view this thread] https://class.coursera.org/optimization-001/forum/thread?thr...
Of course some people are doing OR but don't know they're doing it. Some just use another label. Other useful search terms include "management science", "operational research" (UK), "advanced analytics", and of course "optimi(s||z)ation".
If you're after an introductory text I can recommend Wayne Winston's Operations Research: Applications and Algorithms. 4th edition. ISBN-13: 978-0534380588
FYI, so far it seems that this course requires lot of hours...
The first week's assignment does not seem that hard after having watched the lecture but I've yet to submit my assignment.
It's a free course and there's no harm in enrolling and giving it a shot. At very least, you'll be exposed to some new and interesting stuff. At best, you'll master some new and interesting stuff.
To me, this seems like the kind of stuff that'll make me "level-up" as a programmer so I'm pretty excited and enthusiastic right now.
My qualifications: I got started in optimization scheduling the fleet at FedEx. In the words of FedEx founder, COB, CEO F. Smith, my work "Solved the most important problem facing the start of Federal Express" and the output from my software was "An amazing document".
Later my Ph.D. research was in optimization and, in part, what I'd wished I'd known while at FedEx.
Since my Ph.D. once there a problem in 'resource allocation' that became a 0-1 integer linear programming problem with 40,000 constraints and 600,000 variables. I derived some math, wrote some software, and in 905 seconds on a 90 MHz PC got a feasible solution within 0.025% of optimality.
And there have been other problems.
For the video, a good, first suggestion for an attack on a knapsack problem is via dynamic programming.
By a wide margin, the most important topic in optimization is the simplex algorithm for linear programming. While the algorithm directly solves many problems in practice, it is the most important tool in solving optimization problems that are not linear programming. Usually there the role of linear programming is as a local linear approximation in an iterative scheme of better approximations.
Much of the reason for the power of linear programming as a tool in larger iterative schemes is the several ways can take a linear programming problem and an optimal solution for it, make some changes in the problem, start with the optimal solution for the old problem, and get an optimal solution for the new problem very quickly.
Good starts in linear programming include:
Mokhtar S. Bazaraa and John J. Jarvis, 'Linear Programming and Network Flows', ISBN 0-471-06015-1, John Wiley and Sons.
Vavsek Chvatal, 'Linear Programming', ISBN 0-7167-1587-2, W. H. Freeman, New York.
Yes, the min-cost capacitated (each arc has a maximum flow it can carry) network flow problem, a special case of which is the transshipment problem (find the least cost way to ship some one good from factories to warehouses; also the source of the Kantorovich Nobel prize in economics) is a linear programming problem, and there the simplex algorithm simplifies and becomes the network simplex algorithm. Curiously, and of importance for fast computation, in the network simplex algorithm a basic feasible solution corresponds to a spanning tree in the network. For that problem, don't miss the W. Cunningham idea of a 'strongly feasible basis' or the more recent polynomial algorithm of D. Bertsekas.
A significantly large fraction of real problems in combinatorial and discrete optimization can be solved as min-cost capacitated network flow problems via the network simplex algorithm. A big reason is, if the flow capacities are all integers and if have an integer basic feasible solution, then the simplex algorithm maintains integer basic feasible solutions for no extra work and, with the usual assumptions, produces an optimal integer basic feasible solution. So this is a case of linear programming where get integer linear programming for no extra effort; really, since nearly all the arithmetic is just integer, don't have to be concerned about roundoff error and get the solution for less effort.
Yes, in combinatorial and discrete optimization, along with the rest of optimization, linear algebra helps.
Curiously, one of the more powerful approaches to combinatorial optimization is a technique from nonlinear programming called Lagrangian relaxation, and there commonly the main computational step is linear programming. With that technique, some nonlinear duality theory can yield some bounds on how far are away from an optimal solution; such duality theory is what yielded the bound of 0.025% above.
For combinatorial optimization there is, say,
George L. Nemhauser and Laurence A. Wolsey, 'Integer and Combinatorial Optimization', ISBN 0-471-35943-2, John Wiley & Sons, Inc., New York.
William J. Cook, William H. Cunningham, William R. Pulleyblank, and Alexander Schrijver, 'Combinatorial Optimization', ISBN 0-471-55894-X, John Wiley & Sons, Inc., New York.
In the OP, the emphasis on NP-complete and algorithms that are worst case exponential is a bit exaggerated. E.g., as in the work of Klee and Minty, the simplex algorithm is worst case exponential, but in expectation in practice it is low order polynomial -- for why, there was some good work by K. Borgward.
For integer, combinatorial, and discrete optimization, I have yet to see a claim that getting approximately optimal solutions is in NP-complete. In particular, if in a real problem have saved $10 million and have a bound saying that can't save more than another $2000, then why spend millions trying to save the last tiny fraction of the last penny and guarantee to have done so? If are willing to sacrifice the last penny, then it is not so clear (so far at least to me) that really are being forced into exponential algorithms, either average or worst case.
The claim in the OP that combinatorial and discrete optimization are part of computer science looks like a case of 'academic theft'! Such optimization has long been regarded as part of applied math and there part of operations research. The material has been of interest in, say, departments of mathematical sciences. Some parts of optimization, e.g., control theory, have been regarded as parts of electronic engineering. At times it does appear that academic computer science wants to regard every topic that makes heavy use of computing as part of computer science! It looks like computer science has gotten tired of just quicksort, AVL trees, BNF, YACC, and RDBMS! :-)!
The claims in the OP about the importance of optimization in the economy are a bit over enthusiastic. Maybe the importance would, could, and should be there, and maybe in Australia they are there, but my experience in the US is that there are essentially no significant non-academic career opportunities in optimization. E.g., at one time near year 2000, I had a nice, long talk with one of the leading US headhunters in technical fields, and he finally confessed that in the previous year in all of the US there had been exactly one recruiting request in operations research. He "packed it in" (from the movie 'The Sting', i.e., gave up) and went to law school!
Here is a good future -- although a wildly long long shot -- for integer, combinatorial, and discrete optimization: At present, all but quite simple problems in such optimization are solved by some experts attacking each problem one at a time, exploiting special structure of each problem, trying various techniques, and, hopefully, finally getting some good results. It's custom, one-off, bench scale, expert, creative, hand work and often, really, some applied research.
In addition, there have long been programs that can be used to pose or enter problems in integer, combinatorial, and discrete optimization suitable for solution by a 'solver'. The problem is, since the programs are general purpose, the 'solvers' to be used are also general purpose and, without the hand work, too often in practice are not powerful enough.
Presumably a polynomial algorithm of low degree that showed that P = NP could be the core of a general purpose solver powerful enough to make solving such optimization problems easy and routine.
Lacking such a solver, in practice patience with such optimization has long been a bit thin.
So, what the heck happened? In much of physics, say, planetary motion, we can write down some equations the real system must solve. If the equations have a unique solution, then that solution must be the right one for the real system. At times since early in WWII, such physics was of enormous value for at least the US DoD.
So, given such an equation, solve it. This technique often worked for, say, initial value problems for relatively simple ordinary differential equations. Alas, for the partial differential equations of fluid flow, the Navier-Stokes equations, the situation was usually a bit challenging.
Also in problems for the US DoD, e.g., 'logistics' or how to move a large army across a large ocean in least time within capabilities of existing resources, could write down some equations and other mathematical specifications that a 'best' solution had to satisfy. So, then, to say how to move the army, just 'solve' the equations, etc. This work was called 'operations research', and at times the US DoD was very enthusiastic about it. With enough US Federal Government research grants to academics, parts of academics got enthusiastic about it. And so did Bell Labs.
But there was no law of the universe that said that finding solutions to such mathematical specifications would be easy. Yes, Navier-Stokes is another example of difficulty. Now, in cryptography, so is the fundamental theorem of arithmetic, that is, factoring a positive integer into a product of prime numbers.
Clay Mathematics Institute in Boston has more than one prize of $1 million available for progress on such things.
Net, it does very much appear that for now making money by building a popular Web site and selling ads on it is a much easier way to make money! And, at times, in such work some applied math, possibly new, can be an advantage. But, clearly for now, the grand goals of integer, combinatorial, and discrete optimization are too difficult for 'prime time' in practice in mainstream business.
Or, problem A can make a lot of money if we have a lot of applied math and computing. So, let's attack problem A. Alas, that much applied math and computing, or even just part of the computing, may be much more valuable for solving other problems!
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 amazing!
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 Express.".
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 NP-complete.
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 complicated.
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. 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.
"Thanks for pointing this out.
First, we obviously cover linear programming and mixed-integer programming in this course. These techniques are indeed very successful in practice and I hope that you will also enjoy these lectures. They make up a third of the class. The references
Integer Programming by Laurence A. Wolsey
Integer and Combinatorial Optimization by Laurence A. Wolsey, George L. Nemhauser
Large Scale Linear and Integer Optimization: A Unified Approach by Richard Kipp Martin
Introduction to Linear Optimization by Dimitris Bertsimas, John N. Tsitsiklis
Understanding and Using Linear Programming by Jiri Matousek, Bernd Gärtner
Theory of Linear and Integer Programming by Alexander Schrijver
This being said, constraint programming and local search are also very successful in practice, often for different types of problems. So this class aims at giving an introduction to a subset of the techniques that are successful in practice (there are other too) as an introduction to the field. My research group uses all three of these techniques to solve large-scale problems in logistics and supply-chains, energy, and disaster management. Some of the problems we solve require the three approaches together to achieve high-quality solutions. To paraphrase John von Neumann defending George Dantzig: "If this technique applies to your problem, use it; otherwise do not".
We also cover column generation and large neighborhood search in the advanced topics. I used to cover Lagrangian relaxation in my class at Brown and we may add a lecture on this. This class has almost all the material of my optimization class at Brown University but not all, since it is a shorter. We may still add an advanced lecture on this topic (I have an additional motivation now)
With respect to the job market, I would simply say: Go to the Informs conference and see how many people, both from academia, industry, and government, are recruiting. Companies such Google, IBM, Amazon, ... have outstanding groups in optimization. Follow Mike Trick's blog and tweeter accounts to get a sense of how lively this community is (see the community link on the page). I never had a student not find a job and most of them did not go to academia. One of them actually works for ... Fedex. My sense is that the opportunities for optimization keep growing and it is an exciting time for optimization. There are many startups, established companies, large multi-national organizations all doing optimization. Some focus on solvers, some on vertical products, some on dedicated applications, and some of several or all of these aspects. The field has progressed significantly.
There is a lot of work, and a lot of progress, in making optimization more reusable and the tools/solvers are now much better in being more generic. Unless P=NP, this will always be a challenge but there are more generic tools to solve classes of applications. There are also solvers that provide a lot more flexibility to build dedicated algorithms much more simply. Many people (including me) spent their research and academic careers trying to design such tools and some make a significant difference in practice.
Finally, optimization is a multi-disciplinary field. My group employs mathematicians, physicists, engineers, and computer scientists. What I personally find incredibly stimulating in this area right now, is that sometimes you need a physicist, a mathematician, and a computer scientist together to solve a complex problem. We all look at a problem from different angles and there is tremendous values in that. I am part of the INFORMS, artificial intelligence, and computer science communities, and some of the scientific contributions I am most proud of are typically those when I was able to bridge two fields. Many of the techniques in optimization come from a variety of fields and this is also what makes it exciting.
And, yes, I am exciting about the future of optimization,
I hope it helps."
In the US, optimization was a field with lots of effort back at least to Dantzig at Rand in the late 1940s. The main push for the field was just the US DoD.
For US business, there have been some niche applications, but the overall situation has long been just as I described -- the field "gets no respect". With rare exceptions, people just don't want it. Elsewhere in this thread I've given nearly exhaustive reports of why basically in US business optimization is a dead duck.