BalMCTS: Balancing Objective Function and Search Nodes in MCTS for Constraint Optimization Problems
This work addresses the need for faster near-optimal solutions in combinatorial optimization, though it is incremental as it builds on existing MCTS and neural network techniques.
The paper tackles constraint optimization problems by proposing a novel heuristic neural network algorithm based on MCTS that balances search and training to find near-optimal solutions quickly, achieving a gap of less than 17.63% within the first 5 feasible solutions and reducing search nodes by less than 5% compared to state-of-the-art methods.
Constraint Optimization Problems (COP) pose intricate challenges in combinatorial problems usually addressed through Branch and Bound (B\&B) methods, which involve maintaining priority queues and iteratively selecting branches to search for solutions. However, conventional approaches take a considerable amount of time to find optimal solutions, and it is also crucial to quickly identify a near-optimal feasible solution in a shorter time. In this paper, we aim to investigate the effectiveness of employing a depth-first search algorithm for solving COP, specifically focusing on identifying optimal or near-optimal solutions within top $n$ solutions. Hence, we propose a novel heuristic neural network algorithm based on MCTS, which, by simultaneously conducting search and training, enables the neural network to effectively serve as a heuristic during Backtracking. Furthermore, our approach incorporates encoding COP problems and utilizing graph neural networks to aggregate information about variables and constraints, offering more appropriate variables for assignments. Experimental results on stochastic COP instances demonstrate that our method identifies feasible solutions with a gap of less than 17.63% within the initial 5 feasible solutions. Moreover, when applied to attendant Constraint Satisfaction Problem (CSP) instances, our method exhibits a remarkable reduction of less than 5% in searching nodes compared to state-of-the-art approaches.