Jörg Kalcsics

1. The problem of identifying optimal facility locations has long been recognised as a central theme in operational research, with academic roots traceable to Alfred Weber’s seminal monograph “Über...

In the classical firefighter game, a fire breaks out on some vertices of an undirected connected graph at time zero. At each subsequent time step, a fixed number of firefighters can protect one vertex each from catching fire. Afterwards, the fire spreads from each burning vertex to every adjacent vertex that is neither burning nor defended. The game ends when the fire can no longer spread. The goal is to find a defense strategy that maximizes the number of non-burning (saved) vertices. In this work, we first revisit the classical integer linear programming formulation and then present several improvements for it, as well as two new formulations and tighter bounds on the maximum duration of the game. Moreover, we relax the classical assumptions that all vertices have uniform values and costs, i.e., we allow vertices to have different values and costs for being defended. Furthermore, instead of a fixed number of firefighters, we are given a defense budget that we can spend each time step to defend the vertices. We call this the cost-value firefighter game. We present three different integer linear programming formulations for the problem, along with a series of inequalities to strengthen the formulations and tight bounds on the maximum duration of the game.

We tackle the downgrading maximal covering location problem within a network. In this problem, two actors with conflicting objectives are involved: (a) The location planner aims to determine the location of facilities to maximize the covered demand while anticipating that an attacker will attempt to reduce coverage by increasing the length of some edges (downgrade); (b) The attacker seeks to maximize the demand initially covered by the facilities but left uncovered after the downgrade. The attacker can increase the length of certain edges within a specified budget. We introduce a mixed-integer linear bilevel program to formulate the problem, followed by a preprocessing phase and a matheuristic algorithm designed to address it. Additionally, computational results are presented to illustrate the potential and limitations of the proposed algorithm.

In this article, we study the complexity of the upgrading version of the maximal covering location problem with edge length modifications on networks. This problem is NP-hard on general networks. However, in some particular cases, we prove that this problem is solvable in polynomial time. The cases of star and path networks combined with different assumptions for the model parameters are analysed. In particular, we obtain that the problem on star networks is solvable in O(nlogn) time for uniform weights and NP-hard for non-uniform weights. On paths, the single facility problem is solvable in O(n^3) time, while the p-facility problem is NP-hard even with uniform costs and upper bounds (maximal upgrading per edge), as well as, integer parameter values. Furthermore, a pseudo-polynomial algorithm is developed for the single facility problem on trees with integer parameters.

We study the upgrading version of the maximal covering location problem with edge length modifications on networks. This problem aims at locating p facilities on the vertices (of the network) so as to maximise coverage, considering that the length of the edges can be reduced at a cost, subject to a given budget. Hence, we have to decide on: the optimal location of p facilities and the optimal edge length reductions. This problem is NP-hard on general graphs. To solve it, we propose three different mixed-integer formulations and a preprocessing phase for fixing variables and removing some of the constraints. Moreover, we strengthen the proposed formulations including valid inequalities. Finally, we compare the three formulations and their corresponding improvements by testing their performance over different datasets.

This paper addresses a version of the single-facility Maximal Covering Location Problem on a network where the demand is: (i) distributed along the edges and (ii) uncertain with only a known interval estimation. To deal with this problem, we propose a minmax regret model where the service facility can be located anywhere along the network. This problem is called Minmax Regret Maximal Covering Location Problem with demand distributed along the edges (MMR-EMCLP). Furthermore, we present two polynomial algorithms for finding the location that minimises the maximal regret assuming that the demand realisation is an unknown constant or linear function on each edge. We also include two illustrative examples as well as a computational study for the unknown constant demand case to illustrate the potential and limits of the proposed methodology.