无容量限制设施选址问题是经典的组合优化问题, 具有广泛的应用价值,然而该问题已被证明是NP难问题, 并且传统的分支定界方法求解速度较慢.研究以最大化总收益费用与总投建费用之差为目标的无容量限制设施选址问题,将其转化为节点包装问题,并根据模型的图形特点提出了新的合法不等式族------轴不等式族,经过严格的数学证明后得出轴不等式要强于原有的奇洞不等式. 同时,设计出切割不等式快速搜索算法嵌入到分支割平面方法中. 最后,通过实验验证了轴不等式族的强有效性,
以及分支割平面方法比分支定界方法求解速度快、节点数量少的优点.

The uncapacitated facility location problem is a classic combinatorial optimization problem with wide applications. However, this problem had been proven to be NP-hard and the traditional solving method based on branch-and-bound is slow. In this paper, we studies a class of UFLP problem aiming at maximizing the gap between total income and total investment cost, we transform this problem into a node packing problem and propose a new family of valid inequalities-axis inequalities based on graphic features of the model, which are stronger than the odd-hole inequalities after a strict proof. We also design a fast searching algorithm for cut inequalities and embed it in the branch-and-cut method. In the end, strong validity of axis inequalities are validated by experiments. The experimental results also showed that compared with the branch-and-bound method, the branch-and-cut method can reduce the number of branch nodes as
well as speed up the solving process.