Operations Research Transactions ›› 2013, Vol. 17 ›› Issue (2): 1-9.

• Original Articles •     Next Articles

Facility location problem with submodular penalties and stochastic demands

WANG Xing1, XU Dachuan2,*   

  1. 1. School of Science, Hangzhou Dianzi University, Hangzhou 310018, China 2. Department of Applied Mathematics, Beijing University of Technology, Beijing 100124, China
  • Received:2012-05-10 Online:2013-06-15 Published:2013-06-15
  • Supported by:

    北京市教育委员会科技计划面上项目 (No. KM201210005033)

Abstract: In this paper, we consider the facility location problem with submodular penalties and stochastic demands. The objective is to open a subset of facilities,  to connect a subset of clients to open facilities, and  to penalize the remaining  clients such that the total cost of opening cost, connection cost, inventory cost, handling cost and penalty cost is minimized. Based on the special structure of the problem, we propose a primal-dual 3-approximation algorithm. In the algorithm, we construct a dual feasible solution in the first step followed by constructing the corresponding  primal integer feasible solution in the second step. This  primal integer feasible solution indicates the final opening facility set and penalty client set. We prove that the proposed algorithm can be implemented in polynomial time and the cost of the incurred primal integer feasible solution is no more than 3 times of the optimal value.

Key words: submodular penalties, stochastic demands, approximation algorithm, primal-dual algorithm

CLC Number: