Approximation and Heuristic Algorithms for the Priority Facility Location Problem with Outliers

Hang Luo; Lu Han; Tianping Shuai; Fengmin Wang

doi:10.26599/TST.2023.9010152

| Sign up

PDF (2.6 MB)

Cite

EndNote(RIS) BibTeX

Collect

Submit Manuscript

Show Outline

Figures (3)

Fig. 1

Fig. 2

Fig. 3

Tables (5)

Table 1

Table 2

Table 3

Table 4

Table 5

Open Access

Approximation and Heuristic Algorithms for the Priority Facility Location Problem with Outliers

Hang Luo^¹, Lu Han^²(), Tianping Shuai^², Fengmin Wang^³

1International School, Beijing University of Posts and Telecommunications, Beijing 100876, China

2School of Science, Beijing University of Posts and Telecommunications, Beijing 100876, China

3Beijing Jinghang Research Institute of Computing and Communication, Beijing 100074, China

Show Author Information

Abstract

In this paper, we propose the Priority Facility Location Problem with Outliers (PFLPO), which is a generalization of both the Facility Location Problem with Outliers (FLPO) and Priority Facility Location Problem (PFLP). As our main contribution, we use the technique of primal-dual to provide a 3-approximation algorithm for the PFLPO. We also give two heuristic algorithms. One of them is a greedy-based algorithm and the other is a local search algorithm. Moreover, we compare the experimental results of all the proposed algorithms in order to illustrate their performance.

Keywords

priority facility location primal-dual approximation algorithm

References

[1]

P. B. Mirchandani and R. L. Francis, Discrete location theory. New York, NY, USA: John Wiley & Sons, 1990.

[2]

D. B. Shmoys, E. Tardos, and K. Aardal, Approximation algorithms for facility location problems, in Proc. of the 29th Annual ACM Symposium on Theory of Computing, El Paso, TX, USA, 1997, pp. 265–274.

Crossref

[3]

S. Li, A 1.488 approximation algorithm for the uncapacitated facility location problem, Inf. Comput., vol. 222, pp. 45–58, 2013.

Crossref

[4]

M. Sviridenko, An improved approximation algorithm for the metric uncapacitated facility location problem, in Proc. of the 9th Int. Conf. on Integer Programming and Combinatorial Optimization, Copenhagen, Denmark, 2002. pp. 240–257,

Crossref

[5]

J. Byrka and K. Aardal, An optimal bifactor approximation algorithm for the metric uncapacitated facility location problem, SIAM J. Comput., vol. 39, no. 6, pp. 2212–2231, 2010.

Crossref Google Scholar

[6]

F. A. Chudak and D. B. Shmoys, Improved approximation algorithms for the uncapacitated facility location problem, SIAM J. Comput., vol. 33, no. 1, pp. 1–25, 2003.

Crossref Google Scholar

[7]

K. Jain and V. V. Vazirani, Approximation algorithms for metric facility location and k-Median problems using the primal-dual schema and Lagrangian relaxation, J. ACM, vol. 48, no. 2, pp. 274–296, 2001.

Crossref Google Scholar

[8]

K. Jain, M. Mahdian, E. Markakis, A. Saberi, and V. V. Vazirani, Greedy facility location algorithms analyzed using dual fitting with factor-revealing LP, J. ACM, vol. 50, no. 6, pp. 795–824, 2003.

Crossref Google Scholar

[9]

K. Jain, M. Mahdian, and A. Saberi, A new greedyapproach for facility location problems, in Proc. of the 34th Annual ACM Symposium on Theory of Computing, Montréal, Canada, 2002, pp. 731–740.

Crossref

[10]

M. Mahdian, Y. Ye, and J. Zhang, Improved approximation algorithms for metric facility location problems, in Proc. of 5th International Workshop, APPROX 2002, Rome, Italy, 2002, pp. 229–242.

Crossref

[11]

V. Arya, N. Garg, R. Khandekar, A. Meyerson, and K. Munagala, Local search heuristic for k-median andfacility location problems, in Proc. of the 33th Annual ACM Symposium on Theory of Computing, Heraklion, Greece, 2001, pp. 21–29.

Crossref

[12]

M. R. Korupolu, C. G. Plaxton, and R. Rajaraman, Analysis of a local search heuristic for facility location problems, J. Algoritms., vol. 37, no. 1, pp. 146–188, 2000.

Crossref Google Scholar

[13]

M. Charikar, S. Khuller, D. M. Mount, and G. Narasimhan, Algorithms for facility location problems with outliers, in Proc. of the 12th Annual ACM-SIAM Symposium on Discrete Algorithms, Washington, DC, USA, 2001, pp. 642–651.

[14]

R. Ravi and A. Sinha, Multicommodity facility location, in Proc. of the 15th Annual ACM-SIAM Symposium on Discrete Algorithms, New Orleans, LA, USA, 2004, pp. 342–349.

[15]

M. Mahdian, Facility location and the analysis of algorithms through factor-revealing programs, PhD dissertation, Massachusetts Institute of Technology, Cambridge, MA, USA, 2004.

[16]

G. Li, Z. Wang, and C. Wu, Approximation algorithms for the stochastic priority facility location problem, Optimization, vol. 62, no. 7, pp. 919–928, 2013.

Crossref Google Scholar

[17]

F. Wang, D. Xu, and C. Wu, Approximation algorithms for the priority facility location problem with penalties, J. Syst. Sci. Complex., vol. 28, no. 5, pp. 1102–1114, 2015.

Crossref Google Scholar

Tsinghua Science and Technology

Volume 29 Issue 6,
December 2024

Pages 1694-1702

DOI: 10.26599/TST.2023.9010152

Cite this article:

Luo H, Han L, Shuai T, et al. Approximation and Heuristic Algorithms for the Priority Facility Location Problem with Outliers. Tsinghua Science and Technology, 2024, 29(6): 1694-1702. https://doi.org/10.26599/TST.2023.9010152

Return

Table 1

Algorithm 1　Pre-construction phase
Input: A given PFLPO instance $I_{P F O}$ .
Output: A modified PFLPO instance $I_{P F O}^{e x p}$ .
Step 1: Guess the most expensive opened facility $(i_{e}, s_{e})$ in an optimal solution of the given PFLPO instance, $I_{P F O} = (F, C, {f_{i s}}_{(i, s) \in F}, {c_{i j}}_{i \in F, j \in C})$ , where $F := {(i, s) : i \in F, s \in L}$ , and $C := {(j, l) : j \in C, l \in L}$ .
Step 2: For each facility $(i, s) \in F$ , we define
$f_{i s}^{'} := {\begin{cases} 0, i f f a c i l i t y (i, s) = (i_{e}, s_{e}); \\ \infty, i f f a c i l i t y (i, s) s a t i s f i e s f_{i s} > f_{i_{e} s_{e}}; \\ f_{i s}, o t h e r w i s e . \end{cases}$
Construct the modified PFLPO as $I_{P F O}^{e x p} = (F, D, {f_{i s}^{'}}_{(i, s) \in F}, {c_{i j}}_{i \in F, j \in C})$ .
Step 3: Output modified PFLPO instance $I_{P F O}^{e x p}$ .

Table 2

Algorithm 2　Dual construction phase
Input: Modified PFLPO instance $I_{P F O}^{e x p}$ .
Output: A dual feasible solution of the dual program of the modified PFLPO instance $I_{P F O}^{e x p}$ and some useful sets.
Step 1: Initialization.
For any client $(j, l) \in C$ , set $α_{j l} := 0$ . For any facility $(i, s) \in F$ , client $(j, l) \in C$ , set $β_{i s, j l} := 0$ , $γ := 0$ . $F_{t e m} := \emptyset$ , $C_{t e m} := \emptyset$ , $O_{t e m} := C$ , and $t := 0$ . For any facility $(i, s) \in F$ , set $t_{i s} := \infty$ . Construct a dummy facility $(i_{d}, s_{d})$ . For any client $(j, l) \in C$ , set $w (j, l) := (i_{d}, s_{d})$ .
Step 2: Dual ascent process.
while $\| O_{t e m} \| > q$ do
Raise $t$ as well as each dual variable $α_{j l}$ satisfying $(j, l) \in O_{t e m}$ uniformly until some of the following events happens. If several events happen at the same time, we arbitrarily break ties.
Event 1. There exist some facility $(i, s) \in F ∖ F_{t e m}$ and client $(j, l) \in O_{t e m}$ , such that
$l ⩽ s a n d α_{j l} = c_{i j} .$
Event 2. There exist some facility $(i, s) \in F_{t e m}$ and client $(j, l) \in O_{t e m}$ , such that
$l ⩽ s a n d α_{j l} = c_{i j} .$
Event 3. There exists some facility $(i, s) \in F ∖ F_{t e m}$ , such that
$\sum_{(j, l) \in C} β_{i s, j l} = f_{i s}^{'} .$
If Event 1 happens, update $β_{i s, j l} := α_{j l} - c_{i j}$ . Raise $β_{i s, j l}$ uniformly as $α_{j l}$ increases. If Event 2 happens, stop raise $α_{j l}$ . Update $C_{t e m} := C_{t e m} \cup {(j, l)}$ , and $O_{t e m} := O_{t e m} ∖ {(j,$ $l)}$ . Update $w (j, l) := (i, s)$ . If Event 3 happens, stop raise $α_{j l}$ for each client $(j, l) \in O_{t e m}$ satisfying $β_{i s, j l} > 0$ . Define $C_{(i, s)} := {(j, l) \in O_{t e m} : β_{i s, j l} > 0} .$ Update $F_{t e m} :=$ $F_{t e m} \cup {(i, s)}$ , $C_{t e m} := C_{t e m} \cup C_{(i, s)}$ , and $O_{t e m} := O_{t e m} ∖$ $C_{(i, s)} .$ Update $t_{i s} := t$ and $w (j, l) := (i, s)$ for each client $(j, l) \in C_{(i, s)}$ .
Stop raise $t$ as well as each dual variable $α_{j l}$ satisfying $(j, l) \in$ $O_{t e m}$ , and update $γ := t$ .
Step 3: Output dual variables ${α_{j l}}_{(j, l) \in C}$ , ${β_{i s, j l}}_{(i, s) \in F, (j, l) \in C}$ and $γ$ . Set $F_{t e m}$ , $C_{t e m}$ , and $O_{t e m}$ .

Table 3

Algorithm 3　Primal construction phase
Input: A dual feasible solution of the dual program of $I_{P F O}^{e x p}$ and sets $F_{t e m}$ , $C_{t e m}$ , and $O_{t e m}$ obtained from Algorithm 2.
Output: A primal feasible solution of the integer program of the given PFLPO instance $I_{P F O}$ .
Step 1: Initialization.
For any facility $(i, s) \in F$ , client $(j, l) \in C$ , set $x_{i s, j l} := 0$ . For any facility $(i, s) \in F$ , set $y_{i s} := 0$ . For any client $(j, l) \in C$ , set $z_{j l} := 0$ . Denote by $(i_{l a}, s_{l a})$ the last facility to be added to $F_{t e m}$ (i.e., the last temporarily opened facility).
Step 2: Determine outliers.
If $\| O_{t e m} \| = q$ , set $O_{f i n} := O_{t e m}$ . For each client $(j, l) \in O_{f i n}$ , update $z_{j l} := 1$ . If $\| O_{t e m} \| < q$ , arbitrarily select $q - \| O_{t e m} \|$ clients in $C_{(i_{l a}, s_{l a})}$ , and denote by $O_{l a}$ these selected clients. Set $C_{f i n} := C_{t e m} ∖ O_{l a}$ , and $O_{f i n} := O_{t e m} \cup O_{l a}$ . For each client $(j, l) \in O_{f i n}$ , update $z_{j l} := 1$ .
Step 3: Open facilities.
Set $F_{f i n} := \emptyset$ . For each facility $(i, s) \in F$ , define
$N_{(i, s)} := {(j, l) \in C : β_{i s, j l} > 0} .$
According to the opening levels of the facilities in $F_{t e m}$ , order the facilities from the one with largest level to the one with smallest level. Set $k := 1$ .
while $k ⩽ \| F_{t e m} \|$ do
For the $k -$ th facility $(i, s)$ in $F_{t e m}$ , check whether there exists some facility $(i^{'}, s^{'})$ in $F_{f i n}$ , such that
$N_{(i, s)} \cap N_{(i^{'}, s^{'})} \neq \emptyset .$
If there exists such facility, update $k := k + 1$ . Otherwise, update $F_{f i n} := F_{f i n} \cup {(i, s)}$ , and $y_{i s} := 1$ , and $k := k + 1$ .
Step 4: Connect clients.
For each client $(j, l) \in C_{f i n}$ , find facility
$(i, s) := \arg min_{(i^{'}, s^{'}) \in F_{f i n} : l ⩽ s^{'}} c_{i^{'} j},$
set $σ (j, l) := (i, s)$ , and update $x_{i s, j l} := 1$ .
Step 5: Output primal variables ${x_{i s, j l}}_{(i, s) \in F, (j, l) \in C}$ , ${y_{i s}}_{(i, s) \in F}$ , and ${z_{j l}}_{(j, l) \in C}$ .

Table 4

Algorithm 4　Greedy-based algorithm
Input: A given PFLPO instance $I_{P F O}$ .
Output: A primal feasible solution of the integer program of the given PFLPO instance $I_{P F O}$ .
Step 1: Initialization.
For any facility $(i, s) \in F$ , client $(j, l) \in C$ , set $x_{i s, j l}^{g b} := 0$ . For any facility $(i, s) \in F$ , set $y_{i s}^{g b} := 0$ . For any client $(j, l) \in C$ , set $z_{j l}^{g b} := 0$ . Set $F_{g b} := \emptyset$ , $C_{g b} := \emptyset$ , and $O_{g b} := C$ . Construct a dummy facility $(i_{d}, s_{d})$ , where $s_{d} = L$ . Set $c_{i_{d} j} := \infty$ for each client $(j, l) \in C$ . For each facility set $F^{'} \subseteq F$ , and client $(j, l) \in C$ , define
$(i_{(F^{'}, j)}, s_{(F^{'}, j)}) := \arg min_{(i, s) \in F^{'} \cup {(i_{d}, s_{d})} : l ⩽ s} c_{i j},$
and $τ (F^{'}, j)$ is the location of the facility $(i_{(F^{'}, j)}, s_{(F^{'}, j)})$ , i.e., $τ (F^{'}, j) := i_{(F^{'}, j)}$ . For each facility set $F^{'} \subseteq F$ , define
$T (F^{'}) := \sum_{(i, s) \in F^{'}} f_{i s} + \sum_{(j, l) \in C_{F^{'}}^{m i n}} c_{τ (F^{'}, j) j},$
where $C_{F^{'}}^{m i n}$ are the first $n - q$ clients in $C$ with the smallest connection cost of $c_{τ (F^{'}, j) j}$ .
Step 2: Open facilities.
Step 2.1: Find facility
$(i_{g b}, s_{g b}) := \arg min_{(i, s) \in F : s = L} T ({(i, s)}) .$
Update $F_{g b} := F_{g b} \cup {(i_{g b}, s_{g b})}$ .
Step 2.2: For each facility $(i, s) \in F ∖ F_{g b}$ , define
$G a i n (i, s) := T (F_{g b}) - T (F_{g b} \cup {(i, s)}) .$
Find the facility
$(i_{h}, s_{h}) := \arg max_{(i, s) \in F ∖ F_{g b}} \frac{G a i n (i, s)}{f_{i s}} .$
If $G a i n (i_{h}, s_{h}) > 0$ , update $F_{g b} := F_{g b} \cup {(i_{h}, s_{h})}$ , and repeat Step 2.2. Otherwise, update $y_{i s}^{g b} := 1$ for each facility $(i, s) \in F_{g b}$ , and go to Step 3.
Step 3: Determine outliers.
Update $O_{g b} := C ∖ C_{F_{g b}}^{m i n}$ , where $C_{F_{g b}}^{m i n}$ are the first $n - q$ clients in $C$ with the smallest connection cost of $c_{τ (F_{g b}, j) j}$ . For each client $(j, l) \in O_{g b}$ , update $z_{j l}^{g b} := 1$ .
Step 4: Connect clients.
Update $C_{g b} := C_{F_{g b}}^{m i n}$ . For each client $(j, l) \in C_{g b}$ , find facility
$(i, s) := \arg min_{(i^{'}, s^{'}) \in F_{g b} : l ⩽ s^{'}} c_{i^{'} j},$
set $σ_{g b} (j, l) := (i, s)$ , and update $x_{i s, j l}^{g b} := 1$ .
Step 5: Output primal variables ${x_{i s, j l}^{g b}}_{(i, s) \in F, (j, l) \in C}$ , ${y_{i s}^{g b}}_{(i, s) \in F}$ , and ${z_{j l}^{g b}}_{(j, l) \in C}$ .

Table 5

Algorithm 5　Local search algorithm
Input: A given PFLPO instance $I_{P F O}$ .
Output: A primal feasible solution of the integer program of the given PFLPO instance $I_{P F O}$ .
Step 1 Initialization.
For any facility $(i, s) \in F$ , client $(j, l) \in C$ , set $x_{i s, j l}^{l s} := 0$ . For any facility $(i, s) \in F$ , set $y_{l s}^{g b} := 0$ . For any client $(j, l) \in C$ , set $z_{j l}^{l s} := 0$ . Set $F_{l s} := \emptyset$ , $C_{l s} := \emptyset$ , and $O_{l s} := C$ . Construct a dummy facility $(i_{d}, s_{d})$ , where $s_{d} = L$ . Set $c_{i_{d} j} := \infty$ for each client $(j, l) \in C$ . For each facility set $F^{'} \subseteq F$ , and client $(j, l) \in C$ , define
$(i_{(F^{'}, j)}, s_{(F^{'}, j)}) := \arg min_{(i, s) \in F^{'} \cup {(i_{d}, s_{d})} : l ⩽ s} c_{i j},$
and $τ (F^{'}, j)$ is the location of the facility $(i_{(F^{'}, j)}, s_{(F^{'}, j)})$ , i.e., $τ (F^{'}, j) := i_{(F^{'}, j)}$ . For each facility set $F^{'} \subseteq F$ , define
$T (F^{'}) := \sum_{(i, s) \in F^{'}} f_{i s} + \sum_{(j, l) \in C_{F^{'}}^{m i n}} c_{τ (F^{'}, j) j},$
where $C_{F^{'}}^{m i n}$ are the first $n - q$ clients in $C$ with the smallest connection cost of $c_{τ (F^{'}, j) j}$ .
Step 2: Open facilities.
Step 2.1: Find facility
$(i_{l s}, s_{l s}) := \arg min_{(i, s) \in F : s = L} T ({(i, s)}) .$
Update $F_{l s} := F_{l s} \cup {(i_{l s}, s_{l s})}$ .
Step 2.2: For facility set $F_{l s}$ , define
$\begin{array}{l} N (F_{l s}) := \\ {F_{l s} \cup {(i, s)} : (i, s) \in F ∖ F_{l s}} ⋃ \\ {F_{l s} ∖ {(i, s)} : (i, s) \in F_{l s}, F_{l s} ∖ {(i, s)} \\ c a n b e c o n n e c t e d b y a t l e a s t n - q c l i e n t s} ⋃ \\ {F_{l s} ∖ {(i, s)} \cup {(i^{'}, s^{'})} : (i, s) \in F_{l s}, \\ (i^{'}, s^{'}) \in F ∖ F_{l s}, F_{l s} ∖ {(i, s)} \cup {(i^{'}, s^{'})} \\ c a n b e c o n n e c t e d b y a t l e a s t n - q c l i e n t s} \end{array}$
If there exists some facility set $F^{'} \in N (F_{l s})$ satisfying $T (F^{'}) < T (F)$ , update $F_{l s} := F^{'}$ and repeat Step 2.2. Otherwise, update $y_{i s}^{l s} := 1$ for each facility $(i, s) \in F_{l s}$ , and go to Step 3.
Step 3: Determine outliers.
Update $O_{l s} := C ∖ C_{F_{l s}}^{m i n}$ , where $C_{F_{l s}}^{m i n}$ are the first $n - q$ clients in $C$ with the smallest connection cost of $c_{τ (F_{l s}, j) j}$ . For each client $(j, l) \in O_{l s}$ , update $z_{j l}^{l s} := 1$ .
Step 4: Connect clients.
Update $C_{l s} := C_{F_{l s}}^{m i n}$ . For each client $(j, l) \in C_{l s}$ , find facility
$(i, s) := \arg min_{(i^{'}, s^{'}) \in F_{l s} : l ⩽ s^{'}} c_{i^{'} j},$
set $σ_{l s} (j, l) := (i, s)$ , and update $x_{i s, j l}^{l s} := 1$ .
Step 5: Output primal variables ${x_{i s, j l}^{l s}}_{(i, s) \in F, (j, l) \in C}$ , ${y_{i s}^{l s}}_{(i, s) \in F}$ , and ${z_{j l}^{l s}}_{(j, l) \in C}$ .