Mixed Integer Reformulations of Integer Programs and the Affine TU-dimension of a Matrix

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...

Full description

Saved in:
Bibliographic Details
Published in:arXiv.org 2017-04
Main Authors: Bader, Jörg, Hildebrand, Robert, Weismantel, Robert, Zenklusen, Rico
Format: Article
Language:English
Subjects:
Algorithms
Hulls
Integer programming
Linear programming
Mathematical analysis
Matrix methods
Mixed integer
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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 \emph{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.
ISSN:2331-8422