# BalMCTS: Balancing Objective Function and Search Nodes in MCTS for Constraint Optimization Problems

arXiv: https://arxiv.org/abs/2312.15864 · HTML: https://mlsanity.com/paper/2312.15864/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 4 of its 25 references that are in the map.
- First posted on arXiv 26 Dec 2023.

## Builds on (most cited first, 4 of 4)

- [Fast Graph Representation Learning with PyTorch Geometric](https://mlsanity.com/paper/1903.02428/) (2019)
- [Learning to branch with Tree MDPs](https://mlsanity.com/paper/2205.11107/) (2022)
- [Solving NP-Hard Problems on Graphs with Extended AlphaGo Zero](https://mlsanity.com/paper/1905.11623/) (2019)
- [First-Order Problem Solving through Neural MCTS based Reinforcement Learning](https://mlsanity.com/paper/2101.04167/) (2021)

## Built on by (most cited first, 2 of 2)

- [MALinZero: Efficient Low-Dimensional Search for Mastering Complex Multi-Agent Planning](https://mlsanity.com/paper/2511.06142/) (2025)
- [NonZero: Interaction-Guided Exploration for Multi-Agent Monte Carlo Tree Search](https://mlsanity.com/paper/2605.00751/) (2026)

## Abstract (arXiv)

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.