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

Onderzoeksoutput: Hoofdstuk in Boek/Rapport/Congresprocedure › Conferentiebijdrage › Academic

1 Downloads (Pure)

Samenvatting

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.

Originele taal-2	Engels
Titel	Operations Research Proceedings 2017
Redacteuren	Natalia Kliewer, Jan Fabian Ehmke, Ralf Borndörfer
Plaats van productie	Cham
Uitgeverij	Springer
Pagina's	197-203
Aantal pagina's	7
ISBN van elektronische versie	978-3-319-89920-6
ISBN van geprinte versie	978-3-319-89919-0
DOI's	https://doi.org/10.1007/978-3-319-89920-6_28
Status	Gepubliceerd - 2017
Extern gepubliceerd	Ja
Evenement	International Conference of the German Operations Research Society (GOR) - Freie Universiät Berlin, Berlin, Duitsland Duur: 6 sep. 2017 → 8 sep. 2017

Congres

Congres	International Conference of the German Operations Research Society (GOR)
Land/Regio	Duitsland
Stad	Berlin
Periode	6/09/17 → 8/09/17

Toegang tot document

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

Citeer dit

@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

Samenvatting

Congres

Toegang tot document

Vingerafdruk

Citeer dit