In this paper, we show that operations research methods can be successfully applied to support decision-making in politics on the case study of the apportionment of seats in the European Parliament. The related political constraints and assumptions are quantitatively described and the optimization problem is formulated. On this basis, it is revealed that the current composition of the European Parliament as well as some intuitive propositions do not respect degressive proportionality as far as it was assumed. Nevertheless, our algorithm allows us to find better solutions, and among them, there is only one best allocation, which respects degressive proportionality as far as possible, according to the well known and often applied measures. Namely, over 9 thousands allocations consistent with the political requirement “nobody gains and nobody loses more than one” are referred to over 5.4 millions degressively proportional solutions, and only one allocation is revealed to be the best for all defined criteria under given populations of countries.