Analysis of a Metaheuristic for Redistricting
Name
Vjatšeslav Antoškin
Abstract
Redistricting is the process of redrawing district boundaries. It can be
formulated as a combinatorial optimization problem in order to achieve a particular political objective. However, the solution space is staggering in this case, and there are no known methods to tackle the problem in a consistent manner.
Metaheuristics are one of the methods that have been proposed in order to address the problem.
In this thesis, test suites are created for analysis of metaheuristics for redistricting purposes. Two versions of simulated annealing, a well-known metaheuristic, are created: sequential and parallel. They are analyzed using the created test suites.
It is shown that simulated annealing can probably be used for redistricting of a
region with a small number of districts such as the state of Iowa, which has 4
congressional districts. However, the created versions of simulated annealing are ineffective for regions with a larger number of districts such as the state of New York, which has 27 congressional districts.
formulated as a combinatorial optimization problem in order to achieve a particular political objective. However, the solution space is staggering in this case, and there are no known methods to tackle the problem in a consistent manner.
Metaheuristics are one of the methods that have been proposed in order to address the problem.
In this thesis, test suites are created for analysis of metaheuristics for redistricting purposes. Two versions of simulated annealing, a well-known metaheuristic, are created: sequential and parallel. They are analyzed using the created test suites.
It is shown that simulated annealing can probably be used for redistricting of a
region with a small number of districts such as the state of Iowa, which has 4
congressional districts. However, the created versions of simulated annealing are ineffective for regions with a larger number of districts such as the state of New York, which has 27 congressional districts.
Graduation Thesis language
English
Graduation Thesis type
Bachelor - Computer Science
Supervisor(s)
Benson Muite
Defence year
2018