Extended formulations for column constrained orbitopes

Andreas Schmitt, Christopher Hojny, Marc E. Pfetsch

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademic

Abstract

In the literature, packing and partitioning orbitopes were discussed to handle symmetries that act on variable matrices in certain binary programs. In this paper, we extend this concept by restrictions on the number of $1$-entries in each column. We develop extended formulations of the resulting polytopes and present numerical results that show their effect on the LP relaxation of a graph partitioning problem.
Original languageEnglish
Title of host publicationOperations Research Proceedings 2017
EditorsNatalia Kliewer, Jan Fabian Ehmke, Ralf Borndörfer
Place of PublicationCham
PublisherSpringer
Pages197-203
Number of pages7
ISBN (Electronic)978-3-319-89920-6
ISBN (Print)978-3-319-89919-0
DOIs
Publication statusPublished - 2017
Externally publishedYes
EventInternational Conference of the German Operations Research Society (GOR) - Freie Universiät Berlin, Berlin, Germany
Duration: 6 Sep 20178 Sep 2017

Conference

ConferenceInternational Conference of the German Operations Research Society (GOR)
CountryGermany
CityBerlin
Period6/09/178/09/17

Cite this