TY - GEN A1 - Maher, Stephen J. A1 - Desaulniers, Guy A1 - Soumis, Francois T1 - The tail assignment problem with look-ahead maintenance constraints N2 - 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 be operated the next day. The aim of this paper is to develop an operationally flexible tail assignment that satisfies short-range---within the next three days---aircraft maintenance requirements and performs the aircraft/flight gate assignment for each input line-of-flight. While maintenance plans commonly span multiple days, the related tail assignment problems can be overly complex and provide little recourse in the event of schedule perturbations. The presented approach addresses operational uncertainty by extending the one-day routes aircraft maintenance routing approach to satisfy maintenance requirements explicitly for the current day and implicitly for the subsequent two days. A mathematical model is presented that integrates the gate assignment and maintenance planning problems. To increase the satisfaction of maintenance requirements, an iterative algorithm is developed that modifies the fixed lines-of-flight provided as input to the tail assignment problem. The tail assignment problem and iterative algorithm are demonstrated to effectively satisfy maintenance requirements within appropriate run times using input data collected from three different airlines. T3 - ZIB-Report - 15-56 KW - Tail assignment KW - Column generation KW - Iterative algorithm Y1 - 2015 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-56717 SN - 1438-0064 ER - TY - JOUR A1 - Gamrath, Gerald A1 - Koch, Thorsten A1 - Martin, Alexander A1 - Miltenberger, Matthias A1 - Weninger, Dieter T1 - Progress in presolving for mixed integer programming JF - Mathematical Programming Computation N2 - This paper describes three presolving techniques for solving mixed integer programming problems (MIPs) that were implemented in the academic MIP solver SCIP. The task of presolving is to reduce the problem size and strengthen the formulation, mainly by eliminating redundant information and exploiting problem structures. The first method fixes continuous singleton columns and extends results known from duality fixing. The second analyzes and exploits pairwise dominance relations between variables, whereas the third detects isolated subproblems and solves them independently. The performance of the presented techniques is demonstrated on two MIP test sets. One contains all benchmark instances from the last three MIPLIB versions, while the other consists of real-world supply chain management problems. The computational results show that the combination of all three presolving techniques almost halves the solving time for the considered supply chain management problems. For the MIPLIB instances we obtain a speedup of 20 % on affected instances while not degrading the performance on the remaining problems. Y1 - 2015 U6 - https://doi.org/10.1007/s12532-015-0083-5 VL - 7 IS - 4 SP - 367 EP - 398 ER -