Packing and partitioning orbitopes (Q925263)

The article introduces orbitopes as a new way of tackling symmetries in 0/1 programming. Orbitopes characterize the lexicographically maximal 'solutions' with respect to symmetries arising from a group acting on the columns of the problem matrix. The authors study the application to packing and partition problems in particular and conduct a thorough investigation of the polyhedral properties of the associated orbitopes for the symmetric and the cyclic group. It is shown that in this case linear optimization can be performed efficiently over the orbitopes for packing and partition problems thus motivating the study of the polyhedral description. The authors provide complete linear descriptions for packing and partitioning orbitopes for both groups. In the basic case where the group action is cyclic, the description is totally unimodular. In the more complicated case where the group action is symmetric the linear description involves special inequalities, so called shifted column inequalities, whose associated separation problem can be solved efficiently.