“Within this context, parents of young children can be quite discerning customers, so the resulting decisions typically receive a tremendous amount of scrutiny.”
Portland Public Schools,
In a dynamic city, the population of school-age children is always in flux. Unfortunately, the set of buildings available for use as public schools is not nearly as fluid. As a result, it is a constant challenge to choose appropriate assignments of school children to schools in order to achieve desired goals like minimizing travel distance, allowing kids who live near each other to attend the same schools, and achieving desired minimum and maximum class sizes. This “redistricting” problem is challenging, owing to the large number of decisions that are potentially in play:
Traditionally such decisions have been made by hand, requiring many hours of tedious manual work and lots of hand-wringing over whether the resulting assignments were really as good as they could be. Employees of Portland Public Schools have recently built an optimization model that solves the redistricting problem as a Mixed-Integer Programming (MIP) problem using Gurobi Optimizer. This MIP model yielded better results in less time.
After being involved in many iterations of the redistricting process, using tools ranging from pencil-and-paper analysis to computer programs that implemented basic redistricting heuristics, Shawn Helm, a long-time Portland Public Schools employee, decided that there had to be a better way. After reading academic papers by Hayri Önal on using MIP to redistrict political boundaries, Shawn saw the potential for using similar methods in school boundary redistricting. Using a number of online resources, including the Gurobi modeling and interactive examples as well as relevant academic papers (“A Model of Contiguity for Spatial Unit Allocation”, by T. Shirabe), Shawn together with Sahan Dissanayake, assistant professor of Economics at Colby College and Will Kearney, data analyst at Portland Public Schools, began building a MIP model to help solve the redistricting problem in Portland. Their initial model led to the launch of an official project, which eventually resulted in a custom Python application that can propose new district boundaries in a few hours.
The approach is a heuristic that follows a multi-phase strategy:
The solution tool encompassed an SQL-Server database that stored school locations, geographic planning areas, population data – number of kids in each planning area for each grade, and optimization scenarios. An optimization scenario had different parameters to force “this” school to be K-5, reopen “this” closed school, etc. In addition, an optimization scenario enables long-term planning, based on predicted population in 10 years, for example. The solution tool had a Graphical Information System (ArcGIS) that allowed one to visualize data and results and pull data from the SQL-Server. Last, the solution was built using the Gurobi Python API, which pulled data from the SQL-server to create variables and constraints. This decision support tool was used to help make decisions. The tool enabled multi-objective optimization of various conflicting objectives, such as minimizing travel distance, achieving smooth boundaries, creating uniform class sizes, and maintaining continuity with previous years. Also, the decision support tool enabled short-term planning using today’s data and long-term planning using predicted future data.
The team at Portland Public Schools chose Gurobi for a number of reasons:
Portland Public Schools, founded in 1851, is a PK-12 urban school district in Portland, Oregon. With more than 49,000 students in 78 schools, it is one of the largest school districts in the Pacific Northwest.
GUROBI NEWSLETTER
Latest news and releases
Choose the evaluation license that fits you best, and start working with our Expert Team for technical guidance and support.
Request free trial hours, so you can see how quickly and easily a model can be solved on the cloud.