Francesco Carrabs
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Francesco Carrabs has a total of 50 co-authors. Here are the top co-authors by number of shared publications:
- Raffaele Cerulli
Department of Mathematics University of Salerno Fisciano Salerno Italy
26 shared publications Raffaele Cerulli
12 shared publications- Andrea Raiconi
Istituto per le Applicazioni del Calcolo “Mauro Picone” (Naples Unit), National Research Council, Via Pietro Castellino 111, 80131 Naples, Italy
10 shared publications - Ciriaco D'Ambrosio
University of Salerno
10 shared publications - Carmine Cerrone
Department of Economics and Business Studies, University of Genova, 16126 Genova, Italy
7 shared publications - Federica Laureana
Department of Mathematics University of Salerno, Italy
5 shared publications
Latest Publications
- Open Access
On the Complexity of the Paper Selection Problem for the Italian Research Quality Evaluation (VQR)
This work addresses the paper selection problem that each Italian university and department faced in the context of the research quality evaluation (VQR) of the Italian university system for the period 2020–2024. Given the set of researchers of a university and their associated papers, the problem consists of selecting a fixed number of researcher, paper pairs, as established by the Ministry, while respecting bounds on the minimum and maximum number of papers selectable for each researcher, as well as the maximum number of times a paper can be selected. Each pair is associated with a score, which depends on several bibliometric parameters related to both the paper and the author, and the goal of the problem is to select the pairs so as to maximize the total score. In this paper, we consider two versions of the problem, modeling the departments' and the university's perspectives, and for each of them, we provide an integer linear programming formulation. Moreover, we present two proofs showing that the problem can be solved optimally in polynomial time. The first proof consists of a polynomial‐time reduction to the capacitated minimum cost flow problem and is introduced to allow the problem to be solved without the need for commercial solvers (and the associated license costs); this is the ideal approach for any commercial software that already faces this problem. The second proof shows that the constraint matrices of the two formulations are totally unimodular. This property, together with the integrality of the right‐hand sides, ensures that the linear relaxations yield integer optimal solutions, which can be easily computed using the simplex method.
Open AccessOn the Complexity of the Paper Selection Problem for the Italian Research Quality Evaluation (VQR)
This work addresses the paper selection problem that each Italian university and department faced in the context of the research quality evaluation (VQR) of the Italian university system for the period 2020–2024. Given the set of researchers of a university and their associated papers, the problem consists of selecting a fixed number of researcher, paper pairs, as established by the Ministry, while respecting bounds on the minimum and maximum number of papers selectable for each researcher, as well as the maximum number of times a paper can be selected. Each pair is associated with a score, which depends on several bibliometric parameters related to both the paper and the author, and the goal of the problem is to select the pairs so as to maximize the total score. In this paper, we consider two versions of the problem, modeling the departments' and the university's perspectives, and for each of them, we provide an integer linear programming formulation. Moreover, we present two proofs showing that the problem can be solved optimally in polynomial time. The first proof consists of a polynomial‐time reduction to the capacitated minimum cost flow problem and is introduced to allow the problem to be solved without the need for commercial solvers (and the associated license costs); this is the ideal approach for any commercial software that already faces this problem. The second proof shows that the constraint matrices of the two formulations are totally unimodular. This property, together with the integrality of the right‐hand sides, ensures that the linear relaxations yield integer optimal solutions, which can be easily computed using the simplex method.
- Open Access
Minimum cost network flow with interval capacities: The worst-case scenario
We study the problem of determining the worst optimal value and characterizing the corresponding worst-case scenarios in minimum cost network flow problems with interval uncertainty in arc capacities. In this setting, each capacity can take any value within its specified lower and upper bounds. We prove that computing the worst optimal value is a strongly NP-hard problem and remains NP-hard even when restricted to series-parallel graphs. Further, we propose a mixed-integer linear programming formulation that computes the exact worst optimal value, as well as a pseudopolynomial-time algorithm designed for the special case of series-parallel graphs. We also examine the structural properties of the most extremal worst-case scenarios and show that the arcs whose capacities are not fixed at their interval bounds form a forest. This result establishes an upper bound on the number of such arcs, which we show to be tight by constructing a class of instances in which the bound is attained. Finally, we investigate the more-for-less paradox in minimum cost network flow problems with interval capacities, which occurs in instances where increasing the required flow leads to a decrease in the worst-case optimal cost. We provide a general characterization of this phenomenon using augmenting paths and establish a stronger characterization for complete graphs. In addition, we discuss the properties of the cost matrices immune against the paradox and prove that deciding whether a given cost matrix has this property is a strongly co-NP-hard problem.
Open AccessMinimum cost network flow with interval capacities: The worst-case scenario
We study the problem of determining the worst optimal value and characterizing the corresponding worst-case scenarios in minimum cost network flow problems with interval uncertainty in arc capacities. In this setting, each capacity can take any value within its specified lower and upper bounds. We prove that computing the worst optimal value is a strongly NP-hard problem and remains NP-hard even when restricted to series-parallel graphs. Further, we propose a mixed-integer linear programming formulation that computes the exact worst optimal value, as well as a pseudopolynomial-time algorithm designed for the special case of series-parallel graphs. We also examine the structural properties of the most extremal worst-case scenarios and show that the arcs whose capacities are not fixed at their interval bounds form a forest. This result establishes an upper bound on the number of such arcs, which we show to be tight by constructing a class of instances in which the bound is attained. Finally, we investigate the more-for-less paradox in minimum cost network flow problems with interval capacities, which occurs in instances where increasing the required flow leads to a decrease in the worst-case optimal cost. We provide a general characterization of this phenomenon using augmenting paths and establish a stronger characterization for complete graphs. In addition, we discuss the properties of the cost matrices immune against the paradox and prove that deciding whether a given cost matrix has this property is a strongly co-NP-hard problem.
- Open Access
- 13 February 2025
- Published by Elsevier in European Journal of Operational Research
- Vol. 324 (2) , 414-435
Hybridizing Carousel Greedy and Kernel Search: A new approach for the maximum flow problem with conflict constraints
- 13 February 2025
- Published by Elsevier in European Journal of Operational Research
- Vol. 324 (2) , 414-435
Open AccessHybridizing Carousel Greedy and Kernel Search: A new approach for the maximum flow problem with conflict constraints
- Open Access
- 24 May 2024
- Published by Elsevier in EURO Journal on Computational Optimization
- Vol. 12
A two-point heuristic to calculate the stepsize in subgradient method with application to a network design problem
- 24 May 2024
- Published by Elsevier in EURO Journal on Computational Optimization
- Vol. 12
Open AccessA two-point heuristic to calculate the stepsize in subgradient method with application to a network design problem
- Open Access
- 13 March 2024
- Published by Elsevier in Computers & Operations Research
- Vol. 166
Solving the Set Covering Problem with Conflicts on Sets: A new parallel GRASP
- 13 March 2024
- Published by Elsevier in Computers & Operations Research
- Vol. 166
Open AccessSolving the Set Covering Problem with Conflicts on Sets: A new parallel GRASP
- 30 September 2023
- Published by Elsevier in European Journal of Operational Research
- Vol. 314 (2) , 446-465
A new formulation and a branch-and-cut algorithm for the set orienteering problem
- 30 September 2023
- Published by Elsevier in European Journal of Operational Research
- Vol. 314 (2) , 446-465
A new formulation and a branch-and-cut algorithm for the set orienteering problem
A genetic approach for the 2‐edge‐connected minimum branch vertices problem
This article addresses the 2‐edge‐connected minimum branch vertices problem, a variant of the minimum branch vertices problem in which the spanning subgraph is required to be 2‐edge‐connected for survivability reasons. The problem has been recently introduced and finds application in optical networks design scenarios, where branch vertices are associated to switch devices that allow to split the entering light signals and send them to several adjacent vertices. An exact approach to the problem has been proposed in the literature. In this paper, we formally prove its NP‐completeness and propose a genetic algorithm, which exploits some literature‐provided procedures for efficiently checking and restoring solutions feasibility, and makes use of novel ad‐hoc designed operators aiming to improve their values, reducing the number of branch vertices. The computational tests show that, on the benchmark instances, the genetic algorithm very often finds the optimal solution. Moreover, in order to further investigate the effectiveness and the performance of our algorithm, we generated a new set of random instances where the optimal solution is known a priori.
A genetic approach for the 2‐edge‐connected minimum branch vertices problem
This article addresses the 2‐edge‐connected minimum branch vertices problem, a variant of the minimum branch vertices problem in which the spanning subgraph is required to be 2‐edge‐connected for survivability reasons. The problem has been recently introduced and finds application in optical networks design scenarios, where branch vertices are associated to switch devices that allow to split the entering light signals and send them to several adjacent vertices. An exact approach to the problem has been proposed in the literature. In this paper, we formally prove its NP‐completeness and propose a genetic algorithm, which exploits some literature‐provided procedures for efficiently checking and restoring solutions feasibility, and makes use of novel ad‐hoc designed operators aiming to improve their values, reducing the number of branch vertices. The computational tests show that, on the benchmark instances, the genetic algorithm very often finds the optimal solution. Moreover, in order to further investigate the effectiveness and the performance of our algorithm, we generated a new set of random instances where the optimal solution is known a priori.
- 1 August 2021
- Published by Elsevier in European Journal of Operational Research
- Vol. 292 (3) , 830-854
A biased random-key genetic algorithm for the set orienteering problem
- 1 August 2021
- Published by Elsevier in European Journal of Operational Research
- Vol. 292 (3) , 830-854
A biased random-key genetic algorithm for the set orienteering problem
- Open Access
- 2 March 2021
- Published by EDP Sciences in RAIRO - Operations Research
- Vol. 55, S2071-S2082
A reduction heuristic for the all-colors shortest path problem
The All-Colors Shortest Path (ACSP) is a recently introduced NP-Hard optimization problem, in which a color is assigned to each vertex of an edge weighted graph, and the aim is to find the shortest path spanning all colors. The solution path can be not simple, that is it is possible to visit multiple times the same vertices if it is a convenient choice. The starting vertex can be constrained (ACSP) or not (ACSP-UE). We propose a reduction heuristic based on the transformation of any ACSP-UE instance into an Equality Generalized Traveling Salesman Problem one. Computational results show the algorithm to outperform the best previously known one.
- 2 March 2021
- Published by EDP Sciences in RAIRO - Operations Research
- Vol. 55, S2071-S2082
Open AccessA reduction heuristic for the all-colors shortest path problem
The All-Colors Shortest Path (ACSP) is a recently introduced NP-Hard optimization problem, in which a color is assigned to each vertex of an edge weighted graph, and the aim is to find the shortest path spanning all colors. The solution path can be not simple, that is it is possible to visit multiple times the same vertices if it is a convenient choice. The starting vertex can be constrained (ACSP) or not (ACSP-UE). We propose a reduction heuristic based on the transformation of any ACSP-UE instance into an Equality Generalized Traveling Salesman Problem one. Computational results show the algorithm to outperform the best previously known one.