F-CutLearn: A feasibility-guaranteed cut learning method for network design problems

Network Design Problems (NDPs) are fundamental and widely applied in transportation, logistics, and infrastructure planning. They are computationally demanding due to their combinatorial complexity. In this study, we focus on freight transportation NDPs and leave NDPs with user equilibrium (UE) for future work. Within the freight NDPs, the existence of numerous problem variants often necessitates significant algorithmic customization, limiting the generalization capability of existing methods across different settings. These limitations highlight the need for a more generalizable solution framework. Recent advances in learning-based optimization have demonstrated strong potential for enhancing generalizability in combinatorial optimization, and this potential naturally extends to NDP variants. Nevertheless, ensuring feasibility remains a critical challenge, as prediction errors often lead to constraint violations. To address these challenges, we develop a general Feasibility-Guaranteed CutLearning (F-CutLearn) method, a novel learning-enriched optimization framework that improves computational efficiency while guaranteeing feasibility. F-CutLearn first employs an NDP-oriented GCN predictor to estimate the probability of network design variables being selected in the optimal solution. These predictions are then used to guide a feasibility-guaranteed cutting plane generation mechanism, thereby reducing model size and narrowing the solution space to enhance computational efficiency. We further establish theoretical conditions for achieving global optimality and analyze the influence of key framework components on the quality and feasibility of the generated cuts. Extensive computational experiments on two NDP variants demonstrate that F-CutLearn consistently outperforms the baseline methods and generalizes effectively to larger-scale instances. The core ideas of this framework can be extended to support more NDP variants with further development and are broadly extensible to a wide range of linear and nonlinear mathematical programming models with binary decision variables.