Differentiating Network Design Objectives for Balancing Cost and Distance

Many network design tasks must decide which directed arcs to build so that multiple sources can reach a root efficiently. Building fewer or cheaper arcs reduces construction cost, but may force long routing paths; building more arcs shortens routes, but increases construction cost. The Cost–Distance problem formalizes this trade-off, yet it has remained difficult to optimize with gradient-based methods because the selected network, the induced routes, and the routing cost are tightly coupled. We propose Cost Distance Policy Gradient (CDPG), a differentiable framework that treats local next-hop choices as a routing policy, prevents unstable cyclic routing through Dynamic Acyclic Dropout, evaluates the objective with a truncated value solver, and uses the induced acyclic support for quality-preserving TopoRounding. Under the stated conditions, CDPG has a fixed-accuracy \(O(m\log n)\) efficiency guarantee. Experiments cover 1,487 instances in UAV logistics networks, transportation networks, and four synthetic graph families; across this suite, CDPG shows a strong time–quality trade-off compared with other differentiable baselines, Cost–Distance-specific algorithms, and the commercial solver. Our code is available at: https://anonymous.4open.science/r/cdpg_nips-28D5/.