Efficient solvable variants of location problems

The proposed project deals with efficiently solvable variants of location problems. The project splits up into the following three subareas: semi-obnoxious location problems, inverse location problems and location problems with budget constraints. In all areas our main focus will lie on the development of efficient algorithms for the solution of the considered location problems. In classical location problems, each client wishes to have its closest facility as near to itself as possible. In semi- obnoxious facility location problems, we treat the case of facilities for which closeness is desirable only for some clients while other clients prefer the facilities to be as far away as possible. Inverse location problems deal with modifying a set of input parameters at minimum cost such that a given feasible solution of the underlying location problem becomes optimal. The third subarea is concerned with three classes of location problems with budget constraints. Given a limited budget and a set of input parameters of the location problem that can be changed, the goal in improvement problems is to change the parameters within the given budget in such a way so as to improve the quality of an already given solution or of a new optimal solution of the location problem under investigation as much as possible. There also exist variants where the aim is to degrade the quality instead of improving it.

Location problems belong to the most basic problems in operations research and play an important role in practice. In location problems we are given a set of facilities and a set of clients. The task is to place the facilities such that the clients are served in the optimal way and such that the resulting costs, which typically depend on the distances between clients and the facilities from which they are served, are minimized. The main goal of this project was to obtain a better understanding of variants of location problems in which some of the input data can be changed within certain limits. Our research focused on the following two classes of location problems: Inverse location problems: A feasible solution for the considered location problem is given and the goal is to change some of the input data in minimal way such that the given solution becomes an optimal solution. Location problems with budget constraints: A limited budget is available that can be invested to change some of the input parameters with the aim to change the quality of the resulting optimal solution as much as possible. The improvement case is referred to as upgrading and the deterioration case as downgrading. Within this project we proved several variants of location problems to be hard to solve from the computational point of view and identified structures which turn hard cases into efficiently solvable ones. We derived new problem-specific optimality criteria for a variety of location problems that allowed us to derive fast algorithms for their solution.