The running time for solving a mixed-integer 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 so-called affine TU decomposition of the underlying constraint matrix. In this work, we develop affine TU decompositions for two-stage resource-constrained b-matching problems that have challenging applications in runway utilization of aircraft. Mathematically, the task consists in determining an optimum two-stage bipartite b-matching 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 two-stage b-matching 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 state-of-the-art 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.
Article
View Mixed-Integer Reformulations of Resource-Constrained Two-Stage Assignment Problems