### Table of Contents

# Principal Reasearch Topics

My principal areas of research concern theory and algorithms for Mixed Integer Linear
and Non-Linear Programming problems and the study of challenging applications such as
the Aircraft Routing and Sequencing problems, and the Train Timetabling problem.

- Habilitation à Diriger des Recherches pdf

# Generic Dantzig-Wolfe Decomposition and Column Generation Algorithms

From the beginning of my Ph.D, I studied the Dantzig-Wolfe decomposition and reformulation. This technique is well-known to provide strong dual bounds for specially structured mixed integer programs (MIPs). However, the method was not implemented in any state-of-the-art MIP solver as it was considered to require structural problem knowledge and tailoring to this structure. As part of a collaboration between different universities, including Bologna and Aachen Universities, I worked on the development of a computational proof-of-concept that the process can be automated. Our results suggested that generic Dantzig-Wolfe reformulation can be effective used to solve generic MIPs outperforming the classical approaches based on Branch-and-Cut algorithms for different classes of problems. Our results are now implemented in SCIP Optimization Suite which is a state-of-the-art non commercial solver. In particular, now the generic Dantzig-Wolfe decomposition can be automatically exploited using GCG, a generic branch-cut-and-price solver for mixed integer programs.

A second large stream of my research has been devoted to Branch&Price methods and Column Generation techniques, producing various papers in collaboration with different research teams. Among others, I carried out a study on a natural generalization of the knapsack problem, in which each item exists only for a given time interval. We developed exact algorithms outperforming the state-of-the-art previous approaches. As a second example, I studied extensive formulations for the Weighted Vertex Coloring Problem (WVCP), in which a positive weight is associated to each vertex of a graph. We proposed the first exact algorithm for the problem showing excellent performance results when compared with the state-of-the-art algorithms from the literature.

# Cutting and Packing

I studied exact algorithms for Cutting and Packing optimization problems with special attention on 2-Dimensional constraints (2DCSP). I considered the two-dimensional cutting stock problem where stock of different sizes is available, and a set of rectangular items has to be obtained through two-staged guillotine cuts. I proposed algorithms, based on column generation, which requires as their subproblem the solution of a two-dimensional knapsack problem with two-staged guillotines cuts. In addition, I proposed different Mixed-Integer Programming models for the 2-Dimensional Cutting Stock and Bin Packing problems. In collaboration with researchers from the University of Nagoya, Japan, and the University of Modena, Italy, we studied a robust generalization of the 0-1 knapsack problem in which the profit of each item can take values in a range. This problem is called Min-Max Regret Knapsack Problem (MRKP). The problem is extremely challenging both from a theoretical and a practical point of view. We examined the behavior of classical combinatorial optimisation approaches when adapted to the solution of the MRKP, and we introduced an iterated local search approach and a Lagrangian-based branch-and-cut algorithm, evaluating their performance through extensive computational experiments.

# Non-Linear Programming problems

My research in the field of Mixed-Integer Non-Linear Optimization has been focused on two important aspects of this topic. Firstly I have worked on the Perspective Reformulation (PR) of a Mixed-Integer NonLinear Program (MINLP) with semi-continuous variables. This reformulation is obtained by replacing each term in the (separable) objective function with its convex envelope. In turn, the PR of a MINLP can be reformulated either as a Mixed-Integer Second-Order Cone Program (provided that the original objective function is SOCP-representable), or as a Semi-Infinite MINLP, or, under some rather restrictive assumptions, as a piecewise-convex problem. In collaboration with a team from Pisa University, I have worked on improving on the latter approach, showing how to significantly relax the restrictive assumptions, in particular the most binding one which forbids constraints directly linking the binary variables together. This approach is applicable to the many non-projectable applications, and allows direct use of off-the-shelf MIQP software, thereby benefiting from all the sophisticated machinery it includes.

The second aspect that I have explored, with a researcher from Dortmund University, is the exploitation of Semidefinite Programming (SDP) relaxation within the framework provided by Mixed Integer Nonlinear Programming (MINLP) solvers when tackling Binary Quadratic Problems (BQP). SDP relaxation is well-known to provide strong bounds for BQP in practice. However, the method is not typically implemented in many state-of-the-art MINLP solvers based on Linear Programming (LP) relaxation. Our tests indicated that the Hybrid LP/SDP Bounding Procedure allows a noticeable reduction of computing time and a cut of almost one order of magnitude for the branching nodes.

# Applications

In my research, I have also devoted much attention to the real-world applications of Operations Research, and I have had the chance to investigate the problematics associated with Aircraft Routing and Sequencing, and Train Timetabling. Both problems have been studied in collaboration with some of the leading industries of the sector. Firstly, I have studied Air Space Systems automation, which is among the most interesting challenges facing us in the coming years. The use of Uninhabited Aerial Systems (UAS) for civil missions will be one of the most important steps in this automation process. As an example of employment in civil air space, we considered a UAS surveillance mission that consisted in departing from a ground base, taking pictures over a set of mission targets and coming back to the same ground base. Secondly, I have carried out an in-depth study of aircraft sequencing, an issue which is particularly important given the continuous growth of air transportation demand. The runways of large airports serve thousands of aircraft every day, and aircraft sequencing is a challenging problem that aims to increase runway capacity in order to reduce delays as well as the workload of air traffic controllers. In collaboration with ENAV, the Italian Air Traffic Control service provider, I have developed two works of research which investigate a rolling horizon approach, partitioning a sequence of aircraft into chunks and solving the Aircraft Sequencing Problem (ASP) individually for each of these chunks. Finally, I developed an iterated rolling horizon algorithm which, by using different chunking rules, was able to find solutions significantly improving on the First-Come-First-Served rule for real world air traffic instances from Milano Linate Airport.

My other key focus in terms of real-world problems and applications of Operations Research concerns the problematic surrounding Train scheduling. During my PhD research, I worked on a consulting project for Trenitalia, the Italian national railway company, concerning the development of a software to optimise train time-tabling. In this work, I have outlined the conflict-free scheduling problem which arises in railway networks, where ideal timetables have been provided for a set of trains, but where these timetables may be conflicting. I used a space-time graph approach from the railway scheduling literature in order to develop a fast heuristic which resolves conflicts by adjusting the ideal timetables while attempting to minimize the deviation from the ideal timetable. The approach was tested on realistic data obtained from the railway node of Milan.