Parliament seating assignment problems
| Autor: | Dries Goossens, Bart Vangerven, Dirk Briskorn, Frits C. R. Spieksma |
|---|---|
| Přispěvatelé: | Combinatorial Optimization 1 |
| Jazyk: | angličtina |
| Rok vydání: | 2022 |
| Předmět: |
Mathematical optimization
Information Systems and Management Combinatorial optimization General Computer Science Computer science Parliament Heuristic media_common.quotation_subject Complexity theory Management Science and Operations Research Industrial and Manufacturing Engineering Valid inequalities Business and Economics Modelling and Simulation Modeling and Simulation Heuristics Assignment problem Integer programming media_common |
| Zdroj: | EUROPEAN JOURNAL OF OPERATIONAL RESEARCH European Journal of Operational Research, 296(3), 914-926. Elsevier |
| ISSN: | 0377-2217 1872-6860 |
| DOI: | 10.1016/j.ejor.2021.08.002 |
| Popis: | 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect