Mixed integer reformulations of integer programs and the affine TU-dimension of a matrix

• 成果类型: Article
• 署名作者: Bader, Jorg; Hildebrand, Robert; Weismantel, Robert; Zenklusen, Rico
• 署名单位: Swiss Federal Institutes of Technology Domain; ETH Zurich; International Business Machines (IBM); IBM USA
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-017-1147-2
• 发表日期: 2018
• 页码: 565-584
• 关键词: total unimodularity; DECOMPOSITION; matroids

摘要

We study the reformulation of integer linear programs by means of a mixed integer linear program with fewer integer variables. Such reformulations can be solved efficiently with mixed integer linear programming techniques. We exhibit examples that demonstrate how integer programs can be reformulated using far fewer integer variables. To this end, we introduce a generalization of total unimodularity called the affine TU-dimension of a matrix and study related theory and algorithms for determining the affine TU-dimension of a matrix. We also present bounds on the number of integer variables needed to represent certain integer hulls.