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.
| DM | Divisor methods for vector problems |
| PD | Pick-divisor module for output embellishment |
| BD | Biproportional divisor methods for matrix 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 #############################################################
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 ##############################################################
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 #############################################################