REDISTRICTING TO MAXIMIZE THE PRESERVATION OF POLITICAL BOUNDARIES John R. Birge Technical Report 82-12 Department of Industrial and Operations Engineering The University of Michigan Ann Arbor, Michigan 48109 August 1982

REDISTRICTING TO MAXIMIZE THE PRESERVATION OF POLITICAL BOUNDARIES John R. Birge Department of Industrial and Operations Engineering The University of Michigan Ann Arbor, Michigan 48109 Abstract Redefining legislative districts is a task undertaken by the states after each census in order to insure equitable representation. Many criteria have been proposed as objectives in forming districts but specific definitions of an optimal plan have not been enforced. In attempting to eliminate political concerns from the effort, the Michigan Supreme Court defined criteria based on the preservation of county and municipality borders. A quadratic programming formulation is given for this problem, and a heuristic solution procedure is proposed. Keywords: Government, Networks/Graphs, Quadratic Programming.

1. Introduction In Reynolds v. Sims [11], the United States Supreme Court ruled that the states should define the boundaries of legislative districts according to decennial census data in order not to violate the "one person, one vote" rule. The state legislatures undertake this redistricting activity and generally develop politically partisan plans. Avoiding political considerations becomes very difficult because many objectives may be used to justify alternative plans. The following criteria are examples of those considered in evaluating redistricting plans: 1) population euality: The districts are selected so as not to deviate beyond some limit from a mean population; 2) compactness: The districts are composed of nearby regions, being nearly square or nearly circular; 3) contiguity: The districts are constructed of contiguous regions; 4) political boundary integrity: The districts should preserve political boundaries as much as possible. Contiguity and some standard of population equality are most frequently considered in redistricting plans. Possible dissolution of minority voting strength is also considered and can be challenged in court. Gerrymandering, however, is still considered seriously by the courts even when supposedly nonpartisan equally populous districts have been constructed (Engstrom [2]). On challenges of redistricting plans based on violation of equal population ("one person - one vote"), the Supreme Court has considered plans

-2 - with less than a 10 percent (of the mean district population) deviation from smallest to largest population district as essentially having equal population districts. In cases where the deviation is greater than 10 percent the states should show some justification for the deviation (Guida [5]). The court has allowed up to a 16.4 percent deviation given the states' need to maintain existing political unit boundaries (Mahan v. Howell [7]). Many optimization methods for redistricting have been considered with the goal of creating as nearly equally populous districts as possible. Garfinkel and Nemhauser [4] proposed an algorithm for minimizing population deviation by generating all possible districts, Forrest [3] developed a heuristic method of repeatedly dividing regions into equipopulous districts until the desired number of districts have been achieved. Other methods consider compactness and additional criteria. Weaver and Hess [14] used a warehouse location model to create districts by starting with a group of district centers, assigning regions to the centers while maintaining populations within bounds and then moving the centers to the population centroids of the new districts. When no further improvement is made, the algorithm stops. Nagel [10] considered several criteria in his switching algorithm for trading along the borders of existing districts in order to improve a weighted objective of any of the criteria, population equality, compactness, or other political goals. The advent of these and other methods was hoped to alleviate the problems inherent in partisan choices of districts, The problems are generally so complex, however, that finding "the optimal" plan is impossible. The speed that computers bring to evaluating and constructing plans has indeed made it easier for partisan groups to generate plans according to

-3 - their own desires (Torricelli and Porter t13]). Several suggestions to remedy this situation have been made. Stern [12] proposed to use a strict mathematical definition of compactness as the sum of the areas that are within a circle circumscribing a district but outside of that district, Adams [1] suggested that redistricting be handled by an independent federal committee and that the maintenance of political boundaries be the second most important criterion to population equality. The State of Michigan Supreme Court t8] attempted to avoid the problems of political interests in redistricting by defining a strict set of criteria to be used in developing redistricting plans for the state legislature. The main emphasis of these criteria falls on the integrity of political boundaries. The rules in order of importance are: 1) To miminize the number of county lines broken, consistent with a population deviation of less than 16.4% (91.8% to 108.2% of the mean district population); 2) To minimize the number of townships used in breaking county lines; 3) To minimize the number of city and township lines broken; 4) In cities and townships with more than one representative, to achieve maximum compactness within a population deviation of 4% among districts in that municipality. These criteria are consistesnt with courts opinion in Mahan v, Howell [7] that preserving political boundaries is a legitimate concern of the states. The criteria define the problem more clearly and make fewer partisan

-4 - choices possible, In the next section, we will formulate the problem of minimizing the number of political boundaries broken as a quadratic program. In Section 3, a heuristic solution procedure for this nonconvex problem is proposed and the results for an implementation on the Michigan Senate are presented. 2. Problem Formulation We will consider districts as composed of county units. A district is represented as a connected directed graph composed of arcs (i,j) representing the contiguity of districts i and j, Decision variables are Yik = q, if a fraction q of county i is in district k; xijk = q, if a fraction q of county i is in district k and at least a fraction q of county j adjacent to i is in district k, Parameters of the problem are D - the number of districts, C - the number of counties, Pi- the population of county i, p - the highest population allowed in a district, p - the lowest allowable district population, M - a large number, and N - the maximum number of counties in a district.

-5 - We formulate the problem as D C min Z Z k=l i=1 D C Yik(l - Yik) + z Z M xiik k=l i=l (1) s.t, C i=l Pi Yik < P, k=1,2,.,.,D; (1.1) D k=l C C Z E i=l j=l i+j Yik = 1, il,21,.,, C; C Xijk = Z Yik - 1, k=l,2:,.,,,D; i=l Xijk = Yik' k=l,2,..,,D, i=l, 2,...,C; (1.2) (1.3) C z j=l (1.4) m Z x.,. I, < =1l m - 1, for k=1,2,...,D, and for all distinct sets of m arcs (igjg), for 2 < m < N, (1.5) C z Xjik - M Yik < 0, j=l j+i i=1,2,...,C, k=1,2,..,D; 0 < Xijk < 1, 0 < Yik < 1, i=l,2,...,C, j=l,2,..,C, (1.6) k=l,2,,..,D.

-6 - We note that xijk variables only exist for i and j adjacent and that we may restrict the number of districts in which a county may be included. Constraint (1.1) insures population equality and constraint (1.2) forces each county to be assigned to some district. Constraints (1.3), (1.4), (1.5), (1.6) and the linear objective term in xiik are used to obtain contiguity To see how these constraints lead to contiguity, we first note that constraint (1.5) implies that no set of arcs {(i,j)} form a cycle for any k and that (1.3) forces the arcs to form a tree. The arcs of the tree correspond to all but one of the counties forming the district by (1.4). The root of the tree has no arc leading to another county and, therefore, must have a self loop. (1.6) forces the root to have some fraction assigned to the districts of all arcs incident to it. The linear objective term is used to keep the number of self loops as low as possible and so to avoid having isolated counties that are not contiguous with the main district. We note that (1.3) cannot be satisfied if a district is composed entirely of fractions of counties. The constraint is always feasible if one full county exists in each district since the arcs can be assigned from the fractional counties and the whole county will include the self loop. The quadratic objective term is used to find a solution with the Yik variables as close to 1 or 0 as possible. A solution of this problem would produce a method for splitting counties, and another program to minimize splitting within counties would follow. We note that the problem is not convex and that many local optima may exist, The full program also involves a large number of constraints and even finding local optima may be

-7 - difficult, In the next section, a heuristic solution procedure is applied to the problem, 3. Solution Method A full formulation of (1) would include as many as 6 CD variables if every county was adjacent to four other counties. An equal number of constraints may also be present if N in (1.5) is large. For the Michigan State Senate, there are, for example, 83 counties and 38 districts, yielding possibly 31,540 variables. A heuristic to reduce the size of the program in (1) was developed using a hierarchical clustering procedure (see, for example, Johnson [6]) and appropriate definitions of the variables. The clustering algorithm involved the following: Step 1. Assign districts to all counties which can accommodate an integral number of districts. Step 2. Order all adjacent pairs (i,j) of the remaining counties by =ij = |p* - (Pi + Pj)! (2) C in increasing order of dij, where p* = Z pi/D, i=l the mean population of a district. Step 3. Proceed through the list of pairs and connect all counties into a district if a) Pi + Pj < p, and b) the remaining set of counties is composed of contiguous pieces that can each support an integral number of districts,

-8 - Step 4, If no new connections were made in Step 3, stop, Else, relabel the connected counties as new counties with populations equal to the sum of the populations of the counties forming them and return to Step 2. This algorithm results in a set of districts composed of an integral number of counties and in a set of counties which have not yet been placed into districts. The program in (1) can then be applied to the separate contiguous pieces of the remaining counties, For the State of Michigan Senate, this procedure was implemented, yielding 31 districts composed of 66 whole counties. For the remaining 17 counties and 7 districts, a modified program (1) was solved. In this implementation, the number of districts a county could enter was restricted to reduce the number of variables, The constraints in (1.5) and (1.6) were also eliminated on the first run with the intention of including them if a non-contiguous solution was found. The resulting problem had 71 constraints and 129 variables (including slack variables). The program was solved using the nonlinear programming code MINOS ([9]) on the University of Michigan's Amdahl 470/V8 computer. Several problems were solved in searching for other local optima by branching on the fractional variables. After each solution, the result was checked for contiguity and no non-contiguous districts were formed. In this process, if a fraction of a county was assigned to a district then that county was set at being completely in that district and the problem was solved again. In this way, many local optima were investigated.

-9 - This procedure resulted in the districting scheme in Figure 1, The broken lines represent county borders that are crossed by the districts. In this plan, three counties were split, including one county split among three districts. Because of the presence of two counties with populations slightly above p, it could be shown that at least three counties had to be split. Other plans may, however, split fewer townships within the counties, but this was not considered in the optimization. This plan placed 10 districts in Wayne County.. Another similar plan in which Wayne County obtained 9 districts was also developed and included 3 county line breaks. 4. Conclusion A formulation of a problem in redistricting legislatures was presented with the objective of minimizing the number of existing political units that do not belong to a single district. The full formulation was shown to be extremely large as the number of districts and existing polities becomes large. A heuristic method was described for reducing the size of this problem, and its results on the Michigan Senate were presented. This procedure yielded a plan with three split counties. The State Supreme Court, however, exercised its prerogative in deciding on a plan and adopted a plan commissioned by them in which four counties were split among different districts.

-10 - References [1] B. Adams, "A model state reapportionment process: the continuing quest for 'fair and effective representation"', Harvard Journal of Legislation 14, 825-904 (1977). [2] R, L, Engstrom, "The Supreme Court and equipopulous gerrymandering: a remaining obstacle in the quest for fair and effective representation", Arizona State Law Review 1976, 277-319 (1976), [3] E. Forrest, "Electronic reapportionment mapping", Data Processin Magazine 7 (7), 52-54 (1965). [4] R. S. Garfinkel and G. I. Nemhauser, "Optimal political districting by implicit enumeration techniques", Mgt. Science 16 (8), B495-B500 (1970). [5] K. J. Guida, "Deviations and justifications: standards and remedies in challenges to reapportionment plans", The Urban Lawyer 14 (1), 57-88 (1982). [6] S. Johnson, "Hierarchical clustering schemes", Psychometrika 32, 241-254 (1967). [7] Mahan v. Howell, 410 U.S. 315 (1973). [8] Michigan Supreme Court, "In re apportionment of Michigan legislature1982", Michigan Reports 413 (3), 96-223 (1982). [9] B. A. Murtagh and M. A. Saunders, "MINOS User's guide", Systems Optimization Laboratory, Stanford Unversity, Technical Report 77-9 (1977). [10] S. S. Nagel, "Simplified bipartisan computer redistricting", Stanford Law Review 17, 863-899 (1965). [11] Reynolds v. Sims, 377 U.S. 533, 583 (1964), [12] R. S. Stern, "Political gerrymandering: a statutory compactness standard as an antidote for judicial impotence", Univ. of Chicago Law Review 41, 398-416 (1974). [13] R. G. Torricelli and J. I. Porter, "Toward the 1980 census: the reapportionment of New Jersey's congressional districts", Rutgers Journal of Computers and Law 7, 135-156 (1979). [14] J. B. Weaver and S. W. Hess, "A procedure for nonpartisan districting development of computer techniques", Yale Law Journal 73, 288 (1963).

-11 - Figure 1. Redistricting plan for 17 counties in Michigan

UNIVERSITY OF MICHIGAN 3 90115 03994 828911111 3 9015 03994 8289