{"id":"arxiv/2611.20310","url":"https://arxiv.org/abs/2611.20310","tags":["math.OC","cs.DM"],"score":0,"title":"Strengthening Compact Vehicle Routing Formulations through Arc-Flow Aggregation and Refinement","domain":"math.OC","source":"arxiv","authors":["Julian Yarkony","Willem-Jan van Hoeve","Anthony Karahalios","Martin Karyamsetty","Soheyl Khalilpourazari","Louis-Martin Rousseau","Xiaohang Zhu"],"reviews":0,"subject":"math.OC","summary":"Arc-flow formulations can provide strong relaxations for mixed-integer program formulations of vehicle routing problems, but the associated networks may be prohibitively large. We study the setting in which multiple arc flow relaxations may be applied, and introduce a dual-guided aggregation and refinement framework that constructs substantially smaller arc-flow formulations while recovering the LP bound of the original networks. Dual information is used both to identify states that can be aggregated without weakening the bound and to guide node disaggregation. We show that the resulting…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-11-15","reactions":{}}