Packing and partitioning orbitopes (Q925263): Difference between revisions
From MaRDI portal
Set OpenAlex properties. |
Changed an Item |
||
Property / arXiv ID | |||
Property / arXiv ID: math/0603678 / rank | |||
Normal rank |
Revision as of 18:57, 18 April 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Packing and partitioning orbitopes |
scientific article |
Statements
Packing and partitioning orbitopes (English)
0 references
3 June 2008
0 references
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.
0 references
Integer programming
0 references
Symmetry breaking
0 references
Lexicographic representatives
0 references
packing polytopes
0 references
partitioning polytopes
0 references
graph coloring
0 references