A spatial branch-and-price-and-cut algorithm for finding globally optimal solutions to the continuous network design problem

Transportation network design, or the problem of optimizing infrastructure for a societal goal, subject to individual travelers optimizing their behavior for their own preferences, arises frequently in many contexts. However, it is an NP-hard problem due to the leader-follower or bi-level structure involving a follower objective that is different from yet significantly affects the leader objective. Creating globally optimal solution algorithms has been particularly difficult for the continuous network design problem (CNDP), in which leader variables are continuous, because of the many nonlinearities arising therein. We present a globally optimal algorithm for the CNDP based on using the high-point relaxation, i.e., the system optimal CNDP, and value function cuts to find lower bounds and solving the traffic assignment follower problem to find upper bounds. We introduce a convex relaxation and a spatial branching scheme to handle the non-convexity of value function cuts. This leads to a spatial branch-and-cut algorithm that gradually cuts out bi-level infeasible points from the feasible region of the CNDP. To enhance computational performance, we outer-approximate nonlinear convex functions and use column generation to obtain a sequence of linear programs that can be solved relatively quickly. We show that, for a predefined ϵ, our spatial branch-and-price-and-cut algorithm converges to ϵ-optimality. Compared to prior work on globally optimal solution algorithms for CNDP, we can find ϵ-optimal solutions for the same small test networks in much less time, or solve CNDP on problem instances based on networks that are two orders of magnitude larger than those used in the literature.