Mixed integer reformulations of integer programs and the affine TU-dimension of a matrix (Q1646575): Difference between revisions

This article considers the problem of reformulating an integer program as an equivalent program with fewer integer variables, which makes its solution more computationally efficient. The authors begin with an introduction to linear programming and the affine TU-decomposition of a matrix, which is the technique used for the reformulation. The authors then study the properties of the TU-decomposition and several examples are presented. This very interesting paper concludes with a section of the use of the proposed method for the efficient reformulation of many knapsack problems.