From the lecture:
"These are the problems we are going to deal with. If you find any efficient solutions for all of them call me. And don't tell ANYONE"
FYI, so far it seems that this course requires lot of hours...
He mentioned that you may need to invest about 12 hours a week on the assignments but that figure is more accurate regarding the latter assignments as they get harder as you go along.
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.
Ugghhh, I signed up for this, my only complaint with coursera is there are way too many classes I want to take. Am already taking two classes that are about to wrap up and am probably spending 15-20 hrs/wk on them (lectures included). Hopefully I can manage the load for the next two weeks.
According to a staff reply[0] on the forums, your assignments will only submit the output of your programs so you can use any language you'd like in the course. Did anyone do the Scala course that ended last month? This course seems like the perfect place to try out your newly developed functional programming skills.
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]
I enrolled and I am very excited. The material looks very interesting, especially since I don't have any formal background in this field and I work in operations research.
How do you like working in OR? Are there a lot of jobs in the field? I'm a math major and like programming, so it seems like it'd be an interesting career for me.
No lots of jobs, no, but there are jobs. It's an interdisciplinary field, so your math and programming background will hold you in good stead. Some basic stats are a good idea too.
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
Pascal is one of the most enthralling lecturers I've ever been... well, lectured by. He's incredibly enthusiastic. I think it comes across in his videos, no? ;)
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.
You really wrote the algorithm for FedEx? Thats amazing!
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 flig...
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...
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
http://www.transtats.bts.gov/fuel.asp
with data for US airlines
2013 April 847.5 2,432.4
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 ...
graycat - remember this is a 7-week course and the lecturer, Pascal Van Hentenryck, in the initial video is stirring up interest imitating Indiana Jones - he's on a quest, he's passionate. So it's not the Hillier and Lieberman textbook approach to Operations Research of old. The whole point was to make the difficult problem of combinatorial problem solving fun and attractive to a wide audience.
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?
The Indiana Jones take off is fine.
Mentioning the knapsack problem is less good
because it's not so important in practice.
Saying that the knapsack problem is difficult
to solve, e.g., encounters exponential
algorithms because technically it's in
NP-complete, is next to irrelevant for practice,
misleading, and hype and not fine.
> 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
on optimization,
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
big mistakes.
E.g., again, with Pulleyblank at West Point,
the US DoD remains interested in
optimization.
Heck, I supported myself and my wife
through our Ph.D. degrees by working ...
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
"narcissistic".
And, it's not "babble": Instead, in some situations
it's darned
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,
the song
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
way, also.
Here is the instructor Pascal Van Hentenryck answer from the coursera forums:
"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
are also provided in the additional material. The work mentioned in the introductory lectures include many applications that are based on mixed-integer programming. So I am not sure where this person is coming from with her/his comment.
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 t...
If the course professor can have
a flourishing, productive group in
optimization in Australia, then good
for him, his group, and the good judgment
of his customers.
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.
I, for one, am very appreciative of this course, and the professor for taking the time to do it. Doing the first week's assignment, I've already learned a lot about programming for NP-hard problems.
25 comments
[ 33.7 ms ] story [ 873 ms ] threadFYI, 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.
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...
[1]https://www.coursera.org/course/algo
[2]https://www.coursera.org/course/matrix
http://www.codeforces.com http://www.topcoder.com/tc
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
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, Wil...
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 flig...
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...
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 ...
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 on optimization, 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 big mistakes.
E.g., again, with Pulleyblank at West Point, the US DoD remains interested in optimization.
Heck, I supported myself and my wife through our Ph.D. degrees by working ...
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 "narcissistic".
And, it's not "babble": Instead, in some situations it's darned 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, the song 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 way, also.
"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
are also provided in the additional material. The work mentioned in the introductory lectures include many applications that are based on mixed-integer programming. So I am not sure where this person is coming from with her/his comment.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 t...
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.