Greedy algorithms for fair allocations and efficient assignments within facility location optimization problems


Dr. Bismark Singh
Chair of Analytics & Mixed-Integer Optimization
Department of Data Science (DDS), Department of Mathematics
Friedrich-Alexander Universität Erlangen-Nürnberg

Project Overview

Typically, within facility location problems, fairness is defined in terms of accessibility of users. However, for facilities perceived as undesirable by communities hosting them, fairness between the
usage of facilities becomes especially important. Limited research exists on this notion of fairness.

To close this gap, we develop a series of optimization models for the allocation of populations of users to facilities such that access for users is balanced with a fair utilization of facilities. The optimality conditions of the underlying non-convex quadratic models provide a precise tradeoff between accessibility and fairness. We define new classes of fairness, and a metric to quantify the extent to which fairness is achieved in both optimal and suboptimal allocations. We show a continuous relaxation of our central model is sufficient to achieve a perfect extent of fairness, while a special case reduces to the classical notion of proportional fairness.

Our work is motivated by pervasive ecological challenges faced by the waste management community as policymakers seek to reduce the number of recycling centers in the last few years. As a computational case study, applying our models on data for the state of Bavaria in Germany, we find that even after the closure of a moderate number of recycling centers, large degrees of access can be ensured provided the closures are conducted optimally. Fairness, however, is impacted more, with facilities in rural regions shouldering larger loads of visiting populations than those in urban regions.