Suppose that a state sends R persons to the U.S. House of Representatives. There are D counties in the state (D > R), and the state legislature wants to group these counties into R distinct electoral districts, each of which sends a delegate to Congress. The total population of the state is P, and the legislature wants to form districts whose population approximates p = P/R. Suppose that the appropriate legislative committee studying the electoral districting problem generates a long list of N candidates to be districts (N > R). Each of these candidates contains contiguous counties and a total population pj (j = 1, 2, . . . ,N) that is acceptably close to p. Define cj = |pj €“ p|. Each county i (i = 1, 2, . . . ,D) is included in at least one candidate and typically will be included in a considerable number of candidates (in order to provide many feasible ways of selecting a set of R candidates that includes each county exactly once). Define

Given the values of the cj and the aij, the objective is to select R of these N possible districts such that each county is contained in a single district and such that the largest of the associated cj is as small as possible.
Formulate a BIP model for this problem.

Transcribed Image Text:

1 if county i is included in candidate j ij_j0 ifnot.