IDEAS home Printed from https://ideas.repec.org/a/eee/ejores/v296y2022i3p914-926.html
   My bibliography  Save this article

Parliament seating assignment problems

Author

Listed:
  • Vangerven, Bart
  • Briskorn, Dirk
  • Goossens, Dries R.
  • Spieksma, Frits C.R.

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.

Suggested Citation

  • Vangerven, Bart & Briskorn, Dirk & Goossens, Dries R. & Spieksma, Frits C.R., 2022. "Parliament seating assignment problems," European Journal of Operational Research, Elsevier, vol. 296(3), pages 914-926.
    • Handle: RePEc:eee:ejores:v:296:y:2022:i:3:p:914-926
    DOI: 10.1016/j.ejor.2021.08.002
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S037722172100669X
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.ejor.2021.08.002?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Maarten Oosten & Jeroen H. G. C. Rutten & Frits C. R. Spieksma, 2007. "Disconnecting graphs by removing vertices: a polyhedral approach," Statistica Neerlandica, Netherlands Society for Statistics and Operations Research, vol. 61(1), pages 35-60, February.
    2. Benati, Stefano & Puerto, Justo & Rodríguez-Chía, Antonio M., 2017. "Clustering data that are graph connected," European Journal of Operational Research, Elsevier, vol. 261(1), pages 43-53.
    3. Nikolaj Harmon & Raymond Fisman & Emir Kamenica, 2019. "Peer Effects in Legislative Voting," American Economic Journal: Applied Economics, American Economic Association, vol. 11(4), pages 156-180, October.
    4. Douglas M. King & Sheldon H. Jacobson & Edward C. Sewell & Wendy K. Tam Cho, 2012. "Geo-Graphs: An Efficient Model for Enforcing Contiguity and Hole Constraints in Planar Graph Partitioning," Operations Research, INFORMS, vol. 60(5), pages 1213-1228, October.
    5. Saia, Alessandro, 2018. "Random interactions in the Chamber: Legislators' behavior and political distance," Journal of Public Economics, Elsevier, vol. 164(C), pages 225-240.
    Full references (including those not matched with items on IDEAS)

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Ximeng Fang & Sven Heuser & Lasse S. Stötzer, 2023. "How In-Person Conversations Shape Political Polarization: Quasi-Experimental Evidence from a Nationwide Initiative," ECONtribute Discussion Papers Series 270, University of Bonn and University of Cologne, Germany.
    2. Matthew Lowe & Donghee Jo, 2021. "Legislature Integration and Bipartisanship: A Natural Experiment in Iceland," CESifo Working Paper Series 9452, CESifo.
    3. Bolletta, Ugo, 2021. "A model of peer effects in school," Mathematical Social Sciences, Elsevier, vol. 114(C), pages 1-10.
    4. Nathan Canen & Ko Sugiura, 2022. "Inference in Linear Dyadic Data Models with Network Spillovers," Papers 2203.03497, arXiv.org, revised Jun 2023.
    5. Alexander Veremyev & Oleg A. Prokopyev & Eduardo L. Pasiliao, 2014. "An integer programming framework for critical elements detection in graphs," Journal of Combinatorial Optimization, Springer, vol. 28(1), pages 233-273, July.
    6. Haase, Knut & Müller, Sven, 2014. "Upper and lower bounds for the sales force deployment problem with explicit contiguity constraints," European Journal of Operational Research, Elsevier, vol. 237(2), pages 677-689.
    7. Chad P. Bown & Paola Conconi & Aksel Erbahar & Lorenzo Trimarchi, 2020. "Trade Protection along Supply Chains," CESifo Working Paper Series 8812, CESifo.
    8. Benati, Stefano & Ponce, Diego & Puerto, Justo & Rodríguez-Chía, Antonio M., 2022. "A branch-and-price procedure for clustering data that are graph connected," European Journal of Operational Research, Elsevier, vol. 297(3), pages 817-830.
    9. Garro, Haritz, 2020. "The Role of Connections in Congressional Lawmaking," SocArXiv efnrq, Center for Open Science.
    10. Alessandro Avellone & Stefano Benati & Rosanna Grassi & Giorgio Rizzini, 2022. "On Finding the Community with Maximum Persistence Probability," Papers 2206.10330, arXiv.org.
    11. Calvino, José J. & López-Haro, Miguel & Muñoz-Ocaña, Juan M. & Puerto, Justo & Rodríguez-Chía, Antonio M., 2022. "Segmentation of scanning-transmission electron microscopy images using the ordered median problem," European Journal of Operational Research, Elsevier, vol. 302(2), pages 671-687.
    12. Healy, Patrick & Jozefowiez, Nicolas & Laroche, Pierre & Marchetti, Franc & Martin, Sébastien & Róka, Zsuzsanna, 2024. "A branch-and-cut algorithm for the connected max-k-cut problem," European Journal of Operational Research, Elsevier, vol. 312(1), pages 117-124.
    13. Brice Romuald Gueyap Kounga, 2023. "Nonparametric Regression with Dyadic Data," Papers 2310.12825, arXiv.org.
    14. Rota Bulò, Samuel & Pelillo, Marcello, 2017. "Dominant-set clustering: A review," European Journal of Operational Research, Elsevier, vol. 262(1), pages 1-13.
    15. Nikolaj Harmon & Raymond Fisman & Emir Kamenica, 2019. "Peer Effects in Legislative Voting," American Economic Journal: Applied Economics, American Economic Association, vol. 11(4), pages 156-180, October.
    16. D. M. King & S. H. Jacobson & E. C. Sewell, 2018. "The geo-graph in practice: creating United States Congressional Districts from census blocks," Computational Optimization and Applications, Springer, vol. 69(1), pages 25-49, January.
    17. T. N. Dinh & M. T. Thai & H. T. Nguyen, 2014. "Bound and exact methods for assessing link vulnerability in complex networks," Journal of Combinatorial Optimization, Springer, vol. 28(1), pages 3-24, July.
    18. Han, Jialin & Hu, Yaoguang & Mao, Mingsong & Wan, Shuping, 2020. "A multi-objective districting problem applied to agricultural machinery maintenance service network," European Journal of Operational Research, Elsevier, vol. 287(3), pages 1120-1130.
    19. Ningji Wei & Jose L. Walteros & Foad Mahdavi Pajouh, 2021. "Integer Programming Formulations for Minimum Spanning Tree Interdiction," INFORMS Journal on Computing, INFORMS, vol. 33(4), pages 1461-1480, October.
    20. Camacho-Collados, M. & Liberatore, F. & Angulo, J.M., 2015. "A multi-criteria Police Districting Problem for the efficient and effective design of patrol sector," European Journal of Operational Research, Elsevier, vol. 246(2), pages 674-684.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:eee:ejores:v:296:y:2022:i:3:p:914-926. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Catherine Liu (email available below). General contact details of provider: http://www.elsevier.com/locate/eor .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.