  


MixedInteger Reformulations of ResourceConstrained TwoStage Assignment Problems
Lena Hupp(lena.huppsiemens.com) Abstract: The running time for solving a mixedinteger linear optimization problem (MIP) strongly depends on the number of its integral variables. Bader et al. [Math. Progr. 169 (2018) 565–584] equivalently reformulate an integer program into an MIP that contains a reduced number of integrality constraints, when compared to the original model. Generalizing the concept of totally unimodular (TU) matrices, the reformulation is determined via a socalled affine TU decomposition of the underlying constraint matrix. In this work, we develop affine TU decompositions for twostage resourceconstrained bmatching problems that have challenging applications in runway utilization of aircraft. Mathematically, the task consists in determining an optimum twostage bipartite bmatching in a graph. The two stages are linked by resource restrictions modeled by specific knapsack constraints. Determining an affine TU decomposition for this problem is reduced to the question of how the incidence matrix of a bipartite graph can be enlarged by appending a submatrix such that the resulting matrix again is TU. Sufficient conditions are derived for the structure of such a submatrix. We apply our findings to twostage bmatching problem with one resource constraint. For several resource constraints, the TU requirements are not met in general. Nevertheless, in case b = 1, we reformulate the problem with one resource constraint per node such that the underlying polytope is integral. This again leads to a reduced number of integrality constraints, when compared to the original formulation. The computational study focuses on the aircraft application. Using stateoftheart MIP solvers, it is shown that, especially for the case with few resource constraints, the reformulated models usually lead to considerably shorter running times, when compared to solving the original formulation. Keywords: mixedinteger programming reformulation, affine TU decomposition, total unimodularity, runway utilization Category 1: Integer Programming ((Mixed) Integer Linear Programming ) Category 2: Combinatorial Optimization Category 3: Applications  OR and Management Sciences (Airline Optimization ) Citation: Download: [PDF] Entry Submitted: 11/09/2020 Modify/Update this entry  
Visitors  Authors  More about us  Links  
Subscribe, Unsubscribe Digest Archive Search, Browse the Repository

Submit Update Policies 
Coordinator's Board Classification Scheme Credits Give us feedback 
Optimization Journals, Sites, Societies  