(no title)
cleancoder0 | 4 years ago
When TSP is mentioned today, unlike 50 years ago when LK heuristic got published, I assume all of the popular & practical variants, like time window constraints, pickup and delivery, capacity constraints, max drop time requirement after pickup, flexible route start, adding location independent breaks (break can happen anytime in the sequence or in a particular time window of day) etc. Some of the subproblems are so constrained that you cannot even move around that effectively as you can with raw TSP.
Some of the subproblems have O(n) or O(n log n) evaluations of best local moves, generic solvers are even worse at handling that (Concorde LP optimizations cannot cover that efficiently). When no moves are possible, you have to see what moves brings you back to a feasible solution and how many local changes you need to do to accomplish this.
For example, just adding time windows complicates or makes most well known TSP heuristics useless. Now imagine if we add a requirement between pairs of locations that they need to be at most X time apart (picking up and then delivering perishable goods), that the route can start at an arbitrary moment etc.
I personally spent quite a lot of time working on these algorithms and I'd say the biggest issue is instance representation (is it enough to have a sequence of location ids ?). For example, one of my recent experiments was using zero suppressed binary decision diagrams to easily traverse some of these constrained neighborhoods and maintain the invariants after doing local changes. Still too slow for some instances I handle (real world is 5000 locations, 100 salesmen and an insane amount of location/salesmen constraints).
graycat|4 years ago
I did a lot in optimization, in my Ph.D. studies and in my career, but I dropped it, decades ago -- my decision was made for me by my customers, essentially there weren't any or at least not nearly enough that I could find.
Actually, my summary view is that for applications of math in the US, the main customer is US national security. Now there are big bucks to apply algorithms and software to some big data, and maybe, maybe, there is some interest in math. But the call I got from Google didn't care at all about my math, optimization, statistics, or stochastic processes background. Instead they asked what was my favorite programming language, and my answer, PL/I, was the end of the interview. I'm sure the correct answer was C++. I still think PL/I is a better language than C++.
Early in my career, I was doing really well with applied math and computing, but that was all for US national security and within 50 miles of the Washington Monument.
Now? I'm doing a startup. There is some math in it, but it is just a small part, an advantage, maybe crucial, but still small.
cleancoder0|4 years ago
There's a lot of companies that want to provide an Uber/Lyft-like service of their own product. So you have a bunch of smaller problems that you want to solve as best as possible in ~1 second.
A lot of small companies with their delivery fleets want to optimize (pest control, christmas tree delivery, cleaning, technical service, construction (coordinating teams that construct multiple things at multiple locations at the same time) etc.).
On the other hand, not related to TSP, the whole energy market in the US is very LP/ILP optimizable and has a lot of customers (charging home batteries, car batteries, discharging when price is high, etc.).
I would admit that the scientific field of discrete optimization is littered with genetic algorithms, ant colonies and other "no free lunch" optimization algorithms that make very little sense from progress perspective, so it does feel like the golden era was from the 70s to early 90s. I do not have a PhD but somehow ended up doing machine learning and discrete optimization most of my career.