A Monte Carlo Tree Search for Budget-Constrained Combinatorial Optimal Facility Investment Problem with a Blackbox Objective Function

A budget-constrained combinatorial optimal facility investment problem is a problem that optimally locates multiple facilities on the vertices of a given undirected graph and allocates many different types of equipment to each facility under a budget constraint. The objective function is not given explicitly, and we can know the evaluation of our investment through a given noisy blackbox function. We propose a search method using Monte Carlo tree search (MCTS) for this problem with a noisy blackbox function. In our search through MCTS, we make use of the lattice structure of subspaces defined using a hierarchical range partition for each variable and reinforce to select good order of variable range partitions preferentially using the upper confidence bound score, into which rapid action value estimation method is incorporated, for selection operations. The effectiveness of our proposed method is demonstrated through the experiments for the layout optimization problem of distributed small power grids (nanogrids) using a public simulator and data that are based on real-world maps, population, and weather as a noisy blackbox function and another setting including an undirected graph, respectively.