Testing a solver based on local search [dual]

This post discusses some challenges associated with testing a solver based on local search heuristics. Local search is quite different from mathematical programming-based solvers and it should be tested accordingly. The associated primal post (not yet published) presents the results of my experiments with LocalSolver 3.0.

Local Search VS MI(N)LP: Apples and Oranges

First thing to mention is that I won’t directly benchmark LocalSolver – or any local search, for that matter – against a MILP solver such as CPLEX. A typical mathematical programming (MP) solver spends resources doing two jobs: finding an optimal solution to the model and proving its optimality. A solver based on local search only focuses on the first job. It’s just not fair to ask LocalSolver to be better at what MP solvers were built to do. If your model is easily solvable to optimality using a MP solver, then you should be using that  instead of a local search. However, in some contexts, MP solvers can help assessing whether a local search solver is able to find good solutions.

Is the solver able to find good solutions quickly?

A good local search should be able to quickly find a near-optimal solution. Whether that solution is 0.2% or 0.0002% away from the optimum is not that relevant. What you want to assess, however, is whether the solver gets close to the optimum (search trajectory #1 in figure below) or gets struck in a strong local optimum far away from the optimum (search trajectory #2). In general, a local search algorithm has no way to tell whether it is on a type-1 or type-2 search trajectory, so testing this is quite important. Spending more resources (CPU power or clock time) on the serarch should also result in better solution quality.

SearchTrajectory

A common strategy to test a local search is to use it on mono-objective mixed-integer programming models for which good bounds or optimal solutions are known. Doing this type of experiment can lead to comparing apples against oranges as it requires using local search outside of its traditional sweet spot. On the other hand, I am skeptical about how an algorithm can find good solutions on a very complex model if it cannot handle simple knapsack instances.

Is the solver reliable?

Most local search algorithms depend on stochastic parameters. A good solver should provide reliable performance without requiring fine-tuning several parameters. It should also exhibit stable performance  – that is, solution quality remains constant (and good!) regardless of the random seed used.

Does the solver scale well?

Combinatorial optimization problems are well known for size creep. For a MP solver, small instances are often quite easy to solve, while it is unable to prove optimality on large instances. Huge models are where a local search really can shine, as it does not require storing and managing a branch-and-bound tree. How does the local search handles larger instances? Does it manage resources (CPU effort, parallelism and memory usage) well?  Heuristics based on complete enumeration of a given neighborhood structure can become  exceptionally slow and ineffective on huge instances.

A path not taken

A question I will NOT answer with my tests is how LocalSolver competes against specialized heuristics such as tabu search on a given problem. First, I believe that the burden of proving superior performance befalls on specialized algorithms rather than on general solvers, since they require much more design, implementation and maintenance effort. Second, and more importantly, specialized methods cannot be characterized in general: performance is highly dependent on quality of design, the amount of fine-tuning done as well as the implementation and programming skills of the team.

Hope you enjoyed this rather long post. Stay tuned for the primal post on LocalSolver. How would you test a local search?

Trackbacks

  1. […] experiments with LocalSolver; I encourage you to read this if you didn’t do so already. The dual post describes what are the important questions I wanted to investigate during my testing. Two types of […]

Speak Your Mind

*