Reduce-then-Solve: Iterative Search via Reduction for Combinatorial Optimization

Neural combinatorial optimization (NCO) has emerged as a promising approach to combinatorial optimization problems (COPs). Existing Learning-to-Construct (L2C) methods have complementary limitations: global prediction (GP) provides scalable guidance but struggles with complex constraints, while local construction (LC) handles constraints well but incurs sequential solving overhead. We therefore propose Reduce-then-Solve (RS), a general framework that iteratively retains promising structures from an incumbent, reduces the COP to a residual subproblem, and re-solves it. For NCO, we instantiate RS as COReformer, a Learning-to-Search (L2S) method that couples GP and LC through problem reduction, with Perturbed Rectified Flow (PRF) as the global predictor and SymNCO as the local constructor. At each iteration, PRF identifies promising incumbent structures to induce a size-controllable LinkGraph, which SymNCO then solves to refine the incumbent. PRF adapts rectified flow to iterative search by transporting over perturbed-solution distributions rather than a single optimum. Extensive Experiments on TSP, CVRP, and CVRPTW show that COReformer achieves SOTA among learning-based solvers across prior L2C, L2S, and D&C comparisons. A learning-free RS instantiation on MCut further shows that the framework extends beyond neural routing.