Parliament seating assignment problems

Bart Vangerven; Dirk Briskorn; Dries R. Goossens; Frits C.R. Spieksma

doi:10.1016/j.ejor.2021.08.002

Parliament seating assignment problems

Bart Vangerven, Dirk Briskorn (Corresponding author), Dries R. Goossens, Frits C.R. Spieksma

Combinatorial Optimization

Onderzoeksoutput: Bijdrage aan tijdschrift › Tijdschriftartikel › Academic › peer review

6 Citaten (Scopus)

127 Downloads (Pure)

Samenvatting

Motivated by evidence that parliament seatings are relevant for decision making, we consider the problem to assign seats in a parliament to members of parliament. We prove that the resulting seating assignment problem is strongly NP-hard in several restricted settings. We present a Mixed Integer Programming formulation of the problem, we describe two families of valid inequalities and we discuss symmetry-breaking constraints. Further, we design a heuristic. Finally, we compare the outcomes of the Mixed Integer Programming formulation with the outcomes of the heuristic in a computational study.

Originele taal-2	Engels
Pagina's (van-tot)	914-926
Aantal pagina's	13
Tijdschrift	European Journal of Operational Research
Volume	296
Nummer van het tijdschrift	3
DOI's	https://doi.org/10.1016/j.ejor.2021.08.002
Status	Gepubliceerd - 1 feb. 2022

Bibliografische nota

Publisher Copyright:
© 2021 Elsevier B.V.

Financiering

The research of Frits C.R. Spieksma was partly funded by the Netherlands Organization for Scientific Research (NWO) through Gravitation grant NETWORKS 024.002.003.

Toegang tot document

10.1016/j.ejor.2021.08.002

published versionDefinitieve gepubliceerde versie, 1,04 MBLicentie: TAVERNE

Andere bestanden en links

Link naar publicatie in Scopus

Citeer dit

@article{aa9eeb76d4a7402ea6c7a4bf87274023,

title = "Parliament seating assignment problems",

abstract = "Motivated by evidence that parliament seatings are relevant for decision making, we consider the problem to assign seats in a parliament to members of parliament. We prove that the resulting seating assignment problem is strongly NP-hard in several restricted settings. We present a Mixed Integer Programming formulation of the problem, we describe two families of valid inequalities and we discuss symmetry-breaking constraints. Further, we design a heuristic. Finally, we compare the outcomes of the Mixed Integer Programming formulation with the outcomes of the heuristic in a computational study.",

keywords = "Combinatorial optimization, Complexity theory, Heuristics, Valid inequalities",

author = "Bart Vangerven and Dirk Briskorn and Goossens, \{Dries R.\} and Spieksma, \{Frits C.R.\}",

note = "Funding Information: The research of Frits C.R. Spieksma was partly funded by the Netherlands Organization for Scientific Research (NWO) through Gravitation grant NETWORKS 024.002.003. ",

year = "2022",

month = feb,

day = "1",

doi = "10.1016/j.ejor.2021.08.002",

language = "English",

volume = "296",

pages = "914--926",

journal = "European Journal of Operational Research",

issn = "0377-2217",

publisher = "Elsevier B.V.",

number = "3",

}

TY - JOUR

T1 - Parliament seating assignment problems

AU - Vangerven, Bart

AU - Briskorn, Dirk

AU - Goossens, Dries R.

AU - Spieksma, Frits C.R.

N1 - Funding Information: The research of Frits C.R. Spieksma was partly funded by the Netherlands Organization for Scientific Research (NWO) through Gravitation grant NETWORKS 024.002.003.

PY - 2022/2/1

Y1 - 2022/2/1

N2 - Motivated by evidence that parliament seatings are relevant for decision making, we consider the problem to assign seats in a parliament to members of parliament. We prove that the resulting seating assignment problem is strongly NP-hard in several restricted settings. We present a Mixed Integer Programming formulation of the problem, we describe two families of valid inequalities and we discuss symmetry-breaking constraints. Further, we design a heuristic. Finally, we compare the outcomes of the Mixed Integer Programming formulation with the outcomes of the heuristic in a computational study.

AB - Motivated by evidence that parliament seatings are relevant for decision making, we consider the problem to assign seats in a parliament to members of parliament. We prove that the resulting seating assignment problem is strongly NP-hard in several restricted settings. We present a Mixed Integer Programming formulation of the problem, we describe two families of valid inequalities and we discuss symmetry-breaking constraints. Further, we design a heuristic. Finally, we compare the outcomes of the Mixed Integer Programming formulation with the outcomes of the heuristic in a computational study.

KW - Combinatorial optimization

KW - Complexity theory

KW - Heuristics

KW - Valid inequalities

UR - http://www.scopus.com/inward/record.url?scp=85114775982&partnerID=8YFLogxK

U2 - 10.1016/j.ejor.2021.08.002

DO - 10.1016/j.ejor.2021.08.002

M3 - Article

AN - SCOPUS:85114775982

SN - 0377-2217

VL - 296

SP - 914

EP - 926

JO - European Journal of Operational Research

JF - European Journal of Operational Research

IS - 3

ER -

Parliament seating assignment problems

Samenvatting

Bibliografische nota

Financiering

Toegang tot document

Andere bestanden en links

Vingerafdruk

Citeer dit