Marta Baldomero-Naranjo

This paper presents the Multi-type Maximal Covering Location Problem with upgrading, a novel problem that integrates a network-continuous multi-type facility location problem, incorporating both facility and infrastructure upgrades. Specifically, the problem considers the superposition of two solution spaces: a network space, where a subset of customers is located on the nodes, and a continuous space, where other customers are located. The problem involves locating two types of facilities: p-discrete facilities at the nodes of the network and q-continuous facilities within the continuous space, with the objective of maximizing the covered demand. Network customers can be served by any of the types of facilities, and continuous space customers have to be served by continuous facilities. The paper presents two types of upgrades: edge upgrading, which reduces edge lengths for a fee, and facility upgrading, which increases the coverage radius of continuous facilities. These two types of upgrades are subject to a common budget.This research is the first attempt to address upgrades within a network-continuous multi-type covering context. A non-linear formulation with a Mixed Integer Second Order Cone (MISOCO) reformulation and two integer linear formulations for the Euclidean planar case are proposed to model this problem. Moreover, a set of valid inequalities is proposed to strengthen these formulations. A comprehensive computational analysis is undertaken to test the effectiveness of the proposed improvements.

This work addresses the Covering Tour Problem with Path Upgrades (CTP-PU), a routing problem where a tour must be designed to cover all nodes in a given graph, while selected arcs can be upgraded within a budget to extend coverage through shortest paths. The problem generalizes classical covering-tour variants introducing operational upgrades decisions, making it computationally challenging.To solve the CTP-PU, we propose a novel matheuristic approach that integrates data science and machine learning techniques with combinatorial optimization methods. First, node-level features are extracted to describe structural and operational properties. Then, a classifier predicts whether each node belongs to the tour or is covered. These predictions are used to fix variables in a reduced MILP model, which is solved iteratively to guarantee feasibility and improve the solution. Random Forest and Naive Bayes classifiers are trained on optimal solutions of small instances and tested on medium- and large-scale cases.Computational experiments on three different sets of instances with up to 101 nodes show that the proposed method achieves solution quality very close to the model, while drastically reducing the computation running time. The approach proves robust across different instance types and parameter settings, confirming its ability to generalize to new and larger instances.

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.

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.

This paper proposes a robust classification model, based on support vector machine (SVM), which simultaneously deals with outliers detection and feature selection. The classifier is built considering the ramp loss margin error and it includes a budget constraint to limit the number of selected features. The search of this classifier is modeled using a mixed-integer formulation with big M parameters. Two different approaches (exact and heuristic) are proposed to solve the model. The heuristic approach is validated by comparing the quality of the solutions provided by this approach with the exact approach. In addition, the classifiers obtained with the heuristic method are tested and compared with existing SVM-based models to demonstrate their efficiency.