Exploring search space trees using an adapted version of Monte Carlo tree search for combinatorial optimization problems. (February 2023)

• Record Type: Journal Article
• Authors: Jooken, Jorik; Leyman, Pieter; Wauters, Tony; De Causmaecker, Patrick
• Is Part Of: Computers & operations research. Volume 150(2023)
• Publication Date: 2023-02
• Subjects: Combinatorial optimization -- Monte Carlo tree search -- Quay crane scheduling problem with non-crossing constraints -- 0-1 Knapsack problem; Operations research -- Periodicals; Electronic digital computers -- Periodicals; 004.05
• DOI: 10.1016/j.cor.2022.106070
• Languages: English
• ISSNs: 0305-0548

Abstract

Abstract: In this article we propose a heuristic algorithm to explore search space trees associated with instances of combinatorial optimization problems. The algorithm is based on Monte Carlo tree search, a popular algorithm in game playing that is used to explore game trees and represents the state-of-the-art algorithm for a number of games. Several enhancements to Monte Carlo tree search are proposed that make the algorithm more suitable in a combinatorial optimization context. These enhancements exploit the combinatorial structure of the problem and aim to efficiently explore the search space tree by pruning subtrees, using a heuristic simulation policy, reducing the domains of variables by eliminating dominated value assignments and using a beam width. The algorithm was implemented with its components specifically tailored to two combinatorial optimization problems: the quay crane scheduling problem with non-crossing constraints and the 0-1 knapsack problem. For the first problem our algorithm surpasses the state-of-the-art results and several new best solutions are found for a benchmark set of instances. For the second problem our algorithm typically produces near-optimal solutions that are slightly worse than the state-of-the-art results, but it needs only a small fraction of the time to do so. These results indicate that the algorithm is competitive with the state-of-the-art for two entirely different combinatorial optimization problems. Highlights: An adaptation of Monte Carlo tree search is proposed to explore search space trees. The proposed algorithm aims at solving combinatorial optimization problems. The algorithm is shown to be competitive for two combinatorial optimization problems. It typically produces high-quality results fast for the 0-1 knapsack problem. Several new best results are found for the quay crane scheduling problem.