设施选址问题基于线性规划的近似算法研究

Facility locaiton, a central problem in combinatorial optimization, has wide applications in the operations research,computer science and inventory management. This project proposes investiagting three variants of the classical facility location problem by LP-rounding, primal-dual and dual-fitting techniques. These variants inlcude: (1)k-level facility location problem. Firstly, the project proposes using an new LP-rounding method to select cluster center to reduce the connection cost of non-cluster center, with the aim to improve the previously best approximation ratio of 3. Moreover, we also investigate an new k-level facility location model introduced by Gabor & van Ommeren. We propose adopting the dual-fitting or the primal-dual method to improve the previous best combinatorial approximation ratio of 3.27. Finally, the project will also investigate whether it is possible to apply the primal-dual method to the k-level concentrator location problem. (2)Fault-tolerant facility location problem. The project proposes designing an constant-factor combinatorial approximation algorithm for this problem. In adddition, the project also proposes improving the approximation factor for the fault-tolerant facility location problem with uniform requirements.(3) Concave facility location problem and its application. The project proposes designing a LP-rounding algorithm to reduce the best approximation factor 1.861 for the concave facility location problem.In the end, the project also investigates two games corresponding to the warehouse-retailer network design problem and the stochastic transportation-inventory network design problem and hopes to present two cross-monotonic cost share schems.

设施选址问题是组合优化领域一个重要的模型，在运筹学、计算机科学、库存管理等方面都有广泛的应用。本项目主要采用线性规划舍入、原始对偶和dual-fitting算法研究设施选址问题的三个变形。拟研究的主要内容有：1.拟采用线性规划舍入方法，设计出新的选择cluster中心的算法，降低非cluster中心顾客的连接费用，改进k-层无容量设施选址问题的近似比3;基于Gabor & van Ommeren对k-层无容量设施选址问题提出的新模型，采用dual-fitting和原始对偶技巧，改进组合算法最好的近似比3.27；采用原始对偶算法，改进k-层集中器选址问题的近似比。2.容错设施选址问题常数近似比的组合算法的设计；相同需求容错设施选址问题的近似比的改进。3.研究凹设施选址问题的线性规划舍入算法；仓库零售商网络设计博弈和随机运输库存网络设计博弈的单调费用分摊算法。

设施选址问题是组合优化领域的一个经典的NP困难问题，在运筹学、计算机科学和管理科学有广泛的应用。本项目研究基于线性规划舍入的近似算法，我们的研究内容和结果有：.(1)仓库零售商网络设计博弈： 我们对仓库零售商网络设计博弈给出了一个具有单调性、竞争性和3-近似费用恢复的费用分摊方案。我们的费用分摊方案是紧的。该算法给仓库零售商网络设计给出了开设仓库方案、以及零售商之间费用分摊方案。.(2)多层的经济批量生产博弈:我们得到了一个单调、竞争和 2β(2β + 1)--近似费用恢复的费用分摊方案，这里 β > 1是个常数。该算同时法给出了多层经济批量生产方案、各层生产商间的成本分摊方案。.(3) 带线性和次模惩罚的k层设施选址问题：当惩罚费用是线性时，我们给出了3近似算法，改进了Asadi等的近似比4；当惩罚费用是次模函数时，通过采用Wu &Xu对k层设施选址问题的双因子近似算法技巧，我们得到了3.314近似算法。.(4)带下界约束的设施选址问题: 我们推广了Guha等关于下界约束设施选址变形的双标准近似算法，考虑带有惩罚和下界约束的设施选址问题，得到了同样近似比的双标准近似算法。进一步地，我们推广这个结果到带有惩罚、软容量和下界约束的设施选址问题，得到了近似比是Guha等2倍的双标准近似算法。.(5)动态设施选址问题： 我们考虑了带次模惩罚的动态设施选址问题，推广Jain& Vazirani的算法到这个变形，给出了组合的、原始对偶3近似算法。