% Encoding: UTF-8
@COMMENT{BibTeX export based on data in FAU CRIS: https://cris.fau.de/}
@COMMENT{For any questions please write to cris-support@fau.de}
@misc{faucris.245023378,
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) 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.},
author = {Hupp, Lena and Kapolke, Manu and Liers, Frauke and Martin, Alexander and Weismantel, Robert},
faupublication = {yes},
keywords = {mixed-integer programming reformulation; affine TU decomposition; total unimodularity; runway utilization},
peerreviewed = {automatic},
title = {{Mixed}-{Integer} {Reformulations} of {Resource}-{Constrained} {Two}-{Stage} {Assignment} {Problems}},
url = {http://www.optimization-online.org/DB{\_}HTML/2020/11/8103.html},
year = {2020}
}