Mixed-Integer Nonlinear Programming (MINLP) deals with the most general optimization problems, involving both continuous and discrete variables and nonlinear constraint functions. These are among the most challenging computational optimization problems, arising in countless applications from various areas. While research on mixed-integer linear optimization is quite advanced, MINLP is considered an emerging area that is likely to grow in the coming years. MINLP models being in general very difficult to solve, they require exploiting their properties and developing special solution techniques to reduce the computational effort.
The ATOMIC project is in the framework of this hot research topic, with the aim of contributing to the advancement in both modeling stimulating real-life problems and developing efficient methods for their solution. A number of challenging problems arising in Air Traffic Management (ATM) constitute interesting research topics particularly in Operations Research and Optimization and naturally lead to MINLP models. Air traffic is at the core of the social and economic dynamism of our society, and an efficient Air Traffic Management has evidently a deep impact on the social, economic, environmental and industrial context. In this framework, a few problems urgently need addressing to ensure a higher level of automation in ATM and consequently more efficiency and safety.
The present project focuses on air traffic conflicts, which occur when aircraft are too close to each other according to their predicted trajectories. Mixed-Integer Nonlinear Programming formulations appear to be the natural candidates for these addressed ATM problems, where the need for modeling logical choices suggests the simultaneous presence of mixed (continuous-integer) variables and nonlinear constraints arise from separation condition modeling. Solution algorithms for these ATM problems are mainly based on evolutionary computation. While these methods are computationally efficient, the global optimal solution and even a feasible solution (with no conflict) is not guaranteed to be achieved in a given time. Recent advances in mixed-integer linear and nonlinear programming open new perspectives that have been lacking in earlier researches on conflict avoidance and can have an impact on its effective solution.
The present project is therefore aimed to fully exploiting and developing mixed-integer optimization techniques to propose efficient solutions. The optimization will be performed developing specific strategies to deal with the computational difficulty of the target large-scale problems. Deterministic Branch-and-Bound (BB)-type methods (spatial-Branch-and-Bound and interval-Branch-and-Bound variants) will be primarily considered, exploring strategies that can have an impact on the algorithm’s ability to provide an optimal solution, including for example strong reformulations and branching strategies. To deal with the difficulty of the problem, other strategies will be also explored, where the optimality guarantee is forsaken in exchange for the computational efficiency. Specifically, we will investigate hybridization of mathematical programming techniques and (meta)-heuristics, in a ”matheuristic” framework, where an essential feature is the exploitation of the features of the conceived mathematical programming models of the addressed problem. Starting from the results obtained for the considered specific application, we will seek to identify more general classes of MINLP problems to which the developed techniques can be applied. Expected results of the project include new mathematical models from mixed-integer programming and effective optimization methods, as well as a software library implementing the proposed algorithms.