Name
Title | ||
|---|---|---|
Mixed Integer Reformulations of Integer Programs and the Affine TU-dimension of a Matrix |
Abstract | ||
|---|---|---|
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. |
Year | DOI | Venue |
|---|---|---|
2018 | 10.1007/s10107-017-1147-2 | Math. Program. |
Keywords | Field | DocType |
Integer programming,Master knapsack problem,Total unimodularity,90C10 Integer programming,90C11 Mixed integer programming | Discrete mathematics,Mathematical optimization,Combinatorics,Table of Gaussian integer factorizations,Branch and cut,Branch and price,Integer points in convex polyhedra,Integer programming,Prime factor,Unimodular matrix,Highly cototient number,Mathematics | Journal |
Volume | Issue | ISSN |
169 | 2 | 0025-5610 |
Citations | PageRank | References |
0 | 0.34 | 16 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| jorg bader | 1 | 0 | 0.34 |
| Robert Hildebrand | 2 | 69 | 7.82 |
| Robert Weismantel | 3 | 964 | 90.05 |
| Rico Zenklusen | 4 | 307 | 33.70 |