On the Bounded Fault-Tolerant Facility Placement Problem

摘要

In the bounded fault-tolerant facility placement problem, we are given a set of sites, a set of clients, and distances between clients and sites. At each site, one may open an unlimited number of facilities with the same opening cost for each facility. Each client should be connected to different facilities to satisfy its request. The task is to first determine the number of facilities that are to be opened in which sites, and then to connect each client to different facilities with the required number. The distance from any client to each site that provides facilities to be connected should not be more than a given bound. The goal is to minimize the opening cost for facilities at the sites plus the service cost for connecting clients to facilities. We first formulate this problem into an integer programming model; then, by relaxing the integer decision variables constraints, we obtain its corresponding linear programming formulation and dual linear programming formulation. Based on the solutions of its corresponding linear programming formulation and dual linear programming formulation, we propose an LP-rounding heuristic algorithm to solve the bounded fault-tolerant facility placement problem. Finally, we use a numerical example to show the solution procedure and evaluate its performance ratio.