Cyclic group and knapsack facets (Q1424275)

This article considers the problem of finding facet-defining inequalities for group relaxations of knapsack problems. A group relaxation of an integer program can be found by removing the non-negativity constraints on the basic variables of its linear programming relaxation. The article begins with an introduction to cyclic group relaxations and the master cyclic group problem for general integer programs. In the third section, a classification of cyclic group facets is presented, focusing on {mappings} and {seeds}, which are used to generate cuts (the mixed integer cut being one of them). In sections 4 and 5 the knapsack polytope is studied, and the relationship between the master cyclic group problem and the master equality knapsack polytope is examined. Sections 6 and 7 concentrate on knapsack and knapsack cover facets. A summary of the facets in tabular form and detailed proofs of lemmas are presented in the annexes.