Extended formulations for column constrained orbitopes

Andreas Schmitt; Christopher Hojny; Marc E. Pfetsch

doi:10.1007/978-3-319-89920-6_28

Extended formulations for column constrained orbitopes

Andreas Schmitt, Christopher Hojny, Marc E. Pfetsch

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic

1 Downloads (Pure)

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 language	English
Title of host publication	Operations Research Proceedings 2017
Editors	Natalia Kliewer, Jan Fabian Ehmke, Ralf Borndörfer
Place of Publication	Cham
Publisher	Springer
Pages	197-203
Number of pages	7
ISBN (Electronic)	978-3-319-89920-6
ISBN (Print)	978-3-319-89919-0
DOIs	https://doi.org/10.1007/978-3-319-89920-6_28
Publication status	Published - 2017
Externally published	Yes
Event	International Conference of the German Operations Research Society (GOR) - Freie Universiät Berlin, Berlin, Germany Duration: 6 Sept 2017 → 8 Sept 2017

Conference

Conference	International Conference of the German Operations Research Society (GOR)
Country/Territory	Germany
City	Berlin
Period	6/09/17 → 8/09/17

Access to Document

10.1007/978-3-319-89920-6_28

Cite this

@inproceedings{d677f25c38d44c668f348cb11b1a96a8,

title = "Extended formulations for column constrained orbitopes",

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.",

author = "Andreas Schmitt and Christopher Hojny and Pfetsch, {Marc E.}",

year = "2017",

doi = "10.1007/978-3-319-89920-6_28",

language = "English",

isbn = "978-3-319-89919-0",

pages = "197--203",

editor = "Natalia Kliewer and Ehmke, {Jan Fabian} and Ralf Bornd{\"o}rfer",

booktitle = "Operations Research Proceedings 2017",

publisher = "Springer",

address = "Germany",

note = "International Conference of the German Operations Research Society (GOR) ; Conference date: 06-09-2017 Through 08-09-2017",

}

TY - GEN

T1 - Extended formulations for column constrained orbitopes

AU - Schmitt, Andreas

AU - Hojny, Christopher

AU - Pfetsch, Marc E.

PY - 2017

Y1 - 2017

N2 - 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.

AB - 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.

U2 - 10.1007/978-3-319-89920-6_28

DO - 10.1007/978-3-319-89920-6_28

M3 - Conference contribution

SN - 978-3-319-89919-0

SP - 197

EP - 203

BT - Operations Research Proceedings 2017

A2 - Kliewer, Natalia

A2 - Ehmke, Jan Fabian

A2 - Borndörfer, Ralf

PB - Springer

CY - Cham

T2 - International Conference of the German Operations Research Society (GOR)

Y2 - 6 September 2017 through 8 September 2017

ER -

Extended formulations for column constrained orbitopes

Abstract

Conference

Access to Document

Fingerprint

Cite this