The ABC of Apportionment Numeracy:
The Augsburg Bazi Pseudo-Code [Version 2013.07]

by Friedrich Pukelsheim and the Bazi Team, Universität Augsburg


Copyright © 2000-2013 Universität Augsburg

The BAZI program is free software; you may redistribute or modify it under the terms of the Free Software Foundation's GNU General Public License (Version 2, June 1991). If you would like to obtain a paper copy of the GNU General Public License, write to the Free Software Foundation, Inc., 59 Temple Place – Suite 330, Boston, MA 02111-1307, USA.

The BAZI program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for details.


Contents

    DM    Divisor methods for vector problems
    PD Pick-divisor module for output embellishment
    BD Biproportional divisor methods for matrix problems


DM: Divisor methods for vector problems

DM001 #############################################################
DM002 ####### ALGORITHM TO CALCULATE A VECTOR APPORTIONMENT, FOR A
DM003 ####### DIVISOR METHOD THAT IS GIVEN BY ITS SIGNPOST SEQUENCE
DM004 
DM005 ####### Called as: DM[h; v_1..v_ell]
DM006 ####### -> [x; f; Dmin, Dmax, D; muMin, muMax, mu; pt]
DM007 
DM008 ### Input
DM009 v_j >= 0, real (j=1..ell)           # Weights (often: votes)
DM010 h >= 0, integer                     # House size
DM011 s(k) in [k-1,k] (k=1,2,..); s(0)=0  # Signpost sequence
DM012 ### s(k) = k-1/2: the divisor method with standard rounding
DM013 ### s(k,q) = k-1+q: stationary method with parameter q
DM014 ### s(k,p) = {[(k-1)^p+k^p]/2}^(1/p): powermean meth. w.p. p
DM015 a_j = 0, b_j = h, c_j=0 (j=1..ell)  # Default restrictions
DM016 ### Options for third column:
DM017 ### "---" = Dead (default): Do nil, with data or without.
DM018 ### "Min" = Min restrictions a_j: Force x_j >= a_j.
DM019 ### "Max" = Max restrictions b_j: Force x_j <= b_j.
DM020 ### "Range" = Range interval:     Force x_j in [a_j..b_j].
DM021 ### "Dir" = Direct seats c_j:     Calculate overhang seats.
DM022 ### "Sub" = Subtraction c_j:      Calculate discrepancies.
DM023 
DM024 ### Output
DM025 x_j (j=1..ell)                      # Seat numbers
DM026 f_j (j=1..ell)                      # Flags to indicate ties
DM027 c_j (j=1..ell)                      # Third column option
DM028 D, Dmin, Dmax                       # Nice divisor, limits
DM029 mu, muMax, muMin                    # Nice multiplier, limits
DM030 pt                                  # Last plus-tie index,
DM031 ##################################### without ties, pt=0.
DM032 
DM033 ### Check validity of input, feasibility of house size
DM034 IF min_j {v_j, a_j, b_j} < 0  OR    # If input is invalid
DM035    min_j (b_j - a_j) < 0      OR    # of some sort or other,
DM036    max_{j: v_j=0} a_j > 0     OR    # prompt error message
DM037    [s(1)=0 AND min_{j:v_j>0} b_j = 0] THEN
DM038    PROMPT "Invalid weights, restrictions"; ABORT # and abort.
DM039 ENDIF
DM040 IF [h=0 OR max_j v_j=0] THEN        # House size or weights
DM041    x_j=0 (j=1..ell)                 # zero entail zero seats,
DM042    mu = muMin = muMax = 0           # multiplier zero,
DM043    D = Dmin = Dmax = oo             # divisor infinity
DM044    RETURN                           # (just to be safe).
DM045 ENDIF
DM046 IF [s(1)>0 AND h < sum_{j:v_j>0} a_j] OR # Pervious and
DM047    [s(1)=0 AND h < sum_{j:v_j>0} max{a_j,1}] OR # impervious
DM048    h > sum_{j:v_j>0} b_j THEN       # feasibility check.
DM049    PROMPT "NA=Not applicable: Infeasible house size"; RETURN
DM050 ENDIF                               
DM051 
DM052 ### Initialize multiplier, seat numbers, tie flags:
DM053 IF [h > ell/2 AND stationary method with parameter q is used]
DM054    THEN mu = h + (q-1/2)*ell        # Unbiased multiplier,
DM055    ELSE mu = h                      # or default multiplier,
DM056 ENDIF                               # neglecting restrictions
DM057 ### Function signpostRnd(x) takes value k for x < s(k+1) and
DM058 ### k+1 otherwise, where k=DwnRd(x): Initialize restricted
DM059 x_j = med{a_j,signpostRnd(mu*v_j/v_+),b_j} # seat numbers,
DM060 f_j = 0 (j = 1..ell)                # tie flags,
DM061 pt = 0                              # last plus-tie index.
DM062 
DM063 ### Remove discrepancies, if any, recalling s(0)=0:
DM064 ### Empty set min-max-convention: min{}=oo, max{}=0.
DM065 k = 1                               # Start at beginning.
DM066 WHILE [x_+ < h AND k <= ell] DO     # Incrementation needed:
DM067    Dmin = max{v_j/s(x_j+1):s(x_j+1) > 0, x_j < b_j} 
DM068    WHILE [v_k = 0 OR x_k = b_k OR v_k/s(x_k+1) < Dmin]
DM069       DO k=k+1                      # Search candidate
DM070    ENDWHILE                         # component.
DM071    x_k = x_k + 1                    # Increment, but check:
DM072    IF max{v_j/s(x_j+1):s(x_j+1)>0, x_j< b_j} # If lower limit
DM073       > min{v_j/s(x_j):s(x_j)>s(a_j)} # passes upper limit,
DM074       THEN x_k = x_k-1; k = k+1     # Java accuracy artifact.
DM075       ELSE k = 1                    # Else initialize next
DM076    ENDIF                            # incrementation step.
DM077 ENDWHILE
DM078 WHILE [x_+ > h AND k <= ell] DO     # Decrement: Critical
DM079    Dmax = min{v_j/s(x_j):s(x_j)>s(a_j)} # divisor value.
DM080    WHILE [s(x_k) = s(a_k) OR v_k/s(x_k) > Dmax] DO
DM081       k=k+1                         # Have-nots cannot
DM082    ENDWHILE                         # lose a seat.
DM083    x_k = x_k - 1                    # Decrement, but check:
DM084    IF max{v_j/s(x_j+1):s(x_j+1)>0, x_j< b_j} # If lower limit
DM085       > min{v_j/s(x_j):s(x_j)>s(a_j)} # passes upper limit,
DM086       THEN x_k = x_k+1; k = k+1     # Java accuracy artifact.
DM087       ELSE k = 1                    # Else initialize next
DM088    ENDIF                            # decrementation step.
DM089 ENDWHILE
DM090 
DM091 ### Set tie flags and pick secure intervals.
DM092 Dmin = max{v_j/s(x_j+1):s(x_j+1) > 0, x_j < b_j} # Endpoints
DM093 Dmax = min{v_j/s(x_j):s(x_j) > s(a_j)} # of divisor interval.
DM094 IF[Dmin > 0 AND Dmax < oo AND StdRd([Dmax/Dmin-1]*10^15) = 0]
DM095    THEN FOR j=1..ell DO             # Degenerate interval:
DM096       IF [s(x_j+1) > 0 AND x_j < b_j # If j hits Dmin, set
DM097          AND StdRd([v_j/(s(x_j+1)*Dmin) - 1]*10^15)=0] # flag
DM098          THEN f_j=1; pt=j           # + = increment candidate
DM099       ENDIF                         # pt= last plus-tie index
DM100       IF [s(x_j) > s(a_j) AND       # If party j hits Dmax,
DM101          StdRd([v_j/(s(x_j)*Dmax) - 1]*10^15) = 0] # set flag
DM102          THEN f_j=-1                # - = decrement candidate
DM103       ENDIF
DM104    ENDFOR
DM105 ENDIF
DM106 IF pt > 0 THEN                      # If tied, use pt to
DM107    muMin=muMax=mu=s(x_pt+1)/v_pt    # calculate multiplier,
DM108    Dmin =Dmax =D =v_pt/s(x_pt+1)    # divisor.
DM109 ELSE                                # Else first embellish
DM110    PD[1/Dmax, 1/Dmin] -> [muMin, muMax, mu] # multiplier,
DM111    PD[Dmin, Dmax] -> [Dmin, Dmax, D]# then divisor.
DM112 ENDIF
DM113 
DM114 ### Final check before going public
DM115 IF max_{j: v_j=0} x_j > 0       OR  # Zero in, zero out.
DM116    min_j {x_j-a_j, b_j-x_j} < 0 OR  # Verify restrictions,
DM117    |x_+ - h| > 0                OR  # house size.
DM118    max_{j: f_j=0, s(x_j+1)>0, x_j< b_j} # Check divisor:
DM119        [v_j/s(x_j+1) - D] > 0   OR  # Untied weights
DM120    min_{j: f_j=0, s(x_j)>s(a_j)}    # respect divisor to
DM121        [v_j/s(x_j) - D] < 0     OR  # within Java accuracy,
DM122    max_{j: f_j=1, s(x_j+1)>0}       # tied weights only
DM123        [StdRd([v_j/(s(x_j+1)*D) - 1]*10^15)] > 0 OR
DM124    min_{j: f_j=-1, s(x_j)>0}        # to within a relative
DM125        [StdRd([v_j/(s(x_j)*D) - 1]*10^15)] < 0
DM126    THEN ABORT                       # error of 10^(-15).
DM127 ENDIF
DM128 
DM129 ### Output determined by options for third column:
DM130 ### "---" = nil                     # Nothing.
DM131 ### "Min" = a_j                     # Min restrictions.
DM132 ### "Max" = b_j                     # Max restrictions.
DM133 ### "Range" = a_j"-"b_j             # Range interval.
DM134 ### "Dir" = max{0, c_j-x_j}         # Overhang seats.
DM135 ### "Sub" = x_j-c_j                 # Discrepancy.
DM136 RETURN
DM137 #############################################################

PD: Pick-divisor module for output embellishment

PD01 ##############################################################
PD02 ####### ALGORITHM TO DETERMINE A NICE, COMMUNICATABLE DIVISOR
PD03 ####### AND TO CALCULATE SAFE LIMITS FOR THE DIVISOR INTERVAL
PD04
PD05 ####### Called as: PD[Dmin, Dmax] -> [Dmin, Dmax, D]
PD06
PD07 ### Input                            # Input interval limits
PD08 Dmin, Dmax                           # in Java accuracy
PD09
PD10 ### Output                           # Output safe limits
PD11 Dmin, Dmax                           # inside interval,
PD12 D                                    # nice divisor.
PD13 ##############################################################
PD14
PD15 ### Nonregular cases: Illegal input, degenerate interval:
PD16 IF [Dmin > Dmax OR Dmin < 0] THEN ABORT ENDIF # Absurd.
PD17 IF Dmin = Dmax THEN D = Dmax; RETURN ENDIF  # Ties.
PD18 IF Dmax = oo                         # Infinite Dmax: Stop
PD19    THEN IF Dmin=0 THEN D=1; RETURN ENDIF # when Dmin is zero.
PD20    Dmax=10*Dmin; DmaxEqInfty=1       # For positive Dmin,
PD21    ELSE DmaxEqInfty=0                # Dmax is temporarily
PD22 ENDIF                                # set finite, but large.
PD23 
PD24 ### Functions to round a positive number x to k digits
PD25 Size(x) = DwnRd[log10(x)] + 1        # Order of magnitude
PD26 DwnRdDig(x,k) = DwnRd[x*10^{k-Size(x)}] / 10^{k-Size(x)}
PD27 UpRndDig(x,k) = UpRnd[x*10^{k-Size(x)}] / 10^{k-Size(x)}
PD28 StdRdDig(x,k) = StdRd[x*10^{k-Size(x)}] / 10^{k-Size(x)}
PD29 
PD30 ### Regular cases: Round to 6 digits, unless more are needed
PD31 Dbar = (Dmin+Dmax)/2                 # Midpoint of true limits
PD32 k = max{6, Size(Dmin), Size(Dmin)-Size(Dmax-Dmin)+2}
PD33 Dmin = UpRndDig(Dmin,k)              # Round up, into interior
PD34 k = max{6, Size(Dmax), Size(Dmax)-Size(Dmax-Dmin)+2}
PD35 Dmax = DwnRdDig(Dmax,k)              # Rnd down, into interior
PD36 IF Dmin < Dmax THEN                  # Test rounded limits
PD37    k = 0                             # Number of digits
PD38    WHILE k < 16 AND                  # Maximum Java accuracy
PD39       [ StdRdDig(Dbar,k)<=Dmin OR    # Round Dbar to as few
PD40       StdRdDig(Dbar,k)>=Dmax ]       # digits as possible in
PD41       DO k = k+1                     # the divisor interval.
PD42    ENDWHILE
PD43    D = StdRdDig(Dbar,k)              # Round, check, polish:
PD44    IF D < Dmin OR Dmax < D THEN D = Dmax ENDIF
PD45    IF Dmin < StdRd(D) < Dmax THEN D = StdRd(D) ENDIF
PD46 ELSE
PD47    IF Dmin = Dmax THEN D = Dmax      
PD48    ELSE ABORT                        # Should never be true,
PD49    ENDIF                             # but then who knows.
PD50 ENDIF
PD51 IF DmaxEqInfty=1 THEN Dmax=oo ENDIF  # Reset Dmax if needed.
PD52 RETURN
PD53 ##############################################################

BD: Biproportional divisor methods for matrix problems

BD001 #############################################################
BD002 ####### ALGORITHM TO CALCULATE A BIPROPORTIONAL (MATRIX)
BD003 ####### APPORTIONMENT BASED ON A GIVEN DIVISOR METHOD
BD004 
BD005 ### Input for k districts (rows) and ell parties (columns)
BD006 v_{ij}>=0, real   (i=1..k;          # Weight in District i
BD007                    j=1..ell)        # of Party j
BD008 row_i>=0, integer (i=1..k)          # District magnitudes
BD009 col_j>=0, integer (j=1..ell)        # Party seats
BD010 n_{ij} >= 0, int. (i=1..k,j=1..ell) # Third column, optional
BD011 ### Options how to invoke the third column:
BD012 ### "---" = Dead (default): Do nil, with data or without.
BD013 ### "MIN" = Lower bounds for GLOBAL party seat numbers: 
BD014 ###         Force col_j >= max_{i} n_{ij}.
BD015 
BD016 ### Output
BD017 x_{ij} (i=1..k; j=1..ell)           # Seat numbers
BD018 f_{ij} (i=1..k; j=1..ell)           # Tie flags
BD019 Cmin_i, Cmax_i, C_i (i=1..k)        # Row divisors
BD020 Dmin_j, Dmax_j, D_j (j=1..ell)      # Column divisors
BD021 rhoMin_i, rhoMax_i, rho_i (i=1..k)  # Row multipliers
BD022 gamMin_j, gamMax_j, gam_j (j=1..ell)# Column multipliers
BD023 #############################################################
BD024 
BD025 ### Initialization
BD026 h = row_+                           # Total seat number
BD027 IF |h - col_+| > 0                  # Row total must
BD028    THEN ABORT                       # equal column total.
BD029 ENDIF
BD030 FOR i = 1..k AND j = 1..ell DO      # Minimum assignment 
BD031     e_{ij} = 0                      # 0, lest s(1)=0 and
BD032     IF [s(1)=0 AND v_{ij}>0] THEN e_{ij}=1 ENDIF
BD033 ENDFOR                              # v_{ij}>0 force 1.
BD034 FOR i = 1..k AND j = 1..ell DO      # Check whether
BD035    IF row_i < e_{i+} OR             # marginals are
BD036       col_j < e_{+j} THEN           # large enough.
BD037       PROMPT "NA = Not applicable: Prespecified marginals
BD038       are too small to serve all positive weights."; RETURN
BD039    ENDIF                      
BD040 ENDFOR
BD041 SUBROUTINE ExistenceCheck           # See below lines BDE
BD042 
BD043 ### Alternating Scaling (AS) algorithm
BD044 StepAS = 0                          # Initialize counter,
BD045 a_i = 1 (i=1..k)                    # row divisors,
BD046 b_j = 1 (j=1..ell)                  # column divisors,
BD047 Fcount = h                          # current flaw count,
BD048 Fpenult = h + 1                     # penultimate count.
BD049 WHILE 0 < Fcount < Fpenult DO       # While progressing:
BD050    Fpenult = Fcount                 # Store flaw count.
BD051    StepAS = StepAS + 1              # Next step.
BD052    FOR i = 1..k DO                  # Odd steps: Rows.
BD053       DM[row_i; v_{i1}/(a_i*b_1) .. v_{i,ell}/(a_i*b_ell)] ->
BD054       [m;f;Cmin_i,Cmax_i,C_i;rhoMin_i,rhoMax_i,rho_i;ptr_i]
BD055 ### Divisor update, as checked in menu "Edit>Biprop.Alg...":
BD056 "mdpt": a_i = a_i*C_i
BD057 "extr": either a_i = a_i*Cmin_i, or else a_i = a_i*Cmax_i 
BD058 "unif": a_i = a_i*(Cmax_i-Cmin_i)*u, with u uniform(0,1)
BD059    ENDFOR
BD060    Fcol_j = x_{+j}-col_j (j=1..ell) # Column j flaw counts
BD061    SUBROUTINE TT-Algorithm          # See below lines BDT
BD062    Fcount = sum_j max{0, Fcol_j}    # Global flaw count
BD063    IF Fcount > 0 THEN               # Still flaws left?
BD064       StepAS = StepAS + 1           # Next step
BD065       FOR j = 1..ell DO             # Even steps: Columns.
BD066         DM[col_j; v_{1j}/(a_1*b_j)..v_{kj}/(a_k*b_j)] ->
BD067         [m;f;Dmin_j,Dmax_j,D_j;gamMin_j,gamMax_j,gam_j;ptc_j]
BD068         b_j = b_j*D_j               # Divisor update, same
BD069       ENDFOR                        # version as in BD056-8.
BD070       Frow_i=x_{i+}-row_i (i= 1..k) # Row i flaw count
BD071       SUBROUTINE TT-Algorithm       # See below lines BDT
BD072       Fcount = sum_i max{0, Frow_i} # Global flaw count
BD073    ENDIF                            
BD074 ENDWHILE                            # When AS stalls,
BD075 
BD076 ### Tie-and-Transfer (TT) algorithm # switch to TT.
BD077 StepTT = Fcount                     # Residual TT workload
BD078 WHILE Fcount > 0 DO                 # Loop until job is done.
BD079    SUBROUTINE TT-Algorithm          # See below lines BDT
BD080 ENDWHILE
BD081 
BD082 ### Find last plus-tie indices, or else unflag
BD083 FOR i = 1..k DO                     # If row i is tied, find
BD084    IF [min_j f_{ij} = -1 AND max_j f_{ij} = 1] THEN
BD086       ptr_i = max{j: f_{ij}=1}      # last col. with plus-tie
BD087    ELSE
BD088       f_{ij} = 0 (j=1,..,ell)       # Else unflag,
BD089       ptr_i = 0                     # set tie indicator nil.
BD090    ENDIF
BD091 ENDFOR
BD092 FOR j = 1..ell DO                   # Same with columns.
BD093    IF [min_i f_{ij} = -1 AND max_i f_{ij} = 1] THEN
BD094       ptc_j = max{i: f_{ij}=1}
BD095    ELSE
BD096       f_{ij} = 0 (i=1..k)
BD097       ptc_j = 0
BD098    ENDIF
BD099 ENDFOR
BD100 
BD101 ### Keep unflagging while remaining ties are only one-way
BD102 checkFlags = (max_i ptr_i) + (max_j ptc_j)
BD103 WHILE checkFlags > 0 DO             # Keep checking while
BD104    checkFlags = 0
BD105    FOR i = 1..k DO                  # in some row i all
BD106       IF max_j |f_{ij}| = 1 AND     # flags, being of one
BD107          [ min_j f_{ij}>=0 OR max_j f_{ij}<=0 ] THEN
BD108          f_{ij} = 0 (j=1..ell)      # sign, are removed.
BD109          checkFlags = 1
BD110       ENDIF
BD111    ENDFOR
BD112    FOR j = 1..l DO                  # Same with columns.
BD113       IF max_i |f_{ij}| = 1 AND
BD114          [ min_i f_{ij}>=0 OR max_i f_{ij}<=0 ] THEN
BD115          f_{ij} = 0 (i=1..k) 
BD116          checkFlags = 1
BD117       ENDIF
BD118    ENDFOR
BD119 ENDWHILE
BD120 
BD121 ### Find median column divisor, standardize.
BD122 IF max_{ij} f_{ij} = 1 THEN         # Columns with ties,
BD123    med = Median of only those b_j with max_i f_{ij} = 1
BD124 ELSE IF max_j ptc_j > 0 THEN        # or tied columns,
BD125    med = Median of only those b_j with ptc_j > 0
BD126 ELSE                                # or columns with
BD127    med = Median of only those b_j with c_j > 0
BD128 ENDIF ENDIF                         # positive marginals.
BD129 FOR j = 1..ell DO                   # Standardize columns
BD130    IF [max_{ij}f_{ij} = 1 AND b_j = med] THEN # divisors D_j:
BD131       gamMin_j=gamMax_j=gam_j=1     # Set degenerate limits,
BD132       Dmin_j  =Dmax_j  =D_j  =1     # values.
BD133    ELSE                             # Else pick nice numbers.
BD134       DM[col_j; v_{1j}/(a_1*med)..v_{kj}/(a_k*med)] ->
BD135       [nil;nil;Dmin_j,Dmax_j,D_j;gamMin_j,gamMax_j,gam_j;nil]
BD136    ENDIF
BD137 ENDFOR
BD138 FOR i = 1..k DO                     # Adjust row divisors C_i
BD139    t1 = max{j: |f_{ij}|=1=D_j}      # t1 = 0, unless
BD140    IF t1 > 0 THEN                   # tie meets divisor 1:
BD141   rhoMin_i=rhoMax_i=rho_i=s(x_{i,t1}-(1-f_{i,t1})/2)/v_{i,t1}
BD142       Cmin_i=Cmax_i=C_i=v_{i,t1}/s(x_{i,t1}-(1-f_{i,t1})/2)
BD143    ELSE                             # Else pick nice numbers.
BD144       DM[row_i; v_{i1}/D_1..v_{i,ell}/D_ell] ->
BD145       [nil;nil;Cmin_i,Cmax_i,C_i;rhoMin_i,rhoMax_i,rho_i;nil]
BD146    ENDIF
BD147 ENDFOR
BD148 
BD149 ### Final check before going public:
BD150 IF max_{i,j:v_{ij}=0} x_{ij} > 0 OR # Zero in, zero out.
BD151    max_i|x_{i+} - row_i|>0 OR       # Check row fits,
BD152    max_j|x_{+j} - col_j|>0 OR       # column fits.
BD153    max_{i,j: f_{ij}=0;s(x_{ij})>0}  # Untied weights
BD154        v_{ij}/s(x_{ij}) - C_i*D_j > 0 OR
BD155    min_{i,j: f_{ij}=0;s(x_{ij}-1)>0}# obey limits strictly,
BD156        v_{ij}/s(x_{ij}-1) - C_i*D_j < 0 OR
BD157    max_{i,j: f_{ij}=1;s(x_{ij})>0}  # tied weights only
BD158       StdRd( [v_{ij}/(s(x_{ij})*C_i*D_j)-1]*10^15 / 2) > 0 OR
BD159    min_{i,j: f_{ij}=-1;s(x_{ij}-1)>0} # to within 15 digits.
BD160      StdRd( [v_{ij}/(s(x_{ij}-1)*C_i*D_j)-1]*10^15 / 2) < 0
BD161   THEN ABORT                       # Never come here!
BD162 ENDIF
BD163 RETURN
BD164 #############################################################

BDE01 #############################################################
BDE02 SUBROUTINE ExistenceCheck
BDE03 V = { SOURCE, D_1..D_k, P_1..P_ell, SINK } # Set of vertices
BDE04 u(v,w) = 0, for all v,w in V        # Capacity defaults
BDE05 ### Recall e_{ij}=0, lest s(1)=0 and v_{ij}>0 force e_{ij}=1:
BDE06 FOR i = 1..k AND j = 1..ell DO      # Problem-specific
BDE07    u(SOURCE,D_i) = row_i - e_{i+}   # upper capacities, to
BDE08    IF v_{ij} > 0 THEN u(D_i,P_j) = h - e_{++} ENDIF
BDE09    u(P_j,SINK) = col_j - e_{+j}     # build capacitated
BDE10 ENDFOR                              # graph G = (V, A).
BDE11 A = { (v,w) in VxV : u(v,w) > 0 }   # Set of arcs
BDE12 In graph G, calculate maximum flow x from SOURCE to SINK
BDE13 IF x(SOURCE,D_+) < h - e_{++} THEN  # MaxFlow-MinCut Theorem
BDE14    ### Build nodeset W of the MinCut induced by MaxFlow x:
BDE15    W = {SOURCE}                     # Current W
BDE16    Wpenult = emptySet               # Penultimate W
BDE17    WHILE W NOTEQUAL Wpenult DO      # While set W is growing,
BDE18      Wpenult = W                    # enlarge W by node v if
BDE19      FOR ALL w in W AND v in V-W DO # (w,v) is nonsaturated,
BDE20         IF x(w,v) < u(w,v) OR x(v,w) > 0 THEN W = W+{v} ENDIF
BDE21      ENDFOR                         # of if flow on (v,w)
BDE22    ENDWHILE                         # is positive.
BDE23    J = {j=1..ell : P_j is in W}     # Parties in MinCut,
BDE24    I = {i=1..k : sum_{j in J} v_{ij} > 0} # linked districts.
BDE25    K = {j' not in J : sum_{i in I} e_{ij'} > 0} # Only s(1)=0
BDE26    PROMPT "NA = Not applicable: The biproportional method is
BDE27    not applicable since the cumulative number of seats in
BDE28    districts [i in I] is smaller ([row_I]) than what is
BDE29    needed there by parties [j in J+K] ([col_J + e_{I, K}])."
BDE30    ABORT           # row_I = sum_{i in I} row_i; col_J = dto.
BDE31 ENDIF              # e_{I, K} = sum_{i in I, j' in K} e_{ij'}
BDE32 #############################################################

BDTT1 #############################################################
BDTT2 SUBROUTINE Tie-and-Transfer algorithm
BDTT3 See M.Balinski/G.Demange: Math. Programming 45 (1989) 193-210
BDTT4 #############################################################

Back to top