| |||||||||||
| |||||||||||
Set partitioning Description In a country far away, the party of the duke Sark Mevo has
finally beaten the ruling coalition headed by the princess
Reguel Tekris. Mevo wishes to consolidate his position in
the capital, the fourteen quarters of which need to be
grouped to electoral districts. The forecast number of
favorable votes for Mevo and the total number of electors
per quarter are known. All electors must vote and the
winner needs to have the absolute majority. A valid
electoral district is formed by several adjacent quarters
and must have between 30,000 and 100,000 voters. Electoral
districts consisting of a single quarter are permitted if
it has at least 50,000 voters. Nevertheless, Mevo may not
decently define an electoral district solely with quarter
10, since this contains his residence.
Determine a partitioning into five electoral districts
that maximizes the number of seats for Mevo. Should this
cause any difficulties, try a partitioning into six
districts. Further explanation of this example: 'Applications of optimization with Xpress-MP', Section 15.3 'Rigging elections' (j3elect.mos)
Source Files By clicking on a file name, a preview is opened at the bottom of this page.
Data Files partition_calc.mos
(!******************************************************
Mosel Example Problems
======================
file partition_calc.mos
```````````````````````
Include file for data pre-processing
(c) 2008 Fair Isaac Corporation
author: S. Heipcke, 2002, rev. Aug. 2009
*******************************************************!)
declarations
NUMD: integer ! Number of possible districts
RN: range ! Neighboring quarters
NEIGHB: dynamic array(QUARTERS,RN) of integer ! Set of neighboring quarters
POP: array(QUARTERS) of integer ! Number of electors (in 1000)
VOTES: array(QUARTERS) of real ! Number of favorable votes (in 1000)
MINPOP,MAXPOP,MINSINGLE: integer ! Limits on electors per district
end-declarations
initializations from 'partitioning.dat'
NEIGHB POP VOTES MINPOP MAXPOP MINSINGLE
end-initializations
!**** Save a new entry in the list of districts ****
procedure save_distr(sQ: set of integer)
NUMD+=1
forall(q in sQ) DISTR(NUMD,q):=1
end-procedure
!**** Add a neighboring quarter to the current set of quarters ****
procedure add_neighb(toadd:integer, sQ:set of integer)
declarations
nQ: set of integer
end-declarations
nQ:=sQ+{toadd}
if(sum(q in nQ) POP(q) >= MINPOP) then ! Large enough to form distr.
save_distr(nQ)
end-if
forall(p in RN | exists(NEIGHB(toadd,p))) ! Try adding every neighbor
if(sum(q in nQ) POP(q)+POP(NEIGHB(toadd,p))<=MAXPOP) then
add_neighb(NEIGHB(toadd,p), nQ)
end-if
end-procedure
!**** Calculate the list of possible districts ****
procedure calculate_distr
NUMD:=0
forall(q in QUARTERS) do
if (POP(q) >= MINSINGLE and q<>10) then ! Single quarter districts
save_distr({q})
end-if
forall(p in RN | exists(NEIGHB(q,p))) ! Try adding every neighbor
if(POP(q)+POP(NEIGHB(q,p))<=MAXPOP) then
add_neighb(NEIGHB(q,p),{q})
end-if
end-do
forall(d in 1..NUMD) do ! Print the resulting list
write(d,":")
forall(q in QUARTERS) write(if(DISTR(d,q)>0, " "+q, ""))
writeln(" ", (sum(q in QUARTERS | DISTR(d,q)>0) VOTES(q)) *100 /
(sum(q in QUARTERS | DISTR(d,q)>0) POP(q)), "%")
end-do
writeln("Number of possible districts: ",NUMD)
forall(d in 1..NUMD) ! Calculate majorities
MAJ(d):= if(((sum(q in QUARTERS | DISTR(d,q)>0) VOTES(q)) /
(sum(q in QUARTERS | DISTR(d,q)>0) POP(q)) >= 0.5), 1, 0)
finalize(RDIST)
end-procedure
!**** Start the calculation of the list of possible districts ****
calculate_distr
| |||||||||||
| © Copyright 2024 Fair Isaac Corporation. |
