June 4, 2018 in Wagner Prize
Optimization saves state prison system millions
SHARE: Share on PRINT ARTICLE:

In 2015, the Pennsylvania Department of Corrections spent $2.15 billion to house 50,366 inmates, which represents about 8 percent of the state’s total budget. In a typical week, the state Department of Corrections receives a list of approximately 1,000 inmates who need to be assigned to one of its 25 correctional facilities.
Nearly 100 unique factors have to be considered during the complicated task of assigning inmates to any of the Pennsylvania Department of Correction’s (PADoC) 25 facilities. Assigning inmates to correctional facilities is a complex process taking into account factors relating to the inmate, such as criminal history, demographic characteristics and mental and health needs, as well as relating to the prison system, such as facility utilization levels, support program availability and existing inmate characteristics at each facility.
Good assignments are important for both the inmate, since they can result in a lower chance of violent interactions with other inmates and faster access to treatment programs, and the prison system, since they can reduce staff workload and the number of prison transfers.
Prison Population Management System
Pennsylvania officials set out to solve the complex problem of assigning inmates by putting out a call for a better population management system. The goal was to make smarter decisions on inmate assignments to better address security concerns, age demographics and medical, programmatic and educational needs.
A Lehigh University student team, led by professor Tamás Terlaky, chairman of Lehigh’s Department of Industrial and Systems Engineering, answered Pennsylvania’s call and embarked on the project.
The project participants included Kristofer B. Bucklen, Director, Planning, Research & Statistics at the Pennsylvania Department of Corrections, and the following team from Lehigh University’s ISE Department: professors Terlaky, Louis J. Plebani and George R. Wilson and grad students Mohammad Shahabsafa, Naga Venkata Chaitanya Gudapati and Anshul Sharma.
Opportunity for Optimization
The main result of the project was the development of the Inmate Assignment Decision Support System (IADSS) for PADoC, that:
- simultaneously assigns the inmates to correctional institutions (CIs),
- schedules the treatment programs for the inmates, and
- considers all the factors and criteria of the assignment.
The system is comprised of:
- a user-friendly web-based interface, which is linked to PADoC’s databases, and
- an optimization engine that assigns inmates to institutions.
The main objectives of the inmate assignment problem are to:
- reduce the total population of inmates at the institutions,
- minimize inmate movements during prison terms, and
- reduce treatment program wait lists.
Prior to the launch of the project, inmates were manually assigned to various CIs. The subjective nature of this sequential ad-hoc assignment made the efficiency and quality of the assignment dependent on the experience and judgment of the staff at the office of population management. In order to remove the subjective component of the assignment, the Lehigh University team developed a decision-tree-based decision support system to reduce bias and variability in assignments, while improving adherence to the guidelines. This system provided a ranked order of the CIs for a particular inmate from which the staff member can choose the assignment.
Modeling and the Solution Methodology
The Lehigh University students and PADoC developed a first-of-its-kind mixed integer linear optimization (MILO) model to solve this complex problem.
To address all the conflicting factors of the assignment, the Lehigh University team allowed the violation of these conflicting factors and penalized the violations according to their importance. To do so, the team defined a weight for each factor of the assignment, which represents the importance of the factor in the assignment process. The violations of the factors are weighted according to their importance, and the sum of the penalized violations serves as the objective function of the MILO model.
Gurobi Optimizer was the optimization software package used to solve the MILO model based on its performance, flexible licensing options and Ph.D.-level technical support. The MILO model was particularly challenging to solve because the solver has to do the inmate assignment and schedule their treatment programs simultaneously, which leads to a large-scale mixed integer linear optimization model. Specifically, a problem with 200 inmates has 60,000 binary variables and 50,000 constraints. To solve a mixed integer linear programming problem of this size, Gurobi presolve significantly reduced the size of the problem. Also, the heuristics used by Gurobi to find a good initial integer-feasible solution decreased the optimality gap and, subsequently, resulted in a reduction of the overall solution time.
It takes an average of one to three hours to solve a problem with a dataset of 200 inmates; however, to reduce the optimality gap to a small value takes only a few minutes. Consequently, due to the use of hierarchical penalties in the MILO model, a close-to-optimal solution was sufficient for the user.
The objectives of the MILO model were hierarchically weighted, meaning that there were groups of objectives based on their importance, and the weights of the groups were specified accordingly. The weights were first specified through extensive discussions with the Office of Population Management personnel, with the goal of prioritizing the business rules of the assignment process. The weights were specified in a way that avoids numerical issues. Currently, the weights take values in the range [1e-2, 1e2], which were handled without numerical issues. The MILO model was extensively tested with various real data sets from PADoC with the goal of specifying and fine-tuning the weights of each of the factors and ensuring the robustness of the model in recommending appropriate simultaneous assignments and program scheduling.
Since the users of the IADSS tool do not have a background in operations research, a web-based GUI was developed to enable the users to interact with the optimization module and complete the assignments.
Millions of Dollars Saved in First Year
The Department of Corrections saved $2.9 million in the first year of implementation and it expects to reduce the cost by $19.2 million over five years. Four areas of significant savings resulted from the implementation including: 1) reduced waiting time for treatment programs, 2) fewer assaults, 3) reduced staff, and 4) fewer transfers.
The application has reduced the number of incidences of inmate violence, reduced transfer rates and staff workload, and has also reduced the time it takes for inmates to get access to treatment programs. What took a staff of seven a full week to do is now done in minutes on a daily basis by the application. It marked the first time a correctional system utilized O.R. methodologies to optimize its operations.
The team’s process and results are detailed in the paper, “The Inmate Assignment and Scheduling Problem and its Application in the PA Department of Corrections,” which was submitted for the 2017 Daniel H. Wagner Prize for excellence in Operations Research. The team not only won the prestigious Wagner Prize, it was also honored by the Pennsylvania House and Senate at the Pennsylvania Capitol.
Pano Santos is a senior technical content manager at Gurobi. Mohammad Shahabsafa is a Ph.D. candidate at Lehigh University’s Department of Industrial and Systems Engineering. Tamás Terlaky is a professor and chair at Lehigh’s ISE department.