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

As of August 2021, we are working on an optimization problem of allocating resources from different facilities to different users that seek these resources in a fair manner. We formalize the notion of fairness in our work. Specifically, we apply this problem to the state of Bavaria for positioning recycling centers (or, “Wertstoffhöfe”) in a manner that creates a proportionate amount of burdens to each of these centers (facilities) yet is accessible to large amounts of the population (users).

The underlying optimization problem is hard to solve naively requiring the use of a large computing facility. In our current experiments, we cannot even generate problem instances to accommodate all of Bavarian facilities; thus, we do not get to the stage of the solution method. To this end, we develop a simple greedy heuristic that serves as a prototype to achieve feasible solutions quickly, albeit with a loss of optimality. In this proposal, we seek to further investigate and improve on this existing prototype algorithm by leveraging the use of high performance computing facilities at the Regional Computer Centre Erlangen (RRZE).