Refine
Document Type
- Article (9) (remove)
Language
- English (9)
Has Fulltext
- no (9)
Is part of the Bibliography
- no (9) (remove)
Institute
The unrooted set covering connected subgraph problem differentiating between HIV envelope sequences
(2016)
This paper presents a novel application of operations research techniques to the analysis of HIV Env gene sequences, aiming to identify key features that are possible vaccine targets. These targets are identified as being critical to the transmission of HIV by being present in early transmitted (founder) sequences and absent in later chronic sequences. Identifying the key features of Env involves two steps: first, calculating the covariance of amino acid combinations and positions to form a network of related and compensatory mutations; and second, developing an integer program to identify the smallest connected subgraph of the constructed covariance network that exhibits a set covering property. The integer program developed for this analysis, labelled the unrooted set covering connected subgraph problem (USCCSP), integrates a set covering problem and connectivity evaluation, the latter formulated as a network flow problem. The resulting integer program is very large and complex, requiring the use of Benders' decomposition to develop an efficient solution approach. The results will demonstrate the necessity of applying acceleration techniques to the Benders' decomposition solution approach and the effectiveness of these techniques and heuristic approaches for solving the USCCSP.
Schedule disruptions are commonplace in the airline industry with many flight-delaying events occurring each day. Recently there has been a focus on introducing robustness into airline planning stages to reduce the effect of these disruptions. We propose a recoverable robustness technique as an alternative to robust optimisation to reduce the effect of disruptions and the cost of recovery. We formulate the recoverable robust tail assignment problem (RRTAP) as a stochastic program, solved using column generation in the master and subproblems of the Benders' decomposition. We implement a two-phase algorithm for the Benders' decomposition and identify pareto-optimal cuts. The RRTAP includes costs due to flight delays, cancellation, and passenger rerouting, and the recovery stage includes cancellation, delay, and swapping options. To highlight the benefits of simultaneously solving planning and recovery problems in the RRTAP we compare our tail assignment solution against current approaches from the literature. Using airline data we demonstrate that by developing a better tail assignment plan via the RRTAP framework, one can reduce recovery costs in the event of a disruption.
Aircraft maintenance planning is of critical importance to the safe and efficient operations of an airline. It is common to solve the aircraft routing and maintenance planning problems many months in advance, with the solution spanning multiple days. An unfortunate consequence of this approach is the possible infeasibility of the maintenance plan due to frequent perturbations occurring in operations. There is an emerging concept that focuses on the generation of aircraft routes for a single day to ensure maintenance coverage that night, alleviating the effects of schedule perturbations from preceding days. In this paper, we present a novel approach to ensure that a sufficient number of aircraft routes are provided each day so maintenance critical aircraft receive maintenance that night. By penalising the under supply of routes terminating at maintenance stations from each overnight airport, we construct a single day routing to provide the best possible maintenance plan. This single day aircraft maintenance routing problem (SDAMRP) is further protected from disruptions by applying the recoverable robustness framework. To efficiently solve the recoverable robust SDAMRP acceleration techniques, such as identifying Pareto-optimal cuts and a trust region approach, have been applied. The SDAMRP is evaluated against a set of flight schedules and the results demonstrate a significantly improved aircraft maintenance plan. Further, the results demonstrate the magnitude of recoverability improvement that is achieved by employing recoverable robustness to the SDAMRP.
The tail assignment problem is a critical part of the airline planning process that assigns specific aircraft to sequences of flights, called lines-of-flight, to satisfy operational constraints. The aim of this paper is to develop an operationally flexible method, based upon the one-day routes business model, to compute tail assignments that satisfy short-range—within the next three days—aircraft maintenance requirements. While maintenance plans commonly span multiple days, the methods used to compute tail assignments for the given plans can be overly complex and provide little recourse in the event of schedule perturbations. The presented approach addresses operational uncertainty by using solutions from the one-day routes aircraft maintenance routing approach as input. The daily tail assignment problem is solved with an objective to satisfy maintenance requirements explicitly for the current day and implicitly for the subsequent two days. A computational study will be performed to assess the performance of exact and heuristic solution algorithms that modify the input lines-of-flight to reduce maintenance misalignments. The daily tail assignment problem and the developed algorithms are demonstrated to compute solutions that effectively satisfy maintenance requirements when evaluated using input data collected from three different airlines.
The Steiner tree problem in graphs is a classical problem that commonly arises in practical applications as one of many variants. While often a strong relationship between different Steiner tree problem variants can be observed, solution approaches employed so far have been prevalently problem-specific. In contrast, this paper introduces a general-purpose solver that can be used to solve both the classical Steiner tree problem and many of its variants without modification. This versatility is achieved by transforming various problem variants into a general form and solving them by using a state-of-the-art MIP-framework. The result is a high-performance solver that can be employed in massively parallel environments and is capable of solving previously unsolved instances.
The concept of reduction has frequently distinguished itself as a pivotal ingredient of exact solving approaches for the Steiner tree problem in graphs. In this paper we broaden the focus and consider reduction techniques for three Steiner problem variants that have been extensively discussed in the literature and entail various practical applications: The prize-collecting Steiner tree problem, the rooted prize-collecting Steiner tree problem and the maximum-weight connected subgraph problem.
By introducing and subsequently deploying numerous new reduction methods, we are able to drastically decrease the size of a large number of benchmark instances, already solving more than 90 percent of them to optimality. Furthermore, we demonstrate the impact of these techniques on exact solving, using the example of the state-of-the-art Steiner problem solver SCIP-Jack.
The SCIP Optimization Suite provides a collection of software packages for mathematical optimization centered around the constraint integer programming framework SCIP. The focus of this article is on the role of the SCIP Optimization Suite in supporting research. SCIP’s main design principles are discussed, followed by a presentation of the latest performance improvements and developments in version 8.0, which serve both as examples of SCIP’s application as a research tool and as a platform for further developments. Furthermore, this article gives an overview of interfaces to other programming and modeling languages, new features that expand the possibilities for user interaction with the framework, and the latest developments in several extensions built upon SCIP.