TY - JOUR A1 - Maher, Stephen J. T1 - A novel passenger recovery approach for the integrated airline recovery problem JF - Computers & Operations Research N2 - Schedule disruptions require airlines to intervene through the process of recovery; this involves modifications to the planned schedule, aircraft routings, crew pairings and passenger itineraries. Passenger recovery is generally considered as the final stage in this process, and hence passengers experience unnecessarily large impacts resulting from flight delays and cancellations. Most recovery approaches considering passengers involve a separately defined module within the problem formulation. However, this approach may be overly complex for recovery in many aviation and general transportation applications. This paper presents a unique description of the cancellation variables that models passenger recovery by prescribing the alternative travel arrangements for passengers in the event of flight cancellations. The results will demonstrate that this simple, but effective, passenger recovery approach significantly reduces the operational costs of the airline and increases passenger flow through the network. The integrated airline recovery problem with passenger reallocation is solved using column-and-row generation to achieve high quality solutions in short runtimes. An analysis of the column-and-row generation solution approach is performed, identifying a number of enhancement techniques to further improve the solution runtimes. Y1 - 2015 U6 - https://doi.org/10.1016/j.cor.2014.11.005 VL - 57 SP - 123 EP - 137 ER - TY - CHAP A1 - Wu, Cheng-Lung A1 - Maher, Stephen J. T1 - Airline scheduling and disruption management T2 - L. Budd, S. Ison, eds., Air transportation management: an international perspective Y1 - 2017 SN - 9781472451064 SP - 151 EP - 167 PB - Routledge CY - New York ER - TY - GEN A1 - Gottwald, Robert Lion A1 - Maher, Stephen J. A1 - Shinano, Yuji T1 - Distributed domain propagation N2 - Portfolio parallelization is an approach that runs several solver instances in parallel and terminates when one of them succeeds in solving the problem. Despite it's simplicity portfolio parallelization has been shown to perform well for modern mixed-integer programming (MIP) and boolean satisfiability problem (SAT) solvers. Domain propagation has also been shown to be a simple technique in modern MIP and SAT solvers that effectively finds additional domain reductions after a variables domain has been reduced. This paper investigates the impact of distributed domain propagation in modern MIP solvers that employ portfolio parallelization. Computational experiments were conducted for two implementations of this parallelization approach. While both share global variable bounds and solutions they communicate differently. In one implementation the communication is performed only at designated points in the solving process and in the other it is performed completely asynchronously. Computational experiments show a positive performance impact of communicating global variable bounds and provide valuable insights in communication strategies for parallel solvers. T3 - ZIB-Report - 16-71 KW - mixed integer programming KW - parallelization KW - domain propagation KW - portfolio solvers Y1 - 2016 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-61380 SN - 1438-0064 ER - TY - GEN A1 - Gleixner, Ambros A1 - Maher, Stephen J. A1 - Müller, Benjamin A1 - Pedroso, João Pedro T1 - Exact Methods for Recursive Circle Packing N2 - Packing rings into a minimum number of rectangles is an optimization problem which appears naturally in the logistics operations of the tube industry. It encompasses two major difficulties, namely the positioning of rings in rectangles and the recursive packing of rings into other rings. This problem is known as the Recursive Circle Packing Problem (RCPP). We present the first dedicated method for solving RCPP that provides strong dual bounds based on an exact Dantzig–Wolfe reformulation of a nonconvex mixed-integer nonlinear programming formulation. The key idea of this reformulation is to break symmetry on each recursion level by enumerating one-level packings, i.e., packings of circles into other circles, and by dynamically generating packings of circles into rectangles. We use column generation techniques to design a “price-and-verify” algorithm that solves this reformulation to global optimality. Extensive computational experiments on a large test set show that our method not only computes tight dual bounds, but often produces primal solutions better than those computed by heuristics from the literature. T3 - ZIB-Report - 17-07 Y1 - 2017 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-62039 ER - TY - GEN A1 - Maher, Stephen J. A1 - Miltenberger, Matthias A1 - Pedroso, João Pedro A1 - Rehfeldt, Daniel A1 - Schwarz, Robert A1 - Serrano, Felipe T1 - PySCIPOpt: Mathematical Programming in Python with the SCIP Optimization Suite N2 - SCIP is a solver for a wide variety of mathematical optimization problems. It is written in C and extendable due to its plug-in based design. However, dealing with all C specifics when extending SCIP can be detrimental to development and testing of new ideas. This paper attempts to provide a remedy by introducing PySCIPOpt, a Python interface to SCIP that enables users to write new SCIP code entirely in Python. We demonstrate how to intuitively model mixed-integer linear and quadratic optimization problems and moreover provide examples on how new Python plug-ins can be added to SCIP. T3 - ZIB-Report - 16-64 KW - SCIP, Mathematical optimization, Python, Modeling Y1 - 2016 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-61348 SN - 1438-0064 ER - TY - GEN A1 - Rehfeldt, Daniel A1 - Koch, Thorsten A1 - Maher, Stephen J. T1 - Reduction Techniques for the Prize-Collecting Steiner Tree Problem and the Maximum-Weight Connected Subgraph Problem N2 - 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. T3 - ZIB-Report - 16-47 KW - Steiner tree problems KW - reduction techniques KW - prize-collecting Steiner tree problem KW - maximum-weight connected subgraph problem Y1 - 2016 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-60420 SN - 1438-0064 ER - TY - JOUR A1 - Rehfeldt, Daniel A1 - Koch, Thorsten A1 - Maher, Stephen J. T1 - Reduction Techniques for the Prize-Collecting Steiner Tree Problem and the Maximum-Weight Connected Subgraph Problem JF - Networks N2 - 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. Y1 - 2019 U6 - https://doi.org/10.1002/net.21857 VL - 73 SP - 206 EP - 233 PB - Wiley ET - 2 ER - TY - GEN A1 - Gamrath, Gerald A1 - Koch, Thorsten A1 - Maher, Stephen J. A1 - Rehfeldt, Daniel A1 - Shinano, Yuji T1 - SCIP-Jack - A solver for STP and variants with parallelization extensions N2 - 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 is achieved by transforming various problem variants into a general form and solving them 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. T3 - ZIB-Report - 15-27 Y1 - 2015 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-54648 SN - 1438-0064 N1 - A revised version is provided here: http://nbn-resolving.de/urn:nbn:de:0297-zib-60170. ER - TY - GEN A1 - Gamrath, Gerald A1 - Koch, Thorsten A1 - Maher, Stephen J. A1 - Rehfeldt, Daniel A1 - Shinano, Yuji T1 - SCIP-Jack – A solver for STP and variants with parallelization extensions N2 - 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. T3 - ZIB-Report - 16-41 KW - Steiner tree problem KW - SCIP-Jack KW - Steiner tree variants KW - maximum-weight connected subgraph KW - prize-collecting Steiner tree Y1 - 2016 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-60170 SN - 1438-0064 ER - TY - JOUR A1 - Gamrath, Gerald A1 - Koch, Thorsten A1 - Maher, Stephen J. A1 - Rehfeldt, Daniel A1 - Shinano, Yuji T1 - SCIP-Jack – A solver for STP and variants with parallelization extensions JF - Mathematical Programming Computation N2 - 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. Y1 - 2017 U6 - https://doi.org/10.1007/s12532-016-0114-x VL - 9 IS - 2 SP - 231 EP - 296 ER -