Best AIROYoung Dissertation 2022

Time Slot: Friday Morning

Room: 002

Chair: Alice Raffaele

Real-time Train Scheduling: Reactive and Proactive Algorithms for Safe and Reliable Railway Networks

Time: 11:30

Anna Livia Croella (Sapienza – University of Rome)

Train scheduling is a critical activity in rail traffic management, both off-line (timetabling) and on-line/in real-time (dispatching). The research aims at the design and development of advanced optimization models and methods for the real-time re-scheduling. The study covers two overlapping areas and defines two different but somewhat complementary research questions:(i) in case of disturbance, how can we quickly generate a new feasible plan?(ii) in case of disruption (or partial re-scheduling information), how can we add an additional level of safety to the system?To answer the first question, we exploited and extended the Dynamic Discretization Discovery (DDD) paradigm, recently introduced by Boland for the continuous time service network design problem. The result is a restricted Time-Indexed formulation for traintraffic re-scheduling problem and an algorithm to solve it with running times comparable with the best alternatives presented in the literature. Furthermore, the implemented procedure does not suffer by any approximation error introduced by a standard time discretization and can be applied to the broader field of job-shop scheduling. This work has been presented at a renowned railway conference (ICROMA).The second research issue is answered by formulating a Safe Place Assignment Problem. This new model is tested on a set of instances provided by a large Class I U.S. railroad company, demonstrating how it can be used effectively in a real-world context. The relative work has been published on a top tier Operation Research journal whose main focus lays on transport (Transportation Science).Both research outputs are very innovative and off the beaten track. The achievements regards both the theoretical and methodological point of view and present in addition a practical relevance.Keywords: Real-time Train Rescheduling; Dynamic Discretization Discovery; Disruption Management.

Models and Approximations for Optimization Problems under Uncertainty with Applications to Support Vector Machine and Revenue Management

Time: 11:50

Daniel Faccini (University of Bergamo)

In this thesis, we deal with decision making problems plagued by the presence of uncertainty. The first problem we analyze aims at linearly separating two sets of points that have non-disjoint convex closures. To solve this classification task, we formulate robust Support Vector Machine (SVM) models with uncertainty sets in the form of hyperrectangles or hyperellipsoids, and propose a moment-based Distributionally Robust Optimization (DRO) model enforcing limits on first-order deviations along principal directions. The efficiency of the new classifiers is evaluated on real-world databases. Numerical experiments show that considering uncertainty explicitly in the models leads to better solutions with respect to the ones provided by the corresponding deterministic program. Despite the wide applicability of DRO models, this class of problems is notoriously difficult to solve. For this reason, secondly, we propose approximation techniques that provide (lower and upper) bounds on the optimal value for DRO problems. This is done through scenario grouping and using the ambiguity sets associated with φ-divergences and the Wasserstein distance. Numerical results on a multistage mixed-integer production problem show the efficacy of the novel bounding schemes through different choices of partition strategies, ambiguity sets, and levels of robustness. Thirdly, the last problem we investigate aims at detecting the optimal assortments a retailer shall offer to the market with the aim of maximizing expected profits, when strong preferences among products are observed. This Revenue Management (RM) problem with dominated alternatives is firstly modeled through stochastic dynamic programming, which becomes intractable for instances with a large number of resources. To deal with this curse of dimensionality we recover a compact and tractable deterministic approximation and present preliminary numeric results.Keywords: Support Vector Machine; Robust Optimization; Distributionally Robust Optimization; Revenue Management.

Optimizing and Reoptimizing: Tackling Static and Dynamic Combinatorial Problems

Time: 12:10

Serena Fugaro (Institute for Applications of Calculus “Mauro Picone” – National Research Council of Italy)

In this thesis both static and dynamic problems of Operations Research are addressed by either designing new procedures or adapting well-known algorithmic schemes. Specifically, three variants of the well-known Shortest Path Problem (SPP) and a Scheduling Problem in 3D printing are studied.Firstly, we dealt with the Reoptimization of Shortest Paths, in case of multiple and generic cost changes. We implemented an exact primal-dual procedure, and compared its performance with Dijkstra’s label setting procedure to detect the approach to prefer, according to the graph features and the type of cost perturbation.Secondly, the k-Color Shortest Path Problem is tackled: it is a recent problem, defined on an edge-constrained graph, for which we proposed a Dynamic Programming algorithm; its performance is compared with the state of the art solution approach, namely a Branch & Bound procedure.Finally, the Resource Constrained Clustered Shortest Path Tree Problem is presented. It is a newly defined problem for which we detail both a mathematical model and a Branch & Price procedure; moreover, the performance of this solution approach is compared with that of CPLEX solver.Furthermore, the first part of the dissertation addresses the Path Planning in Urban Air Mobility, considering the definition of the Free-Space Maps and the computation of the trajectories. For the former purpose, three different but correlated discretization methods are described; as for the latter, a two steps resolution of the resulting shortest path problems is performed, and it is checked if the reoptimization algorithm is suitable for the second step.The last part of the thesis is devoted to the recently studied Additive Manufacturing Machine Scheduling Problem with not-identical machines. Specifically, a Reinforcement Learning Iterated Local Search meta-heuristic featuring a Q-learning Variable Neighbourhood Search is proposed to solve this problem and its performance is compared with the one of CPLEX solver.It is worthwhile mentioning that, for each of the proposed approaches, a thorough experimentation is performed and each Chapter is equipped with a detailed analysis of the results in order to appraise the performance of the method and to detect its limits.Keywords: Constrained Shortest Path Problem; Combinatorial Optimization; Additive Manufacturing Machine Scheduling.

Theory and Algorithms for Sparsity Constrained Optimization Problems

Time: 12:30

Matteo Lapucci (DINFO, Università di Firenze)

The dissertation is concerned with mathematical optimization problems where a sparsity constraint appears. The sparsity of the solution is a valuable requirement in many applications of operations research. Several classes of very different approaches have been proposed in the literature for this sort of problems; when the objective function is nonconvex, in presence of difficult additional constraints or in the high-dimensional case, the problem shall be addressed as a continuous optimization task, even though it naturally has an intrinsic combinatorial nature. Within this setting, we first review the existing knowledge and the theoretical tools concerning the considered problem; we try to provide a unified view of parallel streams of research and we propose
a new general stationarity condition, based on the concept of neighborhood, which somehow allows to take into account both the continuous and the combinatorial aspects of the problem. Then, after a brief overview of the main algorithmic approaches in the related literature, we propose suitable variants of some of these schemes that can be effectively employed in complex settings, such as the nonconvex one, the derivative-free one or the multi-objective one. For each of the proposed algorithms we provide a detailed convergence analysis showing that these methods enjoy important theoretical guarantees, in line with the state-of-the-art algorithms. Afterwards, exploiting the newly introduced concept of stationarity, we propose a completely novel algorithmic scheme that, combining continuous local searches and discrete moves, can be proved to guarantee stronger theoretical properties than most approaches from the literature and to exhibit strong exploration capabilities in a global optimization perspective. All the proposed algorithms have finally been experimentally tested on a benchmark of relevant problems from machine learning and decision science applications. The computational results show the actual quality of the proposed methods when practically employed.Keywords: Nonlinear Optimization; Sparsity; Convergent Algorithms.