Exploring Integrality Grip for Mixed-integer Programming by MCTS Planning

In modern Mixed-integer Programming(MIP) solvers, the concept of heuristic is well rooted as a principle underlying the search of high-quality solutions. In this respect, Large Neighborhood Search (LNS) has been the first refinement heuristics for improving existing solutions through a generic MIP solver used as a black box. For a refinement heuristic, the quality of the search neighborhood is of critical importance. However, existing methods have not fully investigated the strategy for balancing exploration and exploitation of search spaces. In this work, we introduce a novel refinement strategy for improving MIP solutions. The proposed framework leverages the ideas of integrality grip to guide the neighborhood selection. Moreover, in order to achieve a good trade-off between exploration and exploitation of the solution space, the LNS search is further improved by investigating the convex relaxations of LNS sub-problems with Monte Carlo Tree Search (MCTS). In particular, at each iteration of LNS, MCTS is firstly executed to evaluate the integrality grip of the convex relxations of next LNS sub-problems. Then the expanded MCTS tree will select a promising solution neighborhood, which will be solved to produce improving solutions. Our MCTS method reduces the challenging LNS neighborhood selection problem to solving a series of LP relaxations. Those LP problems are polynomial-time solvable, ensuring computational tractability. We have conducted comprehensive computational experiments demonstrating significant performance improvements of our proposed algorithms over existing LNS methods, particularly in complex MIP scenarios.