On the Bounded Fault-Tolerant Facility Placement Problem

SYNOPTIC ABSTRACT

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.

KEY WORDS AND PHRASES:

• Bounded fault-tolerant facility placement problem
• integer programming
• linear programming
• LP-rounding heuristic algorithm

Additional information

Funding

This research was supported by the Humanities and Social Sciences Planning Foundation of the Ministry of Education in China (Grant No. 18YJA630077), the Ningbo Natural Science Foundation (Grant No. 2018A610198) and K.C. Wong Magna Fund in Ningbo University.