Computing Bipath Multicommodity Flows with Constraint Programming–Based Branch-and-Price-and-Cut.

The article focuses on a novel constraint programming (CP)–based branch-and-price-and-cut (BPC) framework developed to exactly solve the bipath multicommodity flow (BP-MCF) problem, which involves routing demands in a capacitated network via two arc-disjoint paths with bounded delay differences at minimum cost. The authors prove the NP-hardness of BP-MCF and its pricing problem, propose two mixed-integer linear programming (MILP) formulations alongside a CP formulation, and introduce a two-level branching scheme combining delay-based and divergence node–based branching. Experimental evaluation on 522 diverse instances demonstrates that the CPBPC approach significantly outperforms compact MILP and CP models in optimality gap, runtime, and solution quality, highlighting the effectiveness of integrating CP modules for column generation, cut generation, primal heuristics, and branching node heuristics within the BPC framework. The methodology is presented as a generalizable CP-LP hybrid framework applicable to other routing and combinatorial optimization problems, with suggestions for future enhancements including improved capacity constraint filtering and deeper CP–LP integration.