Eleonora Vercesi
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Previous Organizations / Institutes
The organizations / institutes from the scholar's other articles in the past ten years
Eleonora Vercesi has a total of 14 co-authors. Here are the top co-authors by number of shared publications:
- Monaldo Mastrolilli
University of Applied Sciences and Arts of Southern Switzerland (SUPSI-IDSIA), CH 6962 Lugano, Switzerland
4 shared publications - János Barta
Dipartimento Tecnologie innovative Scuola universitaria professionale della Svizzera italiana (SUPSI) Lugano Switzerland
2 shared publications Luca Maria Gambardella
2 shared publications- Ambrogio Maria Bernardelli
Department of Mathematics "F. Casorati" University of Pavia Via Ferrata 5 27100 Pavia Italy
1 shared publication - Austin Buchanan
Industrial Engineering & Management, Oklahoma State University, Stillwater, Oklahoma 74078
1 shared publication - Davide Duma
Università degli Studi di Torino
1 shared publication
Latest Publications
- 6 October 2026
- Published by Springer Nature
- p. 290-311
The Falsification Problem: How Hard Is It to Falsify Heuristics?
- 6 October 2026
- Published by Springer Nature
- p. 290-311
The Falsification Problem: How Hard Is It to Falsify Heuristics?
- 25 September 2026
- Published by Institute for Operations Research and the Management Sciences (INFORMS) in INFORMS Journal on Optimization
The Dantzig–Fulkerson–Johnson TSP Formulation Is Easy to Solve for Few Subtour Constraints
The most successful approaches for the traveling salesman problem (TSP) use the integer programming model proposed in 1954 by Dantzig, Fulkerson, and Johnson (DFJ). Although this model has exponentially many subtour elimination constraints (SECs), it has been observed that relatively few of them are needed to prove optimality in practice. This leads us to wonder, what is the complexity of the DFJ model when just a small number of SECs are imposed? Also, for a given instance, what is the minimum number of SECs required to certify the optimality of one of its TSP tours? We offer both positive and negative results. On the positive side, we give an algorithm to solve the DFJ model that runs in polynomial time when only a constant number of SECs are imposed. With an additional condition, we also find a minimum number of SECs in polynomial time. This provides an explanation for the apparent easiness of some TSP instances despite the intractability of the problem in the worst case. As part of our experiments, we show that the original 49-city TSP instance of DFJ requires a minimum of four SECs, which we generate in a fraction of a second with a simple Python implementation. Funding: The research of E. Vercesi was supported by the Swiss National Science Foundation [Grant 200021_212929/1] “Computational methods for integrality gaps analysis.” The research of A. Buchanan is based on work supported by the National Science Foundation [Grant 1942065] and the Air Force Office of Scientific Research [Grant FA9550-25-1-0277]. Supplemental Material: The online appendix is available at https://doi.org/10.1287/ijoo.2025.0078 .
- 25 September 2026
- Published by Institute for Operations Research and the Management Sciences (INFORMS) in INFORMS Journal on Optimization
The Dantzig–Fulkerson–Johnson TSP Formulation Is Easy to Solve for Few Subtour Constraints
The most successful approaches for the traveling salesman problem (TSP) use the integer programming model proposed in 1954 by Dantzig, Fulkerson, and Johnson (DFJ). Although this model has exponentially many subtour elimination constraints (SECs), it has been observed that relatively few of them are needed to prove optimality in practice. This leads us to wonder, what is the complexity of the DFJ model when just a small number of SECs are imposed? Also, for a given instance, what is the minimum number of SECs required to certify the optimality of one of its TSP tours? We offer both positive and negative results. On the positive side, we give an algorithm to solve the DFJ model that runs in polynomial time when only a constant number of SECs are imposed. With an additional condition, we also find a minimum number of SECs in polynomial time. This provides an explanation for the apparent easiness of some TSP instances despite the intractability of the problem in the worst case. As part of our experiments, we show that the original 49-city TSP instance of DFJ requires a minimum of four SECs, which we generate in a fraction of a second with a simple Python implementation. Funding: The research of E. Vercesi was supported by the Swiss National Science Foundation [Grant 200021_212929/1] “Computational methods for integrality gaps analysis.” The research of A. Buchanan is based on work supported by the National Science Foundation [Grant 1942065] and the Air Force Office of Scientific Research [Grant FA9550-25-1-0277]. Supplemental Material: The online appendix is available at https://doi.org/10.1287/ijoo.2025.0078 .
- 31 March 2026
- Published by Institute for Operations Research and the Management Sciences (INFORMS) in Mathematics of Operations Research
Branch-and-Bound Algorithms as Polynomial-Time Approximation Schemes
Branch-and-bound algorithms (B&B) and polynomial-time approximation schemes (PTAS) are two seemingly distant areas of combinatorial optimization. We intend to (partially) bridge the gap between them while expanding the boundary of theoretical knowledge on the B&B framework. Branch-and-bound algorithms typically guarantee that an optimal solution is eventually found. However, we show that the standard implementation of branch-and-bound for certain knapsack and scheduling problems also exhibits PTAS-like behavior, yielding increasingly better solutions within polynomial time. Our findings are supported by computational experiments and comparisons with benchmark methods. Funding: This work was supported by Schweizerischer Nationalfonds zur Förderung der Wissenschaftlichen Forschung [Grant 200021_212929/1 (“Computational methods for integrality gaps analysis”)].
- 31 March 2026
- Published by Institute for Operations Research and the Management Sciences (INFORMS) in Mathematics of Operations Research
Branch-and-Bound Algorithms as Polynomial-Time Approximation Schemes
Branch-and-bound algorithms (B&B) and polynomial-time approximation schemes (PTAS) are two seemingly distant areas of combinatorial optimization. We intend to (partially) bridge the gap between them while expanding the boundary of theoretical knowledge on the B&B framework. Branch-and-bound algorithms typically guarantee that an optimal solution is eventually found. However, we show that the standard implementation of branch-and-bound for certain knapsack and scheduling problems also exhibits PTAS-like behavior, yielding increasingly better solutions within polynomial time. Our findings are supported by computational experiments and comparisons with benchmark methods. Funding: This work was supported by Schweizerischer Nationalfonds zur Förderung der Wissenschaftlichen Forschung [Grant 200021_212929/1 (“Computational methods for integrality gaps analysis”)].
- Open Access
- 4 July 2025
- Published by Elsevier in Discrete Optimization
- Vol. 57
On the integrality gap of small Asymmetric Traveling Salesman Problems: A polyhedral and computational approach
- 4 July 2025
- Published by Elsevier in Discrete Optimization
- Vol. 57
Open AccessOn the integrality gap of small Asymmetric Traveling Salesman Problems: A polyhedral and computational approach
- Open Access
On the integrality Gap of Small Asymmetric Traveling Salesman Problems: A Polyhedral and Computational Approach
In this paper, we investigate the integrality gap of the Asymmetric Traveling Salesman Problem (ATSP) with respect to the linear relaxation given by the Asymmetric Subtour Elimination Problem (ASEP) for instances with $n$ nodes, where $n$ is small. In particular, we focus on the geometric properties and symmetries of the ASEP polytope ($P^{n}_{ASEP}$) and its vertices. The polytope's symmetries are exploited to design a heuristic pivoting algorithm to search vertices where the integrality gap is maximized. Furthermore, a general procedure for the extension of vertices from $P^{n}_{ASEP}$ to $P^{n + 1}_{ASEP}$ is defined. The generated vertices improve the known lower bounds of the integrality gap for $ 16 \leq n \leq 22$ and, provide small hard-to-solve ATSP instances.Open AccessOn the integrality Gap of Small Asymmetric Traveling Salesman Problems: A Polyhedral and Computational Approach
In this paper, we investigate the integrality gap of the Asymmetric Traveling Salesman Problem (ATSP) with respect to the linear relaxation given by the Asymmetric Subtour Elimination Problem (ASEP) for instances with $n$ nodes, where $n$ is small. In particular, we focus on the geometric properties and symmetries of the ASEP polytope ($P^{n}_{ASEP}$) and its vertices. The polytope's symmetries are exploited to design a heuristic pivoting algorithm to search vertices where the integrality gap is maximized. Furthermore, a general procedure for the extension of vertices from $P^{n}_{ASEP}$ to $P^{n + 1}_{ASEP}$ is defined. The generated vertices improve the known lower bounds of the integrality gap for $ 16 \leq n \leq 22$ and, provide small hard-to-solve ATSP instances. - Open Access
- 12 June 2024
- Published by Springer Nature in Flexible Services and Manufacturing Journal
- Vol. 37 (4) , 1148-1202
Multi-objective stochastic scheduling of inpatient and outpatient surgeries
With the advancement of surgery and anesthesiology in recent years, surgical clinical pathways have changed significantly, with an increase in outpatient surgeries. However, the surgical scheduling problem is particularly challenging when inpatients and outpatients share the same operating room blocks, due to their different characteristics in terms of variability and preferences. In this paper, we present a two-phase stochastic optimization approach that takes into account such characteristics, considering multiple objectives and dealing with uncertainty in surgery duration, arrival of emergency patients, and no-shows. Chance Constrained Integer Programming and Stochastic Mixed Integer Programming are used to deal with the advance scheduling and the allocation scheduling, respectively. Since Monte Carlo sampling is inefficient for solving the allocation scheduling problem for large size instances, a genetic algorithm is proposed for sequencing and timing procedures. Finally, a quantitative analysis is performed to analyze the trade-off between schedule robustness and average performance under the selection of different patient mixes, providing general insights for operating room scheduling when dealing with inpatients, outpatient, and emergencies.
- 12 June 2024
- Published by Springer Nature in Flexible Services and Manufacturing Journal
- Vol. 37 (4) , 1148-1202
Open AccessMulti-objective stochastic scheduling of inpatient and outpatient surgeries
With the advancement of surgery and anesthesiology in recent years, surgical clinical pathways have changed significantly, with an increase in outpatient surgeries. However, the surgical scheduling problem is particularly challenging when inpatients and outpatients share the same operating room blocks, due to their different characteristics in terms of variability and preferences. In this paper, we present a two-phase stochastic optimization approach that takes into account such characteristics, considering multiple objectives and dealing with uncertainty in surgery duration, arrival of emergency patients, and no-shows. Chance Constrained Integer Programming and Stochastic Mixed Integer Programming are used to deal with the advance scheduling and the allocation scheduling, respectively. Since Monte Carlo sampling is inefficient for solving the allocation scheduling problem for large size instances, a genetic algorithm is proposed for sequencing and timing procedures. Finally, a quantitative analysis is performed to analyze the trade-off between schedule robustness and average performance under the selection of different patient mixes, providing general insights for operating room scheduling when dealing with inpatients, outpatient, and emergencies.