Given a set of facilities and clients, and costs to open facilities, the classic facility location problem seeks to
open a set of facilities and assign each client to one open facility to minimize the cost of opening the chosen
facilities and the total distance of the clients to their assigned open facilities. Such an objective may induce an
unequal cost over certain socioeconomic groups of clients (i.e., total distance traveled by clients in such a
group). This is important when planning the location of socially relevant facilities such as emergency rooms.
In this work, we consider a fair version of the problem where we are given π clients groups that partition
the set of clients, and the distance of a given group is defined as the average distance of clients in the group
to their respective open facilities. The objective is to minimize the Minkowski π-norm of vector of group
distances, to penalize high access costs to open facilities across π groups of clients. This generalizes classic
facility location (π = 1) and the minimization of the maximum group distance (π = β). However, in practice,
fairness criteria may not be explicit or even known to a decision maker, and it is often unclear how to select a
specific "π" to model the cost of unfairness. To get around this, we study the notion of solution portfolios where
for a fixed problem instance, we seek a small portfolio of solutions such that for any Minkowski norm π, one
of these solutions is an π(1)-approximation. Using the geometric relationship between various π-norms, we
show the existence of a portfolio of cardinality π(log π), and a lower bound of (\sqrt{log r}).
There may not be common structure across different solutions in this portfolio, which can make planning
difficult if the notion of fairness changes over time or if the budget to open facilities is disbursed over time. For
example, small changes in π could lead to a completely different set of open facilities in the portfolio. Inspired
by this, we introduce the notion of refinement, which is a family of solutions for each π-norm satisfying a
combinatorial property. This property requires that (1) the set of facilities open for a higher π-norm must be
a subset of the facilities open for a lower π-norm, and (2) all clients assigned to an open facility for a lower
π-norm must be assigned to the same open facility for any higher π-norm. A refinement is πΌ-approximate if
the solution for each π-norm problem is an πΌ-approximation for it. We show that it is sufficient to consider
only π(log π) norms instead of all π-norms, π β [1, β] to construct refinements. A natural greedy algorithm
for the problem gives a poly(π)-approximate refinement, which we improve to poly(r^1/\sqrt{log π})-approximate
using a recursive algorithm. We improve this ratio to π(log π) for the special case of tree metric for uniform
facility open cost. Our recursive algorithm extends to other settings, including to a hierarchical facility location
problem that models facility location problems at several levels, such as public works departments and schools.
A full version of this paper can be found at https://arxiv.org/abs/2211.14873.
more »
« less
A concentration inequality for the facility location problem
We give a concentration inequality for a stochastic version of the facility location problem. We show the objective Cn = minF[0;1]2 jFj +Px2X minf2F kx τ fk is concentrated in an interval of length O(n1=6) and E[Cn] = (n2=3) if the input X consists of i.i.d. uniform points in the unit square. Our main tool is to use a geometric quantity, previously used in the design of approximation algorithms for the facility location problem, to analyze a martingale process. Many of our techniques generalize to other settings.
more »
« less
- Award ID(s):
- 2022448
- NSF-PAR ID:
- 10341767
- Date Published:
- Journal Name:
- Operations research letters
- Volume:
- 50
- Issue:
- 2
- ISSN:
- 0167-6377
- Page Range / eLocation ID:
- 213-217
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
We present a progressive approximation algorithm for the exact solution of several classes of interdiction games in which two noncooperative players (namely an attacker and a follower) interact sequentially. The follower must solve an optimization problem that has been previously perturbed by means of a series of attacking actions led by the attacker. These attacking actions aim at augmenting the cost of the decision variables of the followerβs optimization problem. The objective, from the attackerβs viewpoint, is that of choosing an attacking strategy that reduces as much as possible the quality of the optimal solution attainable by the follower. The progressive approximation mechanism consists of the iterative solution of an interdiction problem in which the attacker actions are restricted to a subset of the whole solution space and a pricing subproblem invoked with the objective of proving the optimality of the attacking strategy. This scheme is especially useful when the optimal solutions to the followerβs subproblem intersect with the decision space of the attacker only in a small number of decision variables. In such cases, the progressive approximation method can solve interdiction games otherwise intractable for classical methods. We illustrate the efficiency of our approach on the shortest path, 0-1 knapsack and facility location interdiction games. Summary of Contribution: In this article, we present a progressive approximation algorithm for the exact solution of several classes of interdiction games in which two noncooperative players (namely an attacker and a follower) interact sequentially. We exploit the discrete nature of this interdiction game to design an effective algorithmic framework that improves the performance of general-purpose solvers. Our algorithm combines elements from mathematical programming and computer science, including a metaheuristic algorithm, a binary search procedure, a cutting-planes algorithm, and supervalid inequalities. Although we illustrate our results on three specific problems (shortest path, 0-1 knapsack, and facility location), our algorithmic framework can be extended to a broader class of interdiction problems.more » « less
-
Random dimensionality reduction is a versatile tool for speeding up algorithms for high-dimensional problems. We study its application to two clustering problems: the facility location problem, and the single-linkage hierarchical clustering problem, which is equivalent to computing the minimum spanning tree. We show that if we project the input pointset π onto a random π=π(ππ)-dimensional subspace (where ππ is the doubling dimension of π), then the optimum facility location cost in the projected space approximates the original cost up to a constant factor. We show an analogous statement for minimum spanning tree, but with the dimension π having an extra loglogπ term and the approximation factor being arbitrarily close to 1. Furthermore, we extend these results to approximating solutions instead of just their costs. Lastly, we provide experimental results to validate the quality of solutions and the speedup due to the dimensionality reduction. Unlike several previous papers studying this approach in the context of π-means and π-medians, our dimension bound does not depend on the number of clusters but only on the intrinsic dimensionality of π.more » « less
-
Healthcare capacity shortage contributes to poor access in many countries. Moreover, rapid urbanization often occurring in these countries has exacerbated the imbalance between healthcare capacity and need. One way to address the above challenge is expanding the total capacity and redistributing the capacity spatially. In this research, we studied the problem of locating new hospitals in a two-tier outpatient care system comprising multiple central and district hospitals, and upgrading existing district hospitals to central hospitals. We formulated the problem with a discrete location optimization model. To parameterize the optimization model, we used a multinomial logit model to characterize individual patientsβ diverse hospital choice and to quantify the patient arrival rates at each hospital accordingly. To solve the hard nonlinear combinatorial optimization problem, we developed a queueing network model to approximate the impact of hospital locations on patient flows. We then proposed a multi-fidelity optimization approach, which involves both the aforementioned queuing network model as a surrogate and a self-developed stochastic simulation as the high-fidelity model. With a real-world case study of Shanghai, we demonstrated the changes in the care network and examined the impacts on the network design by population center emergence, governmental budget change and considering patients with different age groups or income levels. Note to Practitioners βOur work focuses on improving system-wide care access in a two-tier care network. We believe that our work can lead to effective development of a location analytics tool for city-wide healthcare system planners. We also think the importance of this study is further strengthened by the case studies based on real-world hospital choice experimental data from Shanghai, China, a region suffering from the imbalance between healthcare capacity and need. Our case studies are expected to make recommendations on care facility expansion and dispersion to better align with the spatial distribution of residential communities and patient hospital choice behavior.more » « less
-
Label-efficient and reliable semantic segmentation is essential for many real-life applications, especially for industrial settings with high visual diversity, such as waste sorting. In industrial waste sorting, one of the biggest challenges is the extreme diversity of the input stream depending on factors like the location of the sorting facility, the equipment available in the facility, and the time of year, all of which significantly impact the composition and visual appearance of the waste stream. These changes in the data are called βvisual domainsβ, and label-efficient adaptation of models to such domains is needed for successful semantic segmentation of industrial waste. To test the abilities of computer vision models on this task, we present the \emph{VisDA 2022 Challenge on Domain Adaptation for Industrial Waste Sorting}. Our challenge incorporates a fully-annotated waste sorting dataset, ZeroWaste, collected from two real material recovery facilities in different locations and seasons, as well as a novel procedurally generated synthetic waste sorting dataset, SynthWaste. In this competition, we aim to answer two questions: 1) can we leverage domain adaptation techniques to minimize the domain gap? and 2) can synthetic data augmentation improve performance on this task and help adapt to changing data distributions? The results of the competition show that industrial waste detection poses a real domain adaptation problem, that domain generalization techniques such as augmentations, ensembling, etc., improve the overall performance on the unlabeled target domain examples, and that leveraging synthetic data effectively remains an open problem. See https://ai.bu.edu/visda-2022/.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Journal Article:
- https://doi.org/10.1016/j.orl.2022.01.009
