In the field of mathematical optimization there is hardly a problem of more fame than the traveling salesperson problem (TSP). Given a number of cities and the distances between them, find a “round-trip” (a tour) that visits every city, returns to the starting point, thereby covering a shortest possible distance. There is a wealth of applications; a historical one is drilling holes on a printed circuit board in a smallest amount of time, but there are many, many more: DNA sequencing, delivering parcels, painting car bodies, storing containers in a harbor, … I would say: whenever you have to find a best ordering or sequence of actions, there is a TSP somewhere around the corner. And that happens a lot in production, logistics, transport and traffic, and elsewhere.
The scientific literature has countless models, solution approaches, and also deep theoretical results and conjectures, you cannot read all this. Try google scholar with “traveling sales* problem” (the * because in former times, the person usually was a man) and you get almost a quarter of a million hits! One could explain our entire field only relating to this problem. “Well-studied” is a gross understatement.
About two weeks ago, Randal Olson posted an optimal road trip to visit each U.S. state and D.C., 49 cities in total. Randal implemented his own algorithm, provided beautiful visuals, explained the results, etc., still — without even reading the post to its end at the time — I tweeted
The reason for my spontaneous (you may also call it: arrogant) reaction: This is precisely the setting that started the success of the most powerful technique available today for optimally solving the TSP; presented in this paper from 1954:
Well, 49 cities was large-scale 60 years ago. Bill Cook maintains a web page where you can see optimal tours through more than 85.000 cities! There is even an app for that for your phone. It is so incredibly incredible that this is possible, due a tremendous algorithmic progress (not only improved machines), but this is a different story. In any case, reason enough, for us optimizers, to think about the TSP as being practically solved.
Now, it is an important question:
How on earth can it happen that, what we optimizers think every kid should know, is not even used by every well-educated scientist in a nearby area?
Entering Nathan Brixius with a wonderful metaphor that our optimization tools may be so powerful and general that in situations where this full power is not needed, our tools may be simply overlooked. Read Nathan’s post, it says much more what goes wrong here. Bottomline is that we are lousy marketers of our profession if we always insist on this generality and power, even when a little less would do. We scare people away with too much technical detail.
Nathan (rightfully, in my opinion) suggests that in order to reach practitioners we sometimes may need to simplify, we may hide scientific rigor in public communication, and may accept that when a practitioner is happy, this may be already optimal — even when it is not in theory.
Once the door is open, you can still provide more tools and a more optimal solution.
Jeez, I bit on my tongue, before I wrote that. Yet, I believe that many of us can agree on what Nathan writes. Operations research and mathematical optimization needs more marketing, more simple examples, more accessible success stories — even though many of us are working on that, it is not enough yet.
No additional post necessary until here.
But now comes what somewhat depresses me. Randal was recently interviewed by NPR News about his work. And you may read the mind of the interviewer, between the lines: Can this scientist really be thinking that this “improbable” tour of 49 U.S. cities will really, ever be traveled by any family?
Can this really be of any practical use?
Yes, Randal may have missed the opportunity to speak further about practical applications of the TSP, but he did provide one accessible example, he did speak in everyday language, he did good marketing for the idea of optimization. And still it seems to be a very fragile construction to convince people about optimization. You have to find exactly the right examples, exactly the right words, exactly the right level of simplification. And all this may vary across the persons you talk to. Is it really so hard to abstract, so hard to at least conceive that this or any other optimization problem may be useful in companies, services, science, everyday life?
Are we too complicated for this world?
café opt 
“How on earth can it happen that, what we optimizers think every kid should know, is not even used by every well-educated scientist in a nearby area?”
If he does not know, he is not well educated as a computer scientist. So, why should he not use it? Genetic algorithms will always be sexier to the public than cutting planes or column generation and so their marketing is easier.
“… we may hide scientific rigor in public communication, and may accept that when a practitioner is happy, this may be already optimal — even when it is not in theory.”
We should be aware that we rigorously solve models not problems. So what is optimal in theory quite often will be inferior in practice because we neglected some side constraints that we did not know or care about. I think this is well known in our community and communication with practioners, which are well educated in their field, is not that bad.
LikeLiked by 1 person
Fully agree, Winfried, talking to and working with well-educated practitioners is fun and productive. Yet, we have already reached these persons. Point of the post was that it may be difficult to reach the others. One way to address this is to better educate people in optimization and operations research. Let’s do this 😉
LikeLike
Of course OR software needs to be simpler to use, as does any other software out there. I don’t think anyone can disagree with that.
I think all vendors have been trying to make their solvers easier to use (at least I have in OptaPlanner – one of our core principles is that OptaPlanner is usable by normal Java programmers). The question is not what we need to do, it’s how we need to do it. And it’s not 1 big step, but thousands of little steps.
LikeLiked by 1 person
Thanks, Geoffrey; “usable by normal Java programmers” is an interesting detail of your comment. I can really appreciate that “simplicity” as probably many can. But those who decide about using OR tools in their company or not in the first place may not code at all, so they may not be able to value that. I wanted to point out that it may be hard to reach those who do not know about the greatness about OR tools yet; simple to use tools certainly contribute to helping convince decision makers, so please keep up the great (simplifying) work! It makes life easier for those who are already “on our side.”
LikeLike
We’re also aiming at business people who don’t have any coding skills, with OptaPlanner Workbench, but that’s work in progress 🙂 That’s a real challenging area.
LikeLiked by 1 person
I am torn two ways on this, as on most things. I guess the clues were there when I did physics at university, when my “love” was the abstract theoretical stuff about relativity and quantum mechanics and all that jazz, but what I was actually good at was making practical experiments work, and grinding out the measurements, driving down the errors etc. So it still is now: I love and need the theoretical foundations of optimisation et al, but what I am good at is making it work in a practical context. To me, the giants of the subject area have laid the foundations and given us a set of tools and techniques which are of enormous value. But it is really very hard to understand how those techniques actually work in any real-world sense. If somebody has a real-world business problem, it is probably stated in business terms, such as allocation of meeting rooms to a set of meetings, or manufacturing widgets in different sizes & colours. I don’t think that anyone in the world could explain the whole gamut of techniques and how they map onto the business problem. You can usually take them as far as the starting point of modelling, typically a 2D array of binary variables for an allocation problem for example, and can show them how some of their business requirements map onto limits on sums of subsets of those variables. But beyond that we find it really hard to get them to see what we are doing. Going on to explain how those requirements are written as constraints, which are equations in (usually linear) algebra, which maps onto an N-dimensional polytope, which we can explore in some systematic fashion, such that each single point in that space is a whole complete solution for their problem, and then how that search is managed (e.g. branch & cut, branch & price), introducing cuts to reduce the search space, using heuristics to accelerate the search, meta-heuristics, hybrid algorithms, and much much more. There is simply NO WAY that standard business users will follow it all. So detailing the full power of the tools doesn’t actually help the business case; instead it scares people away.
But the good news is that people don’t have to do know about all the full power and generality of the tools. Most computer users don’t know how the computer works, just like most drivers don’t really understand how a car works. I consider myself lucky in that I have some insights into the whole computing “stack”, from quantum mechanics to basic electronics (how transistors etc work), through how logic gates work, to building logic circuits, some microcode, assembler etc, building my own trivial compiler, and so on up through many programming languages (C, Fortran, Algol68, Lisp. Prolog, POP11, C++, C#, Java, PHP, and many others), and so on. So for me, the tools like CPLEX, Gurobi and Xpress are just tools or components that I use to solve problems. We all owe a huge debt of thanks for those wonderful people who have dedicated years to making each of these tools as good as they can be. That is all the way from the chip designers and manufacturers, compiler writers, operating systems and so on up to the top-level tools that we use. But, there is NOBODY who understands it all.
The message needs to be simple:
* People are actually not very good at solving complicated problems where there are sets of interacting decisions to be made. People will make decisions on the wrong criteria, in the wrong order, make assumptions and paint themselves into a corner.
* Combinatorics will bite you very fast and hard if the problem size increases on many problems, so what works OK for scheduling 10 people may totally fail for 20, if it is programmed naively.
* Clever people have done an awful lot of thinking about these sorts of problems, and have developed a vast body of knowledge and a large collection of tools and techniques that work well for solving these sorts of problems.
* Almost nobody starts from scratch to build their own car or house, or factory, or whatever. Most often there is something suitable off the shelf or ready-built if it is small enough. If not, they call in someone who is (hopefully) an expert to design it, somebody else to build it, etc.
Why then do people seem to think that they can build software and systems to solve complex business problems from scratch? They wouldn’t build their own computer chips and hard disks. They didn’t build the offices they sit in. I believe that it is just that they don’t understand how ferociously difficult these problems can be, and how explosively they can grow complicated.
People need to see that what they are doing as part of their everyday job is actually solving hard problems. That is why companies pay them money. We have the tools and techniques to help them solve bigger and harder problems, faster and better than ever before. That way, the companies will value them even more, and maybe pay them even more.
If you want a car fixed, you go to a garage.
Pipes leaking? you call a plumber.
Want an office built? go to an architect and/or builders.
Want a sales database? Call in experienced DBAs etc.
Company website? Use a web design company.
100 engineers to schedule for a week? I’ll just do it in my head or in Excel…
*That* is where the education needs to be aimed.
LikeLiked by 1 person
Tim, I am overwhelmed by your comment, actually I think you should start blogging yourself — I am sure you have much much to offer for the community. What I gather is that people do not “feel” that what they are doing every day is utterly complicated and they don’t know that there could be a tool or technique or whatever on earth to help them do their jobs better. So the least we can do is to tell more and more people (in my case: students) about possibilities. So that at least they know that in case they face a planning/decision/whatever complicated situation they should seek someone who knows help, and they look for that person because they know he/she exists. Well, in the end, that’s us.
LikeLiked by 1 person
Apologies for writing so much,but this is something I care deeply about. I hadn’t realised I had written so much when I hit the “post” button 😦
But thank you for your patience and tolerance. Maybe I will start blogging too. Following in the footsteps of a master…
LikeLiked by 1 person
No need to apologize at all, I am glad to hear what others think about this topic. And thanks for the flowers also 😉
LikeLike
A related point – as well as people not understanding that they are trying to solve hard problems and trying to do so by using poor techniques, there has been a big surge in belief in “Big Data” as the source of new insights that will drive business to better things.
The problem is that there is an unwritten assumption that more (and hopefully better) information will lead to better business decisions. That (to me at least) is a complete fallacy. People are poor at making complex decisions, and usually giving them more information does not improve that process, it often makes it worse.
Decision technologies, prescriptive analytics etc *is* the way to make better decisions. If a fraction of the investment in “Big Data” was spent instead on decision sciences and technologies, we would live in a better world.
LikeLiked by 1 person
Amen!
LikeLike
First of all: Thank you, Marco, for your cool blog! It is so much fun to read. 🙂
Coming from academia and being out in the “real world” for a still rather short while now, I figure that we probably ask the wrong question. Imho, it is not “What powerful tools can we offer to the business world?” but rather “What is a company actually looking for?” Is it really top-notch optimization techniques and software to improve their decisions or processes?
Undoubtedly, we all agree that companies can profit a lot from them. But in fact, there are issues that are even more important to a company…such as software that is easy to use potentially by workers of all levels, software that smoothly integrates all aspects and different areas of the business at hand, software that runs reliably and that may easily be adapted to a changing environment. One can often already save an incredible amount of money by simply properly integrating IT from all parts of a company. (IT consultants make their living with it…) Without easy-to-use software one need not even start thinking about a powerful optimization core that may give you some extra advantage.
With that in mind, I think it makes much more sense to talk to consulting companies and collaborate with them to solve business problems (of their clients) together. It should be much simpler that way to convince also non-math managers of what difference we can make.
LikeLiked by 1 person
Two further brief thoughts, agreeing with Raymond…
First, solve the right problem. The best solution to the wrong problem doesn’t necessarily help anyone. So LISTEN to your business users and solve the right problem.
Second, make the software USABLE. The best possible solution and software are not of practical value to our customers if it doesn’t actually get used.
LikeLiked by 1 person
Danke Raymond! I have been thinking about blogging about the question you ask “what is it that a company really needs?” I agree that for many *much* more basic needs are to be satisfied than high-end optimization. But even for (in that respect) “sophisticated” companies, it may be hard for them to tell that they may need optimization, simply because they may not be aware of its usefulness. Brings us back to better educate people…
LikeLike
I’ve seen a Google mash-up to compute the USA contiguous states TSP yielding 113 hours, Well below Randal’s 224 hours. Not sure though. if it is very official or under the same constraints. But the trip is doable within a working week’s time span, which can’t be bad 🙂
LikeLike
I found your blog post and all the comments very interesting. You might find this article interesting:
http://bear.warrington.ufl.edu/centers/mks/articles/243/a4757a7def_article.pdf.
This is an article by founders of a sales and marketing company ZS Associates (disclaimer: I briefly worked there 10 years back). I find this article a good example of how couple of faculty were able to take their research work on optimization and build it into a company. Specifically, the article also shows how their experience and learning were shaped by working with industry.
LikeLiked by 1 person
Thanks for sharing, Shankar. Thankfully, there are several inspiring and ecouraging examples of successful and useful use optimization in practice. Incidentally, I found this post yesterday, it says “start right away with optimization”: http://www.ibmbigdatahub.com/blog/optimization-really-complex
LikeLike