The hub location problem with comparisons of compact formulations: A note
本文比较了p-枢纽选址问题的三种紧凑型公式（路径型、流型等）在理论松弛强度和计算性能上的差异，发现路径型公式线性规划松弛最强，而流型公式求解速度最快，尤其适合大规模实例。
Hub location is a planning problem that involves choosing, from a set of nodes, a subset to designate as hub facilities, linking the hubs to the remaining nodes using a hub-and-spoke structure, and routing of flows on the resulting network. This paper presents theoretical and computational comparisons of the fundamental compact formulations of the p -hub location problem ( p -HLP) for three allocation strategies, namely single, multiple and r -allocation. Our theoretical results show that path-based formulations offer the strongest linear programming relaxation. The computational experiments, run on three prominent datasets using a state-of-the-art commercial solver indicate that, flow-based formulations generally solve the largest number of instances to optimality and require the shortest solution time, especially for large-scale instances.