RLBS: An Adaptive Backtracking Strategy Based on Reinforcement Learning for Combinatorial Optimization

Combinatorial optimization problems are often very difficult to solve and the choice of a search strategy has a tremendous influence over the solver´s performance. A search strategy is said to be adaptive when it dynamically adapts to the structure of the problem instance and identifies the areas of the search space that contain good solutions. We introduce an algorithm (RLBS) that learns to efficiently backtrack when searching non-binary trees. Branching can be carried on using any usual variable/value selection strategy. However, when backtracking is needed, the selection of the node to target involves reinforcement learning. As the trees are non-binary, we have the opportunity to backtrack many times to each node during the search, which allows learning which nodes generally lead to the best rewards (that is, to the most interesting leaves). RLBS is evaluated for a scheduling problem using real industrial data. It outperforms classic (nonadaptive) backtracking strategies (DFS, LDS) as well as an adaptive branching strategy (IBS).