title: Decomposition for Large-Scale Optimization with Applications to Airline Traffic Management
Creators: name: Rösel, Florian
Publisher: name: Friedrich-Alexander-Universität Erlangen-Nürnberg (FAU)
Year: 2024
Subjects: subject: Decomposition Approaches, Benders Decomposition, Rolling-Horizon, Mixed-Integer Optimization, Stochastic Optimization

description: In practice, optimization problems are often too large to be solvable. This can be because, for example, decisions to be made in the current optimization step depend on decisions made previously or have an influence on subsequent decisions. Dealing with very large optimization problems is, therefore, playing an increasingly important role in current research. Decomposition approaches can help to deal with large optimization problems. Decomposition approaches aim to split a large and difficult-to-manage optimization problem into several small, easier-to-handle part problems, which are successively solved. By cleverly exchanging information between the part problems, it is often possible to achieve an optimal solution to the original problem. In the following, we consider different types of decomposition methods. The first one is suitable for problems whose size is mainly caused by temporal expansion. The others are suitable for problems whose size is caused by the fact that different, related decisions have to be considered in an integrated manner. The first part of this dissertation contains a brief introduction to the fundamental aspects of decomposition methods and a summary of the results of the articles on which this cumulative dissertation is based. The second part contains reprints of the publications and manuscripts on which the first part is based. The first article that is presented deals with the rolling-horizon approach. It breaks down optimization problems with a long time horizon into many subproblems with a shorter time horizon, which are then solved successively. The approach is very popular for practical applications. Hence, it appears frequently in the relevant literature. We developed an adapted variant of the approach. We proved for the first time that quality guarantees for this variant can be achieved, and we proved that no similar quality guarantees can be achieved for the classical variant of this approach. We applied the approach successfully to solve two optimization problems that were emerging in practice. The second article specifies a variant of logic-based Benders Decomposition. First, an integrated model is set up for aircraft-to-flight assignment with ground process planning. This model is difficult to access for conventional decomposition approaches, as it has to be decomposed into two mixed-integer optimization problems. Hence, we developed a decomposition approach to solve the integrated optimization model. We proved that this solution approach is exact. We demonstrated its applicability to realistic problem instances. The third article introduces a variant of Benders Decomposition. More precisely, a new cut selection strategy is developed. The paradigm according to which cuts are selected is to reduce the set of master solutions that have a chance to be optimal as fast as possible. We developed a method to efficiently calculate Benders cuts that follow this paradigm. We showed that our cut selection strategy empirically outperforms several cut selection strategies known from the literature. The fourth article presents optimality certificates for convex mixed-integer opti- mization problems. We found tighter size bounds for the certificates. In addition, we developed an algorithm that calculates optimality certificates. This was used to empirically investigate the properties of optimality certificates. In the last article, a stochastic optimization problem is solved, which optimizes the aircraft-flight assignment, whereby maintenance predictions are included in the decision-making processes. The solution algorithm is a variant of the L-Shaped Method. We proved that the method is not efficient if it is directly applied to solve the problem. Hence, we adapted the method to be able to solve the problem and proved that these adaptations are valid. The computational study demonstrates the high performance of the approach.