A new formulation and branch-and-cut method for single-allocation hub location problems
提出了一个变量更少的无容量单分配枢纽选址问题整数线性规划新公式，设计了基于松弛版本的分支切割算法，在标准数据集上高效求解大规模实例。
A new compact formulation for uncapacitated single-allocation hub location problems with fewer variables than the previous Integer Linear Programming formulations in the literature is introduced. Our formulation works even with costs not based on distances and not satisfying triangle inequality. Moreover, costs can be given in aggregated or disaggregated way. Different families of valid inequalities that strengthen the formulation are developed and a branch-and-cut algorithm based on a relaxed version of the formulation is designed, whose restrictions are inserted in a cut generation procedure together with two sets of valid inequalities. The performance of the proposed methodology is tested on well-known hub location data sets and compared to the most recent and efficient exact algorithms for single-allocation hub location problems. Extensive computational results prove the efficiency of our methodology, that solves large-scale instances in very competitive times.