Optimization Online


Mixed-Integer Reformulations of Resource-Constrained Two-Stage Assignment Problems

Lena Hupp(lena.hupp***at***siemens.com)
Manu Kapolke(manu.kapolke***at***fau.de)
Frauke Liers(frauke.liers***at***fau.de)
Alexander Martin(alexander.martin***at***fau.de)
Robert Weismantel(robert.weismantel***at***ifor.math.ethz.ch)

Abstract: 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) 565584] 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.

Keywords: mixed-integer 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 )


Download: [PDF]

Entry Submitted: 11/09/2020
Entry Accepted: 11/09/2020
Entry Last Modified: 11/09/2020

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society