带容量的设施选址问题及其变形的近似算法研究

As a clustering problem, facility location is one of the classic problems in operations research and theoretical computer science, in which the capacitated facility location depicts actual background better. In view of the cardinality constraint for open facilities, the requirement for the upper and lower bound of facility capacity and the fact that facility cost is whether included in objective function, several cases for facility location are investigated, such as dynamic facility location, k-facility location and k-median etc. According to the latest research for these problems, many methods are adapted to design approximation algorithm to solve them, which are primal-dual scheme, local search and rounding for linear programming etc. These algorithms are performed under the condition that some constraint (the capacity for facility or the cardinality for open facility) is violated or not. The settlement for this project can not only enrich theory of combinatorial optimization, but also provide theoretical results and research methods for k-means, k-center and some other discrete clustering problems. At the meanwhile, by the analogy for problems and methods, the research results and techniques for this project can provide ideas for continuous clustering problems. Therefore, the theory for machine learning can be used for mutual reference, so as to get high quality results.

设施选址作为聚类问题，是运筹学和理论计算机科学的经典问题之一，其中带有容量的设施选址问题刻画实际情况更为贴切。本项目从开设设施基数的限制、设施容量上下界的要求、目标函数是否存在设施费用等多角度讨论了动态设施选址、k-设施选址以及k-中位等问题的近似算法。根据具体问题目前的研究进展，在约束条件(设施容量或者开设设施基数)被违反或者不被违反的情况下，采用原始对偶、局部搜索、线性规划舍入等技巧设计近似算法。项目中问题的解决不仅能够丰富组合最优化的理论，而且为k-平均和k-中心等其他离散聚类问题的解决提供了相应的理论结果和研究方法。同时通过问题的类比和方法的借鉴，该项目的研究结果和技巧也可以为连续型聚类问题的解决提供思路，从而使得机器学习领域的理论相互借鉴，得到高质量的结果。

设施选址问题一直是组合优化领域的热点问题之一，在仓库选择，供应链管理中有很多的应用。它是指在给定的若干位置中选择一些来建立设施使得所有的顾客的需求得到满足，并且总费用最少。现实中很多时候为了服务的合理化和人性化，会限制设施链连接的顾客数量，这样就衍生出设施选址问题的一个重要的变形——带容量的设施选址问题。本项目围绕带容量的设施选址问题中具有重要意义的NP-难问题，从近似算法的角度进行分析和研究。研究的主要问题包括设施选址问题、次模问题以及非次模问题等，取得了很好的研究成果。为了使研究方法具有新颖性和开放性，研究过程中不同问题的算法和技巧被充分调用和融合，使得研究思路创新性增强，并为后续的组合问题研究提供了启发和引导。在本项目支持下共发表期刊论文8篇，会议论文1篇。.设施选址方面，由于设施连接顾客的数量使有容量限制的，所以如果距离设施近的顾客没有被连接上的话，就要支付惩罚的费用。针对于此，项目考查了带有惩罚的k-层设施选址费用分摊博弈的问题，给出合理的近似算法得到较好的近似比。由于设施容量的限制，现实中会将设施和顾客根据时间的节点出现，动态设施选址问题应运而生。本项目关于平方度量距离空间中的动态设施选址问题进行了深入的研究，得到9-近似算法，再利用组合技巧得到更高的2.606-近似算法，顺应现实应用背景。.设施选址的极大化问题属于目前学术界和业界都很活跃的次模问题，为了更好的研究带有容量的设施选址问题，项目中研究了大规模数据情况下近似鲁棒平行次模极大化问题，通过数值实验证明的理论结果的有优良性。.极小设施选址问题属于非次模优化问题，因此，带有容量限制的非次模问题的研究能够为带有容量约束的设施选址问题提供更广阔的研究思路。项目中研究了d-维背包约束下的非次模流算法、单调非次模函数比值的极小化问题、带有基数约束的双准则流算法等等问题。