Mixed integer reformulations of integer programs and the affine TU-dimension of a matrix (Q1646575)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Mixed integer reformulations of integer programs and the affine TU-dimension of a matrix |
scientific article |
Statements
Mixed integer reformulations of integer programs and the affine TU-dimension of a matrix (English)
0 references
25 June 2018
0 references
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.
0 references
integer programming
0 references
knapsack problem
0 references
total unimodularity
0 references
mixed integer reformulation
0 references
0 references