Learning local search operator selection

Question

I'm just reading [1]. The authors use a neural network to solve capacitated vehicle routing problems through iterative generation of tours by solving a price-collecting traveling salesman problem in the action selection step of the neural network.

In the conclusion they state that other promising approaches to use machine learning to help solve discrete optimization problems would be to learn the selection of local search operators.

The success of local search methods in tackling these problems suggests an orthogonal reinforcement learning approach, in which the action space is a set of cost-improving local moves, could be successful.

I was very surprised that this has not been studied before, since it seems kind of an obvious avenue to take (no need to encode constraints directly in the NN as it can be handled by the search operators). A quick search only turned up [2], which seems to generate initial solutions via reinforcement learning and then improves these solutions with local search.

Topics like learning to branch in/decompose mixed-integer programs have been studied since at least 2014 [3-5]. I would argue that those topics have much higher barriers of entry than learning search operator selection for VRPs.

Does anyone know of and can point me to research that studies learning the selection of local search operators (think relocate vs. swap)? Does not need to be vehicle routing.

[1] Delarue A., Anderson R., Tjandraatmadja C. (2020). Reinforcement Learning with Combinatorial Actions: An Application to Vehicle Routing. https://arxiv.org/abs/2010.12001.

[2] Zhao, J., Mao, M., Zhao, X., & Zou, J. (2020). A hybrid of deep reinforcement learning and local search for the vehicle routing problems. IEEE Transactions on Intelligent Transportation Systems.

[3] He, H., Daume III, H., & Eisner, J. M. (2014). Learning to search in branch and bound algorithms. In Advances in neural information processing systems (pp. 3293-3301).

[4] Khalil, E. B., Le Bodic, P., Song, L., Nemhauser, G., & Dilkina, B. (2016). Learning to branch in mixed integer programming. In Thirtieth AAAI Conference on Artificial Intelligence.

[5] Kruber, M., Lübbecke, M. E., & Parmentier, A. (2017). Learning when to use a decomposition. In International Conference on AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems (pp. 202-210). Springer, Cham.

Answer 1

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 the task of finding the best combination of parameter values of a given algorithm, for a problem/instance. The line between these two task is blurred, and you can combine selection and configuration, perform configuration based on features, etc.

If you consider a parameter as a choice you don't make in the algorithm design phase, but leave it to the moment you effectively run the algorithm, then you can naturally extend the idea to the choice at runtime of an operator, among a set of possible ones, as a categorical parameter. Likewise, if you think you have a set of algorithms that only differ for the selection operator, then by choosing one operator you are effectively selecting one algorithm. Which task is more appropriate for your case, will depend on what you have (observable features, experience with a certain tool, implementation of your method).

These are, however, learning tasks, where you want to find a mapping between the instance space and the algorithm/parameter space, such that some performance metric is optimized (maximization or minimization of solution quality, minimization or running time, etc). Relevant discussion on this site include this question and this answer. An introduction to algorithm selection can be found e.g. in these two papers or on this webpage. For configuration, this paper or this website and references therein. For how to apply configuration to generate algorithms, you can take a look at this paper. You can also look for "automatic algorithm design" and "hyperparameter optimization" (how configuration is usually called in ML).

Hyperheuristics are a related approach, that combines low-level, generic heuristics to produce an algorithm. The wikipedia page has several links to explore, including this bibliography.

A line of work you might find of interest uses knowledge about what a good VRP solution look like to design a good algorithm for VRP and some variants, and very large instances.

Edited again to add: this preprint uses Reinforcement Learning to dynamically learn heuristic selection policies, it's probably the closest to what you're looking for.

As a sidenote, I think that titles containing "Learning to..." mostly come from researchers in ML, by using different keywords you can find more works coming from areas such as search heuristics/optimization.

Answer 2

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 this field tries to come up with a method to learn those chains, and also tries to come up with an execution schedule for applying the heuristics (which is what you are interested in). Personally, I am not very familiar with this line of work, but you may find the thesis of Chung-Yao Chuang as a starting point. You can find a copy of his thesis online by searching for: Combining Multiple Heuristics: Studies on Neighborhood-base Heuristics and Sampling-based Heuristics.

Answer 3

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 decrease it. Then, when choosing the next move to apply, consider the score of the moves in such a way that moves with higher scores has a higher probability to be chosen.

Such approaches can be infinitely refined. For instance, if your search strategy is not a pure descent (for example, a simulated annealing heuristic), then you can give a bonus to moves than improve strictly the objective value, in comparison with the moves which are accepted because diversifying the search (ex: neutral moves). Then, you can decide to stop attempting some moves when their score is below a given threshold because you consider their probability of success too low. On the contrary, you can decide to shuffle the scores in order to initialize the probability to be chosen, after a number of iterations. This is the famous dilemma between exploration and exploitation in reinforcement learning.

Such an approach being "elementary", there are not so many papers published about it. The idea is quite simple and very practical, with a lot of experiments to perform to tune up all the machinery. This approach is implemented inside LocalSolver, when it comes to the local search techniques, for both discrete and continuous models. It allows us to automatically adapt, for cheap in terms of running time, the selection of the next move to apply among hundreds of possible moves, to the instance which is tackled.

More tuning can be done by offline learning large datasets, as explained above by Alberto. But to start with, on a practical optimization project, we advise avoiding such kinds of tuning (online or offline). Having just a few local search moves following a random choice with equal probabilities at each iteration is generally enough to make a business client happy with your optimization solution.

Answer 4

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 post is conceptually similar but more focused on the machine learning part. It discusses several recent approaches, most if which use graph neural networks.

This paper looks at the frequency of good (partial) paths of locally optimal solutions during runtime. Good partial solutions are injected into the search allowing to explore promising higher-order moves that would otherwise be too computationally expensive to explore.