A divide-and-conquer strategy for integer programming problems

Integer programming (IP) is a fundamental combinatorial optimization problem, traditionally solved using branch-and-bound methods. However, these methods often struggle with large-scale instances as they attempt to solve the entire problem at once. Existing heuristics, such as a large neighborhood search (LNS), improve efficiency but lack a structured decomposition strategy. We have proposed a divide-and-conquer strategy for IP, which partitions decision variables based on constraint relationships, optimizes them in smaller subproblems, and progressively merges solutions while repairing constraints. This structured approach significantly enhances both solution quality and computational efficiency. Experiments on four standard benchmarks—minimum vertex cover (MVC), maximum independent set (MIS), set cover (SC), and combinatorial auction (CA)—demonstrated that our method significantly outperforms both state-of-the-art solvers (e.g., Gurobi, SCIP) and advanced LNS-based heuristics. When using Gurobi and SCIP as sub-solvers, our approach achieved up to 30× improvement in objective value on certain tasks (e.g., MIS), and reduced solution cost by over 44% compared to exact solvers in minimization settings (e.g., MVC). In addition, our method showed consistently faster convergence and better final solution quality across all tested problems. These results highlight the robustness and scalability of our divide-and-conquer strategy, establishing it as a powerful framework for solving large-scale integer programming problems beyond the capabilities of traditional and heuristic-based solvers.