Cyclic group blocking polyhedra (Q1949270): Difference between revisions

This article considers the cyclic group problem in combinatorial optimization. The authors begin with an introduction to the properties of the cyclic group polyhedron defined by the problem constraints, the properties of its facets and the associated blocking polyhedron. In the second section the authors describe a minimal representation of the polytope defined by the cyclic group facets. This is achieved by using a triple system which serves as a building block for solution vectors of higher length. The authors then consider the shooting linear problem which aims to find the important facets of the polytope, which they apply to the knapsack subadditive polytope and obtain a pattern of facets which absorb over half of the hits in the shooting experiment. The article concludes with suggestions for a future work and a useful list of references.