UC San Diego

This thesis proposes a general search algorithm design for hard combinatorial optimization problems. Monte Carlo Tree Search(MCTS) method is a heuristic search method that partitions the search space balancing exploration and exploitation. The goal is to develop an MCTS framework to navigate the combinatorial input domain that uses existing black-box solvers as subroutines. We design different ways to partition the input regions with MCTS and analyze their search efficiency based on experimental results with different combinatorial problems. The experiments show this framework can outperform other search frameworks and state-of-the-art commercial solvers such as Gurobi by finding more optimized solutions in a shorter wall-clock time.