Detecting Orbitopal Symmetries

Timo Berthold () and Marc E. Pfetsch ()
Additional contact information
Timo Berthold: Zuse Institute Berlin
Marc E. Pfetsch: Zuse Institute Berlin

Chapter 70 in Operations Research Proceedings 2008, 2009, pp 433-438 from Springer

Abstract: Summary Symmetries are usually not desirable in integer programming (IP) models, because they derogate the performance of state-of-the-art IP-solvers like SCIP [1]. The reason for this is twofold: Solutions that are equivalent to ones already discovered are found again and again, which makes the search space \unnecessarily large". Furthermore, the bounds obtained from the linear programming (LP) relaxations are very poor, and the LP-solution is almost meaningless for the decision steps of the IP-solving algorithm. Overall, IP-models mostly suffer much more from inherent symmetries than they benefit from the additional structure. Margot [4, 5] and Ostrowski et al. [7, 8] handle symmetries in general IPs, without knowing the model giving rise to the instance. Kaibel et al. [2, 3] took a polyhedral approach to deal with special IP-symmetries. They introduced orbitopes [3], which are the convex hull of 0=1-matrices of size p X q, lexicographically sorted with respect to the columns. For the cases with at most or exactly one 1-entry per row, they give a complete and irredundant linear description of the corresponding orbitopes. These orbitopes can be used to handle symmetries in IP-formulations in which assignment structures appear, such as graph coloring problems; see the next section for an example. All of the above approaches assume that the symmetry has been detected in advance or is known. Therefore, automatic detection of symmetries in a given IP-formulation is an important task. In this paper, we deal with the detection of orbitopal symmetries that arise in the orbitopal approach. While this problem is polynomially equivalent to the graph automorphism problem, whose complexity is an open problem, orbitopal symmetries can be found in linear time, if at least the assignment structure is given. Otherwise we show that the problem is as hard as the graph automorphism problem.

Keywords: Integer Programming; Assignment Structure; Variable Block; Graph Coloring Problem; Block Pair (search for similar items in EconPapers)
Date: 2009
References: Add references at CitEc
Citations:

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:sprchp:978-3-642-00142-0_70

Ordering information: This item can be ordered from
http://www.springer.com/9783642001420

DOI: 10.1007/978-3-642-00142-0_70

Access Statistics for this chapter

More chapters in Springer Books from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().