Surrogate-Assisted Monte-Carlo Tree Search in Facility Location and Beyond (Extended Abstract)

Abstract

Combinatorial problems abound in industry. A persistent issue encountered using search-based solutions is that evaluating particular nodes may be expensive. As an example, organisations frequently adjust their facilities network by opening new branches in promising areas and closing branches in areas where they expect low profits, which may be formulated as a combinatorial search problem. In this extended abstract, we examine a particular class of facility location problems, where the objective is to minimize the loss of sales resulting from the removal of several retail stores. However, estimating sales accurately is expensive and time-consuming. To overcome this challenge, we leverage Monte-Carlo Tree Search assisted by a surrogate model that computes evaluations faster. Initial results suggest that MCTS supported by a fast surrogate function can generate solutions faster while maintaining a solution consistent with non-assisted MCTS.