Local search: uses (good and bad)

Some time ago @lambdadmitry asked me to elaborate  a bit about some discussion about the relevance of local search, which originated from a tweet by @JeffLinderoth. I apologize that it took me so long to complete this post, but I found some additional wisdom in yesterday’s talk by @MikeTrick. I will provide some examples of known problems. I am aware that the subject of local search-based heuristics is controversial and polarizing in the field of mathematical programming, but I doubt this post will add much fuel to the fire.

Because it’s NP-hard [really, really bad]

NP-hard is a theoretical proprety and does not mean much in practice. The knapsack problem is a NP-hard problem yet it can be solved very, very fast in practice, while some linear programs (a P problem) are yet quite challenging. p43 is a very small traveling salesman problem (TSP) instance that gives nightmares to most solvers, but many large instances are solved almost instantly. If your problem is a mixed-integer program (MIP), don’t say it can’t be solved by MIP solvers unless you’ve actually tried really hard. I’ve seen many papers using heuristics for problems that would take less than 1 second to solve. Try it first, as it does not take much time and you might be surprised with the results.

Your problem is inherently non-linear  [depends]

Some problems have relationships between variables that are inherently non-linear or even non-convex. This is common in some revenue management problems, where demand is affected by many factors such as price, lead times or service, which is affected by some variables. In local search, evaluating any kind of function is usually rather straightforward, while decomposing these in MIPs or MINLPs involve adding approximations or additional variables. Sometimes approximations do the job too, but there are times when they don’t. If a MINLP solver does not do the job, then heuristics are a good idea.

The structure of your problem favors local search [good]

For any problem to be a good fit with local search, two things must exist: (1) some sequencing problem lend themselves pretty easily to local search, as it is easy to design operators to move from one solution to another, and (2) an efficient way to encode the solution. Some complex routing problems have this structure. I currently work on a project involving inventory routing and packing problems where we have many soft constraints that would be difficult to put into a column generation procedure. A classical MIP was also out of the question.

You need a feasible solution ASAP [depends]

Sometimes, you don’t really need the optimal solution to your problem, but need an okay solution while time is of the essence. In this case, heuristics can be a good approach. Be aware, however, that the ability of LP and MIP solvers to find feasible solutions quickly has improved tremendously and continually over the past ten years. Yet, some models pose problems to solvers. It is often the case for routing problems. A specialized column generation or branch-and-price might find a feasible solution quickly, but an out-of-the-shelf MIP solver can take several minutes before finding a feasible solution.

You have plenty of time to improve the solution [good]

Suppose you have a problem that is really difficult to solve, but you have more than enough time to try to achieve a better solution. A good way to try to find a better solution is using large neighborhood search. In this approach, you fix most of the solution (say, 3/4 of the integer and binary variables) and then solve the remaining using a MIP solver. Then you fix the variables to the solution you just found, but unfix another quarter of the variables. What I really like about this approach is that using a solver guarantees you will find the best solution in the neighborhood you explored. It’s especially effective on problems where the MIP search tree of the complete problem grows very large, so letting the solver run for more time is not a good strategy.

There are many more good or bad reasons, but the fact remains that local search can be efficient when used properly and is quite a crappy tool when used in bad contexts or done improperly. Until then, may you find the proper OR approach to solve all your problems.

Speak Your Mind