Parliament seating assignment problems

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. (c) 2021 Elsevier B.V. All rights reserved.

Automated summary

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.