FICO
FICO Xpress Optimization Examples Repository
FICO Optimization Community FICO Xpress Optimization Home
Back to examples browserPrevious exampleNext example

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'

partitioninggr.zip[download all files]

Source Files

Data Files





partitioning_graph.mos

(!******************************************************
   Mosel Example Problems
   ======================

   file partitioning.mos
   `````````````````````
   TYPE:         Partitioning problem
   DIFFICULTY:   4
   FEATURES:     MIP problem, algorithm for data preprocessing; file 
                 inclusion, 3 nested/recursive procedures, working with 
                 sets, `if-then', `forall-do', `exists', `finalize',
                 graphical representation of results
   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 INFO: `Applications of optimization with Xpress-MP', 
                 Section 15.3 `Rigging elections'
   
   (c) 2008 Fair Isaac Corporation
       author: S. Heipcke, 2002, rev. Sep. 2017
*******************************************************!)

model "Rigging elections"
 uses "mmxprs", "mmsvg"

 parameters
  REQD = 6                            ! Required number of districts
 end-parameters

 declarations
  QUARTERS = 1..14                    ! Number of quarters
  RDIST: range                        ! Set of election districts
  
  MAJ: array(RDIST) of integer        ! 1 if majority of votes, 0 otherwise
  DISTR: array(RDIST,QUARTERS) of integer  ! 1 if quarter is in district,
                                           ! 0 otherwise
 end-declarations

 include "partition_calc.mos"

 declarations
  choose: array(RDIST) of mpvar      ! 1 if district chosen, 0 otherwise
 end-declarations

! Objective: number of votes
 Votes:= sum(d in RDIST) MAJ(d)*choose(d)

! Partitioning
 forall(q in QUARTERS) Partition(q):= sum(d in RDIST) DISTR(d,q)*choose(d) = 1
 
! Desired number of districts
 NumDist:= sum(d in RDIST) choose(d) = REQD

 forall(d in RDIST) choose(d) is_binary

! Solve the problem
 maximize(Votes)
 
! Solution printing
 if(getprobstat<>XPRS_OPT) then
  writeln("Problem is infeasible")
 else 
  writeln("Total number of votes: ", getobjval)
  forall(r in RDIST) if getsol(choose(r))>0 then
   write(r, ": ")
   forall(q in QUARTERS) write(if(DISTR(r,q)>0, " "+q, ""))
   writeln(" (", MAJ(r), ")") 
  end-if
 end-if

! Solution drawing
 declarations
  X,Y: array(QUARTERS) of integer        ! x-y-coordinates of quarters
 end-declarations
 
 initializations from 'partitioning.dat'
  [X,Y] as 'POS'
 end-initializations

 svgsetgraphviewbox(0, 0, max(q in QUARTERS) X(q)+10, max(q in QUARTERS) Y(q)+10)
 svgsetgraphscale(2)

 svgaddgroup("Neighbor", "Neighboring quarters", SVG_BLACK)
 svgaddgroup("Fav", "Favorable votes", SVG_GREEN)
 svgaddgroup("Unfav", "Unfavorable votes", SVG_RED)
 forall(q in QUARTERS) do
  svgaddpoint("Neighbor", X(q), Y(q))
  forall(p in QUARTERS | exists(NEIGHB(q,p))) 
   svgaddline("Neighbor", X(q), Y(q), X(NEIGHB(q,p)), Y(NEIGHB(q,p)))
  svgaddtext(if(VOTES(q)/POP(q)>0.5, "Fav", "Unfav"), 
               X(q)+1, Y(q)+1, string(q))
 end-do

 if(getprobstat=XPRS_OPT) then
  forall(r in RDIST) 
   if getsol(choose(r))>0 then
    first:= min(q in QUARTERS | DISTR(r,q)>0) q
    forall(q in QUARTERS | q>first and DISTR(r,q)>0) do
     svgaddline(if(MAJ(r)=1, "Fav", "Unfav"), 
                 X(first), Y(first), X(q), Y(q))
     first:=q
    end-do 
   end-if
 end-if
 
 svgsave("partitioning.svg")
 svgrefresh
 svgwaitclose("Close browser window to terminate model execution.", 1)
end-model

Back to examples browserPrevious exampleNext example