8
Below are some papers from LocalSolver team members that detail local search approaches for diverse combinatorial optimization problems, with some focus on low-level implementation details:
T. Benoist, B. Estellon, F. Gardi, A. Jeanjean (2011). Randomized local search for real-life inventory routing. Transportation Science 45(3), pp. 381-398. pdf (extended ...
8
This is where automatic algorithm configuration and design comes to the rescue. In my experience, different combinations of strategies work equally fine, at least when combined with other components that have a stronger impact in the algorithm (see my work at [1]); it could even be that in certain cases reheating is not necessary.
However, following the ...
6
In addition to the hyperheuristics mentioned by batwing, you can look for the broader topic of (automatic) algorithm selection and configuration.
Generally speaking, algorithm selection is the task of choosing one algorithm among a set of possible ones, based on some information (features) about the problem and instance you want to solve. Configuration is ...
5
I think you may be interested in the topic of hyper-heuristics. Very loosely, given a bunch of local search operators for a problem, the idea is to combine those local search operators to form a short chains. Each chain is a sequence of the local search operators, and so each chain itself acts like a heuristic for the original problem. Typically, the work in ...
4
So we know that MILP instances are independent and that the total throughput is to be maximized. In practice, increasing the number of threads used by a solver to solve a MILP instance could marginally improve the runtime only up to some point. Such optimal number of threads should be checked on a case by case basis. In CPLEX, for instance, the parallelism ...
4
Redefining the solution space is a way to make local search heuristics perform better. This is useful for tightly constrained problems where moving from one feasible solution to another is difficult.
Reformulating the problem, in particular redefining the set of decision variables, is a way to proceed. Such reformulations are well known in integer ...
4
This answer focuses on the "papers that go into the details of implementation on a given optimization problem" part of the question.
In "Variable neighborhood search for the $p$-median" by P. Hansen and N. Mladenovic, they go into quite some detail about how to efficiently implement an interchange heuristic originally proposed in Whitaker ...
4
I'm not an expert in the field, but the paper An effective implementation of the Lin-Kernighan traveling salesman heuristic by Keld Helsgaun was mentioned in another question before.
4
In general you are correct, but the extent to which you are depends heavily on your objective function (and set of constraints, if you have any).
As you say, when the problem changes, the landscape changes, and you will need a different set of hyperparameters. However, small changes, or changes limited to certain features, may alter the landscape in a way ...
3
I suggest you take a look at Variable Neighborhood Search (VNS) method. The Wikipedia page has some useful pseudo codes.
My answer to OP EDIT:
First, I think there is no good or bad algorithm, it depends on how you use the different features.
Getting back to your question, of course VNS is not the only way to have multiple operators. You can implement ...
3
I'm not sure there is a way to tweak your heuristic that will guarantee finding a feasible solution (assuming one exists). What you might try is a restart approach combined with a modification of your priority assignment method. Let's say that the modified heuristic assigns each task a "base" priority and then adjusts it when computing priorities ...
3
Those that you can't completely explore the branch-and-bound tree within your time limit. 😉 Don't forget you can do local search and large neighbourhood search in a branch-and-bound tree: fix some variables, solve, relax the fixings, fix other variables, solve, repeat. You get the best of both worlds with fast feasible solutions from a smaller search tree ...
3
Blot et al. (2018)1 did an extensive literature review on multi-objective LS algorithms. You may wish to take a look at Ishibuchi and Murata (2004)2 which focuses on issues in evolutionary algorithms.
These were found through a very quick search using allintitle: survey OR review OR issue "local search" but the query can be broadened as needed.
...
2
For what it's worth, here you can download our paper on Multithreaded Incremental Solving for Local Search (not to be confused with multi-walk solving (AKA multi-bet solving), multi-tentant solving or multithreaded partitioned solving), which made our Local Search algorithms up to 3 times faster on 4 cores.
2
Elementary learning approaches to select local search operators dynamically - that is, during the search - work well in practice. Here is what we call "elementary learning approaches". Given a pool of local search moves, you can score each move during the search. For example, if one move succeeds at an iteration, increase its score, otherwise ...
2
As far as I know, solution speed for solvers is typically a sublinear function of the number of threads/cores. This makes sense since parallel processing requires additional effort (CPU cycles) to coordinate threads, and may sometimes be subject to blocking. Based on that, and assuming a reasonably large pool of problems and adequate RAM, I would probably ...
1
In general, increasing the dimension of the neighbourhood of a local search can improve the final results, because a local optimum for a neighbourhood is not necessarily a local optimum for a different one, but you need to find a smart way of evaluating the much larger set of solutions. The extent to which this is possible depends on the problem, the ...
1
This talk discusses several approaches to integrate machine learning in local search algorithms by identifying
good solutions
bad solutions
promising neighborhoods
through offline learning of problem instance and solution features.
This paper looks at the frequency of good (partial) paths of locally optimal solutions during runtime. Good partial solutions ...
Only top voted, non community-wiki answers of a minimum length are eligible