The Inmate Assignment and Scheduling Problem and Its Application in the Pennsylvania Department of Corrections

Introduction

According to the International Centre for Prison Studies, the United States incarcerates 698 people for every 100,000 of its population. Although it has approximately 4.5% of the world’s population, the United States has 21.4% of the world’s incarcerated population (Walmsley 2017). In 2010, all levels of government in the United States spent more than $80 billion on corrections (Kyckelhahn and Martin 2010), implying a $260 tax burden for each U.S. resident. Adjusted for inflation, the expenditures on corrections in 2010 were more than three times those costs in 1979 (Schanzenbach et al. 2016).

Because of insufficient capacity in the correctional institutions (CIs), the CIs are increasingly becoming overcrowded. Population management of the inmates, which is one of the most critical operations within a correctional system, requires significant monetary and human resources. Efficiently managing the inmate population can result in substantial savings. Appropriate assignment of the inmates to the CIs is a key element of population management and can lead to significant savings, enhance public safety, and improve security in the CIs.

When a court delivers a sentence, the inmate often receives a list of treatment programs based on various assessments, including the crime committed. Research shows that inmates who complete the programs offered by the CIs have a lower recidivism rate (Davis et al. 2013); hence, these programs have the capability to save CI capacity and promote a safe and healthy society. Inmates are usually given a sentence of minimum length in “indeterminate sentencing states” like Pennsylvania (PA). Having served their minimum sentence, they are eligible to be released conditionally (i.e., paroled) if they satisfy all the parole requirements. One of the parole requirements is to complete all the required treatment programs. Overcrowding of CIs adversely affects the way inmates receive their treatment programming and delays scheduling because the resources for the programs are limited. Inmates who receive timely treatment programming have a better chance of becoming eligible for parole and leaving the CI earlier, thereby reducing the population of the CIs.

In 2015, the Pennsylvania Department of Corrections (PADoC) spent a staggering $2.15 billion to house 50,366 inmates (Mai and Subramanian 2017). All inmates who enter the correctional system have their own programming needs and special requirements. Often a CI can offer only certain programs because it has limited personnel and infrastructure resources and so might not be able to meet the needs of all inmates. We briefly describe the inmate assignment process before our initiation of this project. Each new inmate was manually assigned to a CI by a staff member of the Office of Population Management (OPM). The OPM considers numerous factors (i.e., rules and criteria) in assigning inmates to CIs, including but not limited to security concerns, mental and medical conditions, program needs, separation from other inmates, capacities of the CIs, and home county of the inmates. Having to individually consider each factor for the assignment of each inmate is time-consuming and prone to human errors. Additionally, when inmate assignment is done individually and sequentially, inmates assigned later are not considered in the current assignment. This greedy sequential assignment of inmates to CIs makes the process highly inefficient and results in numerous violations of the factors, the capacity constraints, or both.

The optimal inmate assignment project, in which we collaborated with the PADoC, spanned five years from idea to successful implementation. The main goal of the project was to develop an inmate assignment decision support system (IADSS) for the PADoC, which simultaneously assigns the inmates to CIs, schedules the treatment programs for these inmates, and considers all the factors and criteria of each assignment. The IADSS comprises a user-friendly web-based interface, which is linked to the PADoC databases, and an optimization engine that assigns the inmates to CIs.

The goal of the inmate assignment problem (IAP) is to optimize inmate assignments, transfers, and program scheduling, while considering numerous restrictions and constraints to advance the following objectives:

• reduce the total population of inmates at the CIs,

• minimize inmate movements during prison terms, and

• reduce waiting lists for treatment services.

Literature Review

The IAP is a novel class of the assignment problem (Votaw and Orden 1952, Flood 1953) with several side constraints. The classic assignment problem and the algorithms used to solve it were studied extensively during the 1950s (Dantzig 1951, Orden 1951). Kuhn (1955) suggests the well-known Hungarian method for solving the assignment problem. Assignment models have been used in a large variety of applications of optimization. For example, crew scheduling is a broadly used problem class using generalized assignment models. Airline crew scheduling is one of the most important crew-scheduling problems that received considerable attention within the optimization community during the 1960s (Arabeyre et al. 1969). The problem has since been studied extensively; for example, Caprara et al. (1998) used the assignment model for crew scheduling in the railway industry. To the best of our knowledge, the only operations research (OR) paper relevant to the IAP is Li et al. (2014), in which the authors studied the inmate assignment process and developed a decision tree that represents all the factors involved in the assignment of inmates to CIs.

Contributions: Novel Modeling and Solution Methodology

The IAP revolves mainly around the assignment of inmates to the CIs and the scheduling of programs for the inmates at the CIs. To develop a mathematical optimization model, we mapped and formalized all the inmate assignment processes. This was a challenging process because neither the PADoC nor, to the best of our knowledge, other departments of corrections (DoCs) employ OR experts. Owing to scarce resources and often conflicting rules at DoCs, the IAP is inherently an infeasible problem. To address the need for simultaneous system-wide optimization of inmate assignments and consider all the conflicting factors, we developed and fine-tuned a hierarchically weighted, multiobjective mixed-integer linear optimization (MILO) model. In conjunction with our model development we also developed data collection and preparation procedures, which interface with the DoC database systems. Ultimately we developed the web-based IADSS, which enables a user to make optimal decisions in a fraction of the time needed previously. Since September 2016 the integrated IADSS has been in daily use by PADoC. The IADSS makes the assignment process efficient, while significantly improving the quality and consistency of the assignments. These goals are achieved by advanced optimization modeling of system-wide assignment and scheduling needs and the use of state-of-the-art optimization methodology.

Impact

The IADSS enables the PADoC to make high-quality, consistent assignments, while also increasing security and reducing violence. It has resulted in cost savings by reducing the inmate population and the number of transfers between the CIs. Additionally, it has enabled the PADoC to reduce the staff needed for making assignments and has resulted in a smaller number of assaults within the CIs. The PADoC saved $2.9 million in its first year using the IADSS and expects to reduce its costs by $19.8 million over the subsequent five years.

The broader impact of this project and the highly successful development of the IADSS is that it can be adapted and used in the correctional systems of other states and countries. Thus, this project and the solution methodology we developed represent a new, high-impact application of OR and analytics methodologies.

The remainder of the paper is structured as follows. The Preliminaries and Problem Description section presents the IAP and the numerous factors and program-scheduling requirements that define the IAP. Modeling and solution methodology details are presented in the Modeling and the Solution Methodology section. The Implementation at the PADoC section presents the development of the IADSS and its implementation at the PADoC. We list and quantify the benefits of using the IADSS in the Benefits and Impact of the IADSS section and present a summary of the paper in the Summary section. The multiobjective MILO model for simultaneously assigning inmates to the CIs is presented in the appendix, Hierarchical Multiobjective Mathematical Model.

Preliminaries and Problem Description

In this section we discuss the preliminary developments at the PADoC, formally define the IAP, and elaborate on the rules and criteria used for inmate assignment to the CIs.

Preliminary Development

When the project started, we discussed with PADoC management the need for a decision support system to assist the OPM in assigning each inmate to the best available CI, considering both the needs and limitations of the inmates and the PADoC’s limited resources. This is a complex problem in which the ideal assignment of all inmates is not possible. Inmate-specific factors are a combination of several categories, including medical, psychological, educational, custody-level, and sentence conditions. On the other hand, CIs have numerous limitations, such as security level, treatment-program availability, and capacity.

Conventionally, the assignment process has been manual and subjective, whereby a staff member uses the information provided about the inmate and the CIs from the PADoC database and assigns the inmates one at a time to a CI. Although the general guidelines for the assignment are known, the large number of relevant factors, the daily fluctuations in available capacities at the CIs, and the subjective nature of this sequential ad hoc assignment made the efficiency and quality of the assignment heavily dependent on the experience and judgment of the staff. To remove the subjective component of the assignment, we initially developed a decision tree–based decision support system (DTDSS) to reduce bias and variability in assignments, while improving adherence to the guidelines. The DTDSS provided the PADoC with a ranked order of the possible CIs for a given inmate and allowed the staff member to choose the CI. This eliminated much of the tedious work of evaluating various combinations of factors; thus, it freed staff members to use their experience to choose from a smaller subset of the most suitable CIs.

Figure 1 illustrates the decision tree of the DTDSS. The development and use of the decision tree in the DTDSS were critical in classifying and refining all the relevant factors and their level of importance in inmate assignment. We had in-depth discussions with PADoC personnel about the factors that influenced the inmate assignment, subsequently identified 60 of the most important factors used in the manual assignment procedure, and incorporated them into the DTDSS. The DTDSS uses these factors and rules to evaluate and rank the CIs with respect to their suitability for the inmate being assigned. The DTDSS assigns weights and penalties for each factor and uses the accumulated penalties to rank the CIs for the inmates.

This approach could conceivably have been deemed sufficient, although clearly not optimal, if inmates were arriving at the system in a sequence (i.e., one by one). The greedy assignment strategy embodied in the sequential application of DTDSS cannot adequately anticipate, several assignments into the future, the bottlenecks at the CIs. When a batch of inmates needs assignment, there is an opportunity to make resource trade-offs by performing a batch assignment, a process that is not available in the sequential approach. In a sequential assignment the sequence of the inmates is critical and significantly affects the succeeding assignments. The need for system-wide, simultaneous assignment made clear the need for a multiple-objective optimization model that simultaneously considers both all inmates needing assignment and the current state of all CIs from a system perspective.

Assignment Criteria

In this subsection we present the essential elements of the inmate assignment problem. First we give a brief description of the inmate assignment process. Inmates are evaluated and classified at intake CIs. Each period, a group of inmates must be assigned to CIs, while all restrictions and constraints must be considered. This is the basic inmate initial assignment problem. Figure 2 shows a map of Pennsylvania with its 25 currently running CIs of the PADoC. A crucial feature of the inmate initial assignment problem is that inmates must go through individually specified programs, which are scheduled according to explicit rules and requirements. Furthermore, for a variety of reasons, an inmate might transfer from his (her) initially assigned CI to another one. The need for the inmate transfer further complicates the problem. Below we explain the criteria that must be considered during the initial assignment of inmates to CIs.

• General factors: A variety of factors must be satisfied at initial inmate assignment, and inmates who meet these criteria must be assigned to a predefined set of CIs; these criteria include but are not limited to the following: high-risk inmates, inmates who are mentally unstable, young adult offenders, and inmates serving a life sentence.

• Available beds: The number of available beds for each CI is determined before assigning the inmates. At least a minimum number of inmates, which is a function of the available beds, should be assigned to each CI to properly utilize bed spaces. Additionally, for each CI, the maximum number of inmates, which is again a function of the available beds, is specified to avoid creating long lists of inmates waiting for beds to become available at the CI. Furthermore, the number of inmates assigned to the CIs should be proportional to the number of available beds when it is within the minimum and maximum range.

• Home county: Inmates need to be assigned to a CI near their home county.

• Separations: Considering previous inmate-to-inmate and inmate-to-staff conflicts, some inmates cannot be assigned to specific CIs. Additionally, some pairs or groups of inmates who are waiting for an assignment cannot be assigned to the same CI.

Treatment Programs

Inmates are usually given a minimum-length sentence (i.e., the minimum time they must stay at CIs) and are given a scheduled parole board interview before their minimum-sentence date. To be eligible for parole, they need to satisfy all of the requirements of their sentences. One of the most important requirements is that inmates must complete all their treatment programs before their parole board interviews. Treatment programs are prescribed by the court or by the correctional system.

Ideally, inmates should be assigned to a CI that can offer their required program(s) before their parole board interview. However, because of limited capacity of the programs at CIs, not all the inmates are able to finish their program(s) before their parole board interview. This results in the creation of inmate waiting lists for the programs at the CIs, which turns out to be one of the most important criteria in the IAP. Furthermore, inmates can start their programs only within the 24-month window before their minimum-sentence date.

Programs can be classified as either open enrollment or closed enrollment. In an open enrollment program, enrollments can occur any time. If an inmate completes an open enrollment program, the next inmate can start that program immediately. However, in a closed enrollment program, a group is identified, and all members of the group start and complete the program at the same time.

The number of inmates who start an open enrollment program at time $t$ is driven by the number of open spots of that program at time $t$. However, the number of inmates who can start a closed enrollment program at time $t$ is driven by the number of groups of that program that can start at time $t$. A minimum (maximum) number of inmates can be enrolled in a group for each closed enrollment program.

In handling the program waiting lists, the cluster concept is important. A cluster is a group of closed enrollment programs that have common instructors; that is, an instructor can handle all the programs in a cluster, and the program(s) that the instructor can run at a given time must be determined. Clusters are defined only for closed enrollment programs.

One of the main goals of the IAP is to ensure that inmates start their programs as soon as possible. This goal is formalized as minimizing the maximum waiting time of the inmates for starting their required program(s). To reach this goal, we schedule the programs for the incoming inmates, while considering the limited available resources of the CIs and the inmates who are already housed in the CIs.

Transfer Constraints

After the initial assignment, inmates might need to be transferred. Below, we list some possible reasons for transfer after the initial assignment.

• Parole violator: Inmates who are released on parole and violate their parole terms are brought to a parole intake facility and must subsequently be assigned to a CI.

• Program placement: In some situations, the CI to which an inmate is initially assigned does not have all the inmate’s required programs. Additionally, treatment programs may be prescribed after the initial assignment, and some of these programs may not be available in the assigned CI. In such cases, the inmate should be moved to a CI where all the required programs are offered.

• Incentive-based transfers: Inmates who satisfy specific predefined requirements can request to be moved to other CIs.

• Separation: The need to separate an inmate from other inmates or from DoC staff can lead to a transfer request.

Constraints and restrictions for transfer placements are the same as those we explain above in the Assignment Criteria subsection for the initial assignment of the inmates. However, the importance of the factors for a transfer placement might differ from those of an initial assignment.

Modeling and the Solution Methodology

As we explain above in the Preliminaries and Problem Description section, one of the main goals of the IAP is to assign the inmates to CIs. However, it is not a basic assignment problem, because a variety of factors need to be considered in the assignment of each inmate.

To address all the conflicting factors of the assignment, we developed a hierarchically weighted multiobjective MILO model. Because the problem is inherently infeasible, we allow the violation of the factors and penalize the violations according to their importance. To do so, we define a weight for each factor of the assignment to represent the importance of the factor in the assignment process. The sum of the hierarchically weighted violations serves as the objective function of the MILO model. We present the mathematical model in detail in the appendix.

We used Gurobi (2016), the optimization software package, to solve the MILO models. After developing the MILO model we extensively tested it using various data sets from PADoC. Our objectives were to specify and fine-tune the weights of each factor and ensure the robustness of the model in recommending appropriate simultaneous assignments and program scheduling.

Whenever we solve the MILO model and schedule the programs, not all inmates who will start the programs within the given time horizon are in the system. For example, each week, inmates who have short sentence times and therefore need immediate program enrollment enter the correctional system. Thus, we have freedom in scheduling the programs for periods toward the end of the time horizon. As a result, the MILO model has many equally good solutions. This, in turn, increases the solution time, because a significant amount of time is required to prove optimality. Knowing that proving optimality requires excessive amounts of time, we stop the MILO solver when the absolute optimality gap reaches a predefined threshold.

Implementation at the PADoC

Before the implementation of the IADSS, an OPM staff member manually assigned inmates to CIs. This manual process had three main drawbacks:

• As we mention above, a variety of factors need to be considered in assigning each inmate to a CI; these include security concerns, mental and medical conditions, program needs, separation from other inmates, CI capacity, and the inmate’s home county. However, considering all the factors of the assignment and the characteristics and capacities of the CIs for each inmate is time-consuming and prone to human error. As a result, the manual process resulted in numerous inappropriate assignments of inmates.

• If the inmate assignment is done sequentially, then the inmates who are assigned later are not considered in the earlier assignments. This makes the process inefficient and suboptimal. If the assignment is done manually, it is impossible to appropriately consider the inmate assignments that will follow in assigning the current inmate.

• Scheduling of treatment programs was not considered in the manual inmate assignment. As a result, inmates had to wait longer to receive their programming, thus postponing their eligibility for parole; therefore, the CI population increased.

The DTDSS that was developed initially enabled the PADoC to address the first drawback of the manual inmate assignment and to consider the rules and criteria of the assignment in assigning each individual inmate to a CI. However, the DTDSS cannot simultaneously assign a batch of inmates to the CIs and does not consider the treatment-program scheduling in the assignment. This intensified the need to develop the multiobjective optimization model, which became the heart of the IADSS.

Development of IADSS

The development of the IADSS took three years. First, we developed a mathematical optimization model as a proof of concept to optimize the simultaneous initial assignment of the inmates to the CIs. It demonstrated to OPM personnel that mathematical optimization provides a powerful tool to optimally assign inmates to CIs. In conjunction with model development, we had to harvest data from the PADoC databases; thus, we developed and implemented data collection and clean-up procedures to link the model to the live databases.

Figure 3 shows the components of the IADSS. As one can see in this figure, the graphical user interface (GUI) enables the user to communicate with the IADSS. The web server gets the requests from the GUI, reads the information from the PADoC databases, and passes the information to the optimization module. The heart of the IADSS is the optimization module, which uses the data extracted from the PADoC databases to generate the mathematical optimization model of the IAP databases and solves the model using Gurobi. Because the assignment of inmates to CIs is a multiobjective process, we optimized the weighted sum of the objectives and validated the results by solving real data instances from the PADoC.

The time sequence of the development phases followed the increasing mathematical sophistication and complexity of the modules. The violations of the inmate assignment factors were interpreted as the penalty objectives of the assignment and were added sequentially to the optimization model. As we explain in the Preliminaries and Problem Description section, we needed to make two main decisions: assignment of inmates to CIs and scheduling of their program(s). We initially developed a model that only assigned the inmates to the CIs, and we tested the model with real data from PADoC to validate the assignment recommendations. We then extended the model to include the scheduling of the programs for the inmates. Executing the project in this sequence brought meaningful capability online in a judicious manner, while demonstrating to OPM the possibilities of an optimization model and the utilization of a decision support system to optimally execute its most critical task. OPM has used the model that assigns the inmates and schedules the programs for the daily assignment of inmates since September 2016.

Benefits and Impact of the IADSS

The successful development and implementation of the IADSS has provided both significant financial and nonquantifiable human benefits.

High-Quality, Consistent Assignment

• The assignment of the inmates is done simultaneously for all the inmates with a petition for assignment or transfer. Simultaneous assignment ensures system-wide optimum.

• All factors of the assignment are considered for each inmate, thus ensuring consistently high-quality assignments. The errors encountered have almost exclusively been due to data inconsistency; therefore, the inappropriate assignments have helped OPM to identify data errors.

• The inmate assignment process was previously fragmented in the sense that assignment was done by OPM, and the program waiting lists were monitored by the Bureau of Treatment Services and reported monthly to OPM. With the implementation of the IADSS the processes are integrated, and all necessary elements of the assignment are considered in one system.

• Program schedules and wait lists at each CI are generated as an integral part of the inmate assignment. The integrated IADSS minimizes the wait time of the inmates for their required program(s), thus allowing timely release of inmates and reducing the inmate population.

• In addition to simultaneous assignment, individual assignment can be made for the inmates. Facilities are sorted in the individual assignment for each inmate and consider all the factors of the assignment for that inmate only. If the simultaneous assignment recommendation is not appropriate for an individual, the individual assignment results can be used to evaluate possible assignment to other CIs. The simultaneous assignment recommendation and individual assignment recommendations from the IADSS interface are demonstrated in the first and third panels of Figure 4, respectively.

• Three geographical regions (west, central, east) are defined in PA counties, and CIs are placed in each of these three regions. Figure 2 shows the CI regions. Because of the complexity of considering the distance of the home county to the CIs, only the distance of the home region to the CIs was considered originally. The IADSS enables the PADoC to consider the actual distance of the home county to the CIs for each inmate.

• The rate of acceptance of the simultaneous assignments and individual assignments was measured to validate the MILO model and ensure that the MILO model captures the hierarchy of the factors of the assignment. In January 2017 more than 90% of the inmates were assigned to the facility that was suggested by the simultaneous assignment. Among the remaining 10% of the inmates, more than 6% were assigned to one of the first three CIs recommended by the individual assignment. The remaining 4% who were assigned to other CIs were assigned either because of data inconsistencies or the special conditions of those inmates. Table 1 presents the results of the IADSS for the first 10 days of 2017.

Table 1. The Acceptance Rate of the IADSS Inmate Assignments Recommendations Was More Than 90% in the First 10 Days of 2017

User-Friendly Web Application

• We developed a web-based GUI to enable the user to interact with the IADSS. Figure 4 shows a screenshot of the GUI.

• The IADSS collects all the personal and sentence information needed for the assignment of an inmate and displays it in the GUI to facilitate the review of the assignment. The second panel of Figure 4 displays the inmate’s personal information.

• The IADSS reports the program waiting lists to alert the Bureau of Treatment Services about current and future bottlenecks in program schedules and availability.

Security Enhancement

Security enhancement is hard to quantify; however, it was a major motivation for initiating this project. The use of IADSS at the PADoC has resulted in the security enhancements listed below:

• As stated by the PADoC Secretary, Wetzel, inmate transportation is one of the PADoC’s riskiest operations. By improving inmate initial assignments, IADSS has reduced inmate transfers, thus enhancing the security of the CIs and public safety.

• IADSS considers inmates’ demographic information and enforces inmate separations in making assignments, which in turn reduces the number of assaults, thus increasing the security of the CIs.

Quantified Savings

In this section we identify four areas of significant cost savings that resulted from the implementation of IADSS in the first year, and we project the benefits for the subsequent five years.

1. Reduced waiting time: IADSS helps to decrease the waiting time for treatment programs, which reduces the length of stay for inmates past their minimum sentence date. We consider the inmates who have less than nine months to their minimum sentence date at the time of their initial petition for assignment, and who need at least one treatment program. These inmates must start their programs immediately, because any delay in starting their program(s) will result in a postponement of their parole eligibility. The waiting time of these inmates to start all their programs is calculated with the objective of determining how much IADSS has helped to reduce the waiting time for programs. In Figure 5, the cumulative distribution functions of the waiting time of these inmates for the first and second quarters of 2016 (2016-1, 2016-2) and the first and second quarters of 2017 (2017-1, 2017-2) are plotted. Note that the waiting time in the second quarter of 2017 stops at three months, because we did not have the data for longer waiting times (i.e., beyond the three months) at the time of writing the paper. For both quarters 1 and 2, the cumulative distribution function for 2017 is above and to the left of the one for 2016, thus showing that the use of IADSS has substantially reduced waiting times. Comparing the waiting times of the inmates with initial petition requests in the first quarter of 2016, when IADSS was not yet used, with the first quarter of 2017, we found that the average waiting time of the inmates in the first quarter of 2016 is 143 days, whereas the average waiting time of the inmates in the first quarter of 2017 is 89 days. Therefore, the average waiting times decreased by 54 days from 2016-1 to 2017-1.

   On average, PADoC handles 10,000 initial petitions annually. Of those petitions, 12% have less than nine months to their minimum sentence date and need at least one program. The marginal cost of keeping an inmate in a CI is $16 per day. As a result, the total annual saving of reducing the inmates’ waiting time in starting their program(s) is $10,000\times 0.12\times 54\times \$16=\$1,036,800$. As Figure 5 shows, the waiting time decreased significantly from 2016 to 2017. On the basis of having achieved a 54-day reduction from 2016 to 2017, we project that a 90-day reduction in the waiting time can be achieved at the steady state of the system in years 4 and 5 (i.e., from September 2019 to September 2021). This 90-day reduction in the waiting time for programs will enable the PADoC to close a full CI unit. Closing a CI unit allows for more savings than the marginal cost of keeping an inmate in a CI. If a CI unit is closed, the savings per day for each inmate is $30. Thus, the saving in years 4 and 5 will be $10,000\times 0.12\times 90\times \$30=\$3,240,000$.

2. Fewer assaults: Assigning the most appropriate combination of inmates to the CIs results in fewer assaults. We compared the number of assaults between January and July of 2017 with the same period in 2016; 95 fewer assaults were reported. We then projected 163 fewer assaults for the full year. The PADoC estimated that approximately 10%–15% of this reduction is due to the introduction of IADSS. Thus, IADSS resulted in an average of 20 fewer assaults in 2017. The criminal justice literature (Cohen 2005) documents that an assault costs on average $70,000. Thus, by reducing the number of assaults, IADSS has resulted in savings of $20\times \$70,000=\$1,400,000$.

3. Reduced staff: Fewer OPM staff are required to oversee inmate assignments and transfers. Because of using IADSS, one less position (i.e., captain) is needed to make the inmate assignments at PADoC. The salary and benefits of a captain total $\$134,742$ annually.

4. Fewer transfers: Because of initially assigning inmates to the correct CI, fewer transfers are required later. By using IADSS to make better assignments, there were $4,672$ fewer transfers in 2017. The average cost of a transfer is $\$82.85$; hence, the total annual transportation savings equal $4,672\times \$82.85=\$387,075$.

Considering the four main savings areas, IADSS has decreased the PADoC’s annual costs by $2.96 million. By taking the sum of the savings in the four main areas, we can project savings of $19.20 million over five years. In Table 2, the quantified savings are summarized.

Table 2. Quantified Savings of Using the IADSS in the First Year of Implementation and over Five Years

Summary

Every correctional system faces the inmate assignment problem on a daily basis. Various constraints, including general assignment factors, CI capacity constraints, scheduling of inmate treatment programs, and the assignment of inmates near their home counties, should be satisfied. Making an ideal assignment (i.e., satisfying all the constraints of the assignment) is impossible; thus, the IAP is inherently an infeasible problem. Additionally, the treatment programs must be scheduled at the time of the assignment.

In this paper we discuss the development of a novel hierarchical multiobjective MILO model for the IAP. The weighted sum of the violation of the assignment constraints and the treatment-program waiting times serve as the penalty objective of the MILO model. The multiobjective MILO model is the core of the IADSS. The IADSS enables the PADoC to simultaneously and optimally assign inmates to the CIs in the PA correctional system and schedules treatment programs for them, while considering all the rules and criteria of the assignment. The IADSS minimizes the waiting time of the inmates for being assigned to their required program(s); hence, it facilitates the timely eligibility of the inmates for parole, which ultimately reduces the inmate population within the correctional system. The PADoC has successfully used the IADSS for the daily assignment of inmates to CIs since September 2016.

To the best of our knowledge, this is the first time that OR methodology has been built directly into the routine business operations of a correctional system. The success of this project opens new avenues to (1) adapt and introduce the IADSS methodology to optimize the operations of correctional systems of other states and countries, and (2) explore other applications of OR methodology in the complex operations of correctional systems. Correctional systems in the United States and worldwide have numerous problems that cry out for solutions using OR methodologies. This highly successful application of OR in a large correctional system will open a rich application area of OR, just as the first crew-scheduling application did in the airline industry.

Appendix. Hierarchical Multiobjective Mathematical Model

In this section we present a MILO model for the IAP. We first explain the assignment and the treatment program constraints, and finally the objectives of the problem.

Assignment Criteria Constraints

Let $\mathcal{I}$ be the set of inmates waiting to be assigned and let $\mathcal{J}$ be the set of the available CIs for the assignment. Each inmate should be assigned to one facility, that is,

$$\sum _{j\in \mathcal{J}}{x}_{ij}=1\forall i\in \mathcal{I},$$

where $x_{ij}$ for all $i\in \mathcal{I}$, and $j\in \mathcal{J}$ is a binary variable and is equal to 1 if inmate $i$ is assigned to facility $j$. Let $\mathcal{K}$ be the set of general factors, and let coefficient ${\kappa }_{ik}$ for $i\in \mathcal{I}$, $k\in \mathcal{K}$ be equal to 1 if factor $k$ applies to inmate $i$, and equal to 0 otherwise. Additionally, for all $j\in \mathcal{J}$, $k\in \mathcal{K}$ let ${\rho }_{jk}$ be equal to 1 if facility $j$ can accommodate inmates with factor $k$, otherwise ${\rho }_{jk}=0$. The following constraints describe the general-factors violations of inmates.

$${\kappa }_{ik}\left(1,-,\sum _{j\in \mathcal{J}},{\rho }_{jk},x_{ij}\right)=v_{ik}\forall i\in \mathcal{I},\forall k\in \mathcal{K},$$

where $v_{ik}$ indicates the violation of factor $k$ by inmate $i$ and is equal to 1 if inmate $i$ violates factor $k$; otherwise, $v_{ik}$ is equal to 0. Furthermore, we have capacity-related constraints:

$$\sum _{i\in \mathcal{I}}{x}_{ij}=s_j\forall j\in \mathcal{J},$$

where $s_j$, $j\in \mathcal{J}$ denotes the number of the inmates who are assigned to facility $j$. Let $c_j$ be the capacity of facility $j$. Ideally, for each pair $j_1$ and $j_2$ of CIs, we want to assign inmates proportional to their capacities; that is, ideally we would have

$$c_{j_1}/s_{j_1}=c_{j_2}/s_{j_2}.$$

Variables ${\delta }_{j_1{j}_2}^{+},{\delta }_{j_1{j}_2}^{-}$ are the decision variables representing the deviation from assigning inmates proportional to the capacities of CIs $j_1$ and $j_2$ and are defined as

$$c_{j_2}{s}_{j_1}-c_{j_1}{s}_{j_2}={\delta }_{j_1{j}_2}^{+}-{\delta }_{j_1{j}_2}^{-}\forall j_1,j_2\in \mathcal{J},j_1\ne j_2.$$(A.1)

We aim to minimize ${\delta }_{j_1{j}_2}^{+},{\delta }_{j_1{j}_2}^{-}$ by penalizing them in the objective function.

Additionally, we define upper and lower bounds on the number of inmates who can be assigned to each facility. Let $c_j^{\min }$ and $c_j^{\max }$ be, respectively, the minimum required and maximum allowed capacity of facility $j$, which are functions of the capacity $c_j$ of facility $j$. For example, $c_j^{\min }={\zeta }_j^{-}{c}_j$ and $c_j^{\max }={\zeta }_j^{+}{c}_j$ for appropriately chosen constants ${\zeta }_j^{-}\le 1\le {\zeta }_j^{+}$. Let $o_j$ be the number of inmates assigned over the maximum capacity of facility $j$, and let $u_j$ be the number of inmates needed to reach the minimum capacity of facility $j$. We have

$$\begin{array}{cc}{s}_j& \le c_j^{\max }+o_j\forall j\in \mathcal{J},\\ s_j& \ge c_j^{\min }-u_j\forall j\in \mathcal{J}.\end{array}$$

We aim to minimize $o_j$ and $u_j$ by penalizing them in the objective function.

Another important criterion for the inmate assignment is the separations. Considering the history of inmates, there might be pairs of inmates who cannot be assigned to the same facility. Let ${\mathcal{I}}^s$ be the set of inmate pairs who should be separated from each other. Additionally, an inmate might already have in his (her) file that he (she) has to be separated from certain staff or inmates who are already in a facility. Let ${\mathcal{J}}_i^s$ be the set of CIs from which inmate $i$ should be separated. We have

$$\begin{array}{cc}& \sum _{j\in {\mathcal{J}}_i^s}{x}_{ij}=0\forall i\in \mathcal{I},\\ & x_{i_{1}j}+x_{i_{2}j}\le 1\forall \left(i_1,i_2\right)\in {\mathcal{I}}^s.\end{array}$$

Treatment Program Constraints

Next we explain the constraints needed to describe the waiting lists of the programs at the CIs. Let ${\mathcal{P}}^o,{\mathcal{P}}^c$ be, respectively, the set of open enrollment and closed enrollment programs, and let $\mathcal{C}$ be the set of program clusters. Let ${\widehat{t}}_{ip}$ and ${\overline{t}}_{ip}$ be, respectively, the latest time and earliest time that inmate $i$ is supposed to start program $p$, and let ${\alpha }_{ipt}=1$ if $t\ge {\widehat{t}}_{ip}$, otherwise ${\alpha }_{ipt}=0$; that is, inmate $i$ should not start program $p$ later than $t$ if ${\alpha }_{ipt}=1$. Similarly, ${\beta }_{ipt}=1$ if $t\ge {\overline{t}}_{ip}$, otherwise ${\beta }_{ipt}=0$; that is, inmate $i$ can start program $p$ at time $t$ if ${\beta }_{ipt}=1$.

We would like to minimize the number of inmates who cannot start their programs earlier than their latest start time ${\widehat{t}}_{ip}$. The decision variable $y_{jpt}$ represents the number of inmates at facility $j$ who are prescribed program $p$ and have to start it by time $t$ but cannot do so. We aim to minimize $y_{jpt}$ by penalizing it in the objective function.

Let $\mathcal{T}=\left\{1,2,\dots ,t^{\prime }\right\}$ be the set of the periods in our decision horizon. Parameter $t^{\prime }$ is the last period in the decision horizon, and let ${\psi }_{jpt}$, ${\underset{¯}{q}}_{jpt}$, and ${\overline{q}}_{jpt}$ be defined as

• ${\psi }_{jpt}$: The number of inmates starting program $p$ at $t$ in facility $j$.

• ${\underset{¯}{q}}_{jpt}$: The number of inmates, already in facility $j$, who should start program $p$ at time $t$ or earlier, that is, the number of inmates with ${\widehat{t}}_{ip}\le t$

• ${\overline{q}}_{jpt}$: The maximum number of inmates, already in facility $j$, who can start program $p$ at time $t$, that is, the number of inmates with ${\overline{t}}_{ip}\le t$.

The following two sets of constraints compute the lower and upper bound on the number of inmates who can start the programs at each time period in the CIs.

$$\begin{array}{cc}\sum _{i\in \mathcal{I}}{\alpha }_{ipt}{x}_{ij}+{\underset{¯}{q}}_{jpt}& \le y_{jpt}+\sum _{\tau =0}^t{\psi }_{jp\tau }\forall j\in \mathcal{J},\forall p\in \mathcal{P},\forall t\in \mathcal{T},\\ \sum _{i\in \mathcal{I}}{\beta }_{ipt}{x}_{ij}+{\overline{q}}_{jpt}& \ge y_{jpt}\sum _{\tau =0}^t{\psi }_{jp\tau }\forall j\in \mathcal{J},\forall p\in \mathcal{P},\forall t\in \mathcal{T}.\end{array}$$

Let $R_{jpt}$ be the number of available spots for open enrollment program $p$ at time $t$ in facility $j$. The following constraints ensure that the number of inmates starting an open enrollment program does not exceed the number of spots available for that program at the CIs.

$$\sum _{\tau =\max \left(0,t-d_p\right)}^t{\psi }_{jp\tau }\le R_{jpt}\forall j\in \mathcal{J},\forall p\in {\mathcal{P}}^o,\forall t\in \mathcal{T},$$

where $d_p$ is the duration of program $p$.

Next we explain the constraints related to the closed enrollment programs. As mentioned previously, closed enrollment programs are categorized in clusters. All the programs in a cluster can be facilitated by one instructor (i.e., programs in a cluster use common instructors). Let $R_{jct}^{\prime }$ and ${\psi }_{jpt}^{\prime }$ be defined as

• ${\psi }_{jpt}^{\prime }$: The number of groups of the closed program $p$ that start at time $t$ in facility $j$.

• $R_{jct}^{\prime }$: The number of available groups of cluster $c$ that can start at time $t$ in facility $j$.

Then we have

$$\sum _{p\in {\mathcal{P}}_c}\sum _{\tau =\max \left(0,t-d_p\right)}^t{\psi }_{jp\tau }^{\prime }\le R_{jct}^{\prime }\forall j\in \mathcal{J},\forall c\in \mathcal{C},\forall t\in \mathcal{T},$$

where ${\mathcal{P}}_c$ is the set of the programs of the cluster $c$. Let ${\underset{¯}{G}}_p$ and ${\underset{¯}{G}}_p$ be, respectively, the minimum and maximum number of inmates who can be enrolled in closed enrollment program $p$. The following set of constraints enforces these capacity bounds for the closed enrollment programs.

$${\underset{¯}{G}}_p{\psi }_{jpt}^{\prime }\le {\psi }_{jpt}\le {\underset{¯}{G}}_p{\psi }_{jpt}^{\prime }\forall j\in \mathcal{J},\forall p\in {\mathcal{P}}^c,\forall t\in \mathcal{T}.$$

Scheduling of the Programs for the Inmates

One of the main objectives of the IAP is to minimize the maximum waiting time of inmates to start their program(s). In this section we present the constraints needed to minimize the maximum waiting time of inmates to start their program(s).

Let ${\mathcal{T}}^{\prime }=\mathcal{T}\cup \left\{\infty \right\}$, and let ${\mathcal{P}}_i$ be the set of the programs prescribed for inmate $i$. The new decision variable $z_{ijpt}$, for $i\in \mathcal{I},j\in \mathcal{J},p\in {\mathcal{P}}_i,t\in {\mathcal{T}}^{\prime }$, is equal to 1 if inmate $i$ is assigned to facility $j$, starting program $p$ at time $t$; otherwise, it is equal to 0. If $z_{ijp\infty }=1$, it implies that inmate $i$ is not going to start program $p$ in the decision horizon (i.e., later than the last period of the decision horizon). Following is the set of constraints that define the relationship between $z_{ijpt}$ and $x_{ij}$:

$$\sum _{t\in {\mathcal{T}}^{\prime }}{z}_{ijpt}=x_{ij}\forall i\in \mathcal{I},\forall j\in \mathcal{J},\forall p\in {\mathcal{P}}_i.$$

Let $y_{jpt}^a$ and ${\psi }_{jpt}^a$, for $j\in \mathcal{J},p\in \mathcal{P},t\in \mathcal{T}$, be defined as follows:

• $y_{jpt}^a$: The number of inmates already in facility $j$, who are prescribed program $p$ and have to start it by time $t$ but cannot do so.

• ${\psi }_{jpt}^a$: The number of inmates already in facility $j$, starting program $p$ at time $t$.

We have

$${\underset{¯}{q}}_{jpt}\le \sum _{\tau =0}^t{\psi }_{jp\tau }^a+y_{jpt}^a\le {\overline{q}}_{jpt}\forall j\in \mathcal{J},\forall p\in \mathcal{P},\forall t\in \mathcal{T}.$$

Additionally, let $y_{jpt}^n$ and ${\psi }_{jpt}^n$, for $j\in \mathcal{J},p\in \mathcal{P},t\in \mathcal{T}$, be defined as follows:

• $y_{jpt}^n$: The number of inmates assigned to facility $j$, who are prescribed program $p$ and have to start it by time $t$, but cannot do so.

• ${\psi }_{jpt}^n$: The number of inmates assigned to facility $j$, starting program $p$ at time $t$.

We have

$$\begin{array}{cc}{\psi }_{jpt}^n& =\sum _{i\in {\mathcal{I}}_p}{z}_{ijpt}\forall j\in \mathcal{J},\forall p\in \mathcal{P},\forall t\in \mathcal{T},\\ \sum _{i\in \mathcal{I}}{\alpha }_{ipt}{x}_{ij}& \le \sum _{\tau =1}^t{\psi }_{jp\tau }^n+y_{jpt}^n\\ & \le \sum _{i\in \mathcal{I}}{\beta }_{ipt}{x}_{ij}\forall j\in \mathcal{J},\forall p\in \mathcal{P},\forall t\in \mathcal{T},\end{array}$$

where ${\mathcal{I}}_p$ is the set of the inmates who need program $p$.

Suppose the number of inmates already in facility $j$ who should start program $p$ at time $t$ is more than the available spots for program $p$ at time $t$. Then we have $y_{jpt}^a>0$. In this case, ${\psi }_{jpt}^n$ should be equal to 0. In other words, if there are not enough spots of program $p$ for the inmates who are already in facility $j$, then the number of inmates, assigned to facility $j$ through the model, who are going to start program $p$ at time $t$ should be 0. To satisfy this constraint, the indicator variable ${\varphi }_{jpt}$, for $j\in \mathcal{J},p\in \mathcal{P},t\in \mathcal{T}$ is equal to 1 if $y_{jpt}^a>0$; otherwise, it is equal to 0. Then we have

$$\begin{array}{cc}& y_{jpt}^a\le M{\varphi }_{jpt}\forall j\in \mathcal{J},\forall p\in \mathcal{P},\forall t\in \mathcal{T},\\ & {\psi }_{jpt}^n\le M\left(1-{\varphi }_{jpt}\right)\forall j\in \mathcal{J},\forall p\in \mathcal{P},\forall t\in \mathcal{T},\end{array}$$

where $M$ is a big number.

Additionally, we have the following set of constraints, which defines the relationship between the decision variables of the problem

$$\begin{array}{cc}& {\psi }_{jpt}^a+{\psi }_{jpt}^n={\psi }_{jpt}\forall j\in \mathcal{J},\forall p\in \mathcal{P},\forall t\in \mathcal{T},\\ & y_{jpt}^a+y_{jpt}^n=y_{jpt}\forall j\in \mathcal{J},\forall p\in \mathcal{P},\forall t\in \mathcal{T}.\end{array}$$

Let $w_{ip}$, for $i\in \mathcal{I},p\in {\mathcal{P}}_i$ be the waiting time of inmate $i$ to start program $p$ after his (her) latest possible start time ${\widehat{t}}_{ip}$. We have

$$w_{ip}=\sum _{j\in \mathcal{J}}\sum _{t\in \mathcal{T}}\max \left(0,t-{\widehat{t}}_{ip}\right)z_{ijpt}\forall i\in \mathcal{I},\forall p\in {\mathcal{P}}_i.$$

Finally, let $w_i^{\prime }$ be the maximum waiting time of inmate $i$ to start his (her) program(s). Then

$$w_i^{\prime }\ge w_{ip}\forall i\in \mathcal{I},\forall p\in {\mathcal{P}}_i.$$

Transfer Constraints

The constraints needed to account for the inmate transfers after the initial assignment are the same kind of constraints as the ones for the initial assignment in the current model. However, because the importance of these constraints is frequently different for transfers, the weights of the factors in the objective function differ from an initial assignment.

The Objective Function

The IAP is a multiobjective problem. There are different approaches in the literature to deal with a multiobjective optimization problem. We consider the weighted sum method (Sawaragi et al. 1985) to combine the objectives and have a one-shot optimization in assigning the inmates. The choice of the weighted sum of the objectives is validated by solving real data instances from the Pennsylvania Department of Corrections. It is worth mentioning that the weights of all the objectives are assumed to be positive. The objectives of the IAP are listed as follows:

• Violation of the general factors should be minimized. The violation is equal to

  $$\vartheta =\sum _{i\in \mathcal{I}}\sum _{k\in \mathcal{K}}{\lambda }_{ik}^f{v}_{ik},$$
  where ${\lambda }_{ik}^f$ is the weight of factor $k$ for inmate $i$.

• Assignment of inmates under the capacity and over the capacity of the CIs should be minimized. The violations of the capacity constraints are defined as

  $$\begin{array}{cc}{o}_j& =\sum _{i\in \mathcal{I}}{x}_{ij}-c_j^{\max }\forall j\in \mathcal{J},\\ u_j& =c_j^{\min }-\sum _{i\in \mathcal{I}}{x}_{ij}\forall j\in \mathcal{J}.\end{array}$$
  Then, the overall capacity violation is equal to
  $$\eta =\sum _{j\in \mathcal{J}}{\lambda }_j^o{o}_j+{\lambda }_j^u{u}_j,$$
  where ${\lambda }_j^o$ and ${\lambda }_j^u$ for $j\in \mathcal{J}$ are, respectively, the weights of over-assignment and under-assignment to the CIs.

• The difference between the capacities of the CIs should be minimized.

  $$\delta ={\lambda }^{\delta }\sum _{j_1\in \mathcal{J}}\sum _{j_2\in \mathcal{J}\mid j_2\ne j_1}\left({\delta }_{j_1{j}_2}^{+},+,{\delta }_{j_1{j}_2}^{-}\right),$$
  where ${\lambda }^{\delta }$ is the weight of the capacity difference, and ${\delta }_{j_1{j}_2}^{+}$ and ${\delta }_{j_1{j}_2}^{-}$ are defined in Equation (A.1).

• Distance to the home county of the CIs should be minimized.

  $$\gamma =\sum _{i\in \mathcal{I}}\sum _{j\in \mathcal{J}}{\lambda }_i^d{d}_{ij}{x}_{ij},$$
  where ${\lambda }_i^d$ is the weight of the distance for inmate $i$.

• The number of inmates who cannot start their program on time should be minimized.

  $$\omega =\sum _{j\in \mathcal{J}}\sum _{p\in \mathcal{P}}\sum _{t\in \mathcal{T}}{\lambda }_{jpt}^{\omega }{y}_{jpt},$$
  where ${\lambda }_{jpt}^{\omega }$ is the weight of the wait list of program $p$ at facility $j$ in time $t$.

• The maximum program waiting time of inmates needs to be minimized.

  $$\theta =\sum _{i\in \mathcal{I}}{\lambda }_i^{\theta }{w}_i^{\prime },$$
  where ${\lambda }_i^t$ is the penalty weight of waiting time of inmate $i$.

The weighted sum of the objectives is defined as

$${\lambda }_{\vartheta }\vartheta +{\lambda }_{\eta }\eta +{\lambda }_{\delta }\delta +{\lambda }_{\gamma }\gamma +{\lambda }_{\omega }\omega +{\lambda }_{\theta }\theta ,$$

where the weights of all the objective elements are positive. Objective hierarchies are being enforced through order-of-magnitude differences in the weight applied. General factors have the highest priority in assigning inmates to CIs. Minimizing the maximum waiting time for each inmate is second in the hierarchy of objectives. Assigning in the range of the minimum and maximum capacity of each facility has the next highest priority. Additionally, to reduce the population of the CIs, program waiting lists have a high priority in the objective function. Assigning inmates to a facility near their home counties is less important compared with the other objectives of the problem.

The Multiobjective MILO Model

Now we present the complete optimization model for the inmate assignment and scheduling problem. The lists of parameters and decision variables of IAP are summarized in Tables A.1 and A.2, respectively. We utilize the hierarchically weighted sum method to combine the objectives and have a single-objective optimization problem. The MILO model is as follows:

$$\begin{array}{cc}\min & {\lambda }_{\vartheta }\vartheta +{\lambda }_{\eta }\eta +{\lambda }_{\delta }\delta +{\lambda }_{\gamma }\gamma +{\lambda }_{\omega }\omega +{\lambda }_{\tau }\tau \end{array}$$

$$\begin{array}{ccc}\mathrm{s}.\mathrm{t}.& \sum _{j\in \mathcal{J}}{x}_{ij}=1& \forall i\in \mathcal{I},\end{array}$$

$$\begin{array}{ccc}& \sum _{t\in {\mathcal{T}}^{\prime }}{z}_{ijpt}=x_{ij}& \forall i\in \mathcal{I},\forall j\in \mathcal{J},\forall p\in {\mathcal{P}}_i,\end{array}$$

$$\begin{array}{ccc}& {\psi }_{jpt}^n=\sum _{i\in {\mathcal{I}}_p}{z}_{ijpt},& \forall j\in \mathcal{J},\forall p\in \mathcal{P},\forall t\in \mathcal{T},\end{array}$$

$$\begin{array}{ccc}& {\kappa }_{ik}\left(1,-,\sum _{j\in \mathcal{J}},{\rho }_{jk},x_{ij}\right)=v_{ik}& \forall i\in \mathcal{I},\forall k\in \mathcal{K},\end{array}$$

$$\begin{array}{ccc}& \sum _{i\in \mathcal{I}}{\alpha }_{ipt}{x}_{ij}+{\underset{¯}{q}}_{jpt}\le y_{jpt}+\sum _{\tau =0}^t{\psi }_{jp\tau }& \forall j\in \mathcal{J},\forall p\in \mathcal{P},\forall t\in \mathcal{T},\end{array}$$

$$\begin{array}{ccc}& \sum _{i\in \mathcal{I}}{\beta }_{ipt}{x}_{ij}+{\overline{q}}_{jpt}\ge y_{jpt}+\sum _{\tau =0}^t{\psi }_{jp\tau }& \forall j\in \mathcal{J},\forall p\in \mathcal{P},\forall t\in \mathcal{T},\end{array}$$

$$\begin{array}{ccc}& \sum _{\tau =\max \left(0,t-d_p\right)}^t{\psi }_{jp\tau }\le R_{jpt}& \forall j\in \mathcal{J},\forall p\in {\mathcal{P}}^o,\forall t\in \mathcal{T},\end{array}$$

$$\begin{array}{ccc}& {\underset{¯}{G}}_p{\psi }_{jpt}^{\prime }\le {\psi }_{jpt}\le {\underset{¯}{G}}_p{\psi }_{jpt}^{\prime }& \forall j\in \mathcal{J},\forall p\in {\mathcal{P}}^c,\forall t\in \mathcal{T}\end{array}$$

$$\begin{array}{ccc}& \sum _{p\in {\mathcal{P}}_c}\sum _{\tau =\max \left(0,t-d_p\right)}^t{\psi }_{jp\tau }^{\prime }\le R_{jct}^{\prime }& \forall j\in \mathcal{J},\forall c\in \mathcal{C},\forall t\in \mathcal{T}\end{array}$$

$$\begin{array}{ccc}& {\underset{¯}{q}}_{jpt}\le \sum _{\tau =1}^t\left({\psi }_{jp\tau }^a\right)+y_{jpt}^a\le {\overline{q}}_{jpt}& \forall j\in \mathcal{J},\forall p\in \mathcal{P},\forall t\in \mathcal{T},\end{array}$$

$$\begin{array}{cc}\sum _{i\in \mathcal{I}}{\alpha }_{ipt}{x}_{ij}\le \sum _{\tau =1}^t\left({\psi }_{jpt}^n\right)+y_{jp\tau }^n\le \sum _{i\in \mathcal{I}}{\beta }_{ipt}{x}_{ij},& \forall j\in \mathcal{J},\forall p\in \mathcal{P},\forall t\in \mathcal{T},\end{array}$$

$$\begin{array}{ccc}& y_{jpt}^a\le M{\varphi }_{jpt}& \forall j\in \mathcal{J},\forall p\in \mathcal{P},\forall t\in \mathcal{T},\end{array}$$

$$\begin{array}{ccc}& {\psi }_{jpt}^n\le M\left(1-{\varphi }_{jpt}\right)& \forall j\in \mathcal{J},\forall p\in \mathcal{P},\forall t\in \mathcal{T},\end{array}$$

$$\begin{array}{ccc}& {\psi }_{jpt}^a+{\psi }_{jpt}^n={\psi }_{jpt}& \forall j\in \mathcal{J},\forall p\in \mathcal{P},\forall t\in \mathcal{T},\end{array}$$

$$\begin{array}{ccc}& y_{jpt}^a+y_{jpt}^n=y_{jpt}& \forall j\in \mathcal{J},\forall p\in \mathcal{P},\forall t\in \mathcal{T},\end{array}$$

$$\begin{array}{ccc}& w_{ip}=\sum _{j\in \mathcal{J}}\sum _{t\in \mathcal{T}}\max \left(0,t-{\widehat{t}}_{ip}\right)z_{ijpt}& \forall i\in \mathcal{I},\forall p\in {\mathcal{P}}_i,\end{array}$$

$$\begin{array}{ccc}& w_i^{\prime }\ge w_{ip}& \forall i\in \mathcal{I},\forall p\in {\mathcal{P}}_i,\end{array}$$

$$\begin{array}{ccc}& \sum _{i\in \mathcal{I}}{x}_{ij}=s_j& \forall j\in \mathcal{J},\end{array}$$

$$\begin{array}{ccc}& c_{j_2}{s}_{j_1}-c_{j_1}{s}_{j_2}={\delta }_{j_1{j}_2}^{+}-{\delta }_{j_1{j}_2}^{-}& \forall j_1,j_2\in \mathcal{J},\end{array}$$

$$\begin{array}{ccc}& s_j\le c_j^{\max }+o_j& \forall j\in \mathcal{J},\end{array}$$

$$\begin{array}{ccc}& s_j\ge c_j^{\min }-u_j& \forall j\in \mathcal{J},\end{array}$$

$$\begin{array}{ccc}& \sum _{j\in {\mathcal{J}}_i^s}{x}_{ij}=0& \forall i\in \mathcal{I},\end{array}$$

$$\begin{array}{ccc}& x_{i_{1}j}+x_{i_{2}j}\le 1& \forall \left(i_1,i_2\right)\in {\mathcal{I}}^s,\end{array}$$

$$\begin{array}{ccc}& z_{ijpt}\in \left\{0,1\right\}& \forall i\in \mathcal{I},\forall j\in \mathcal{J},\forall p\in {\mathcal{P}}_i,\forall t\in {\mathcal{T}}^{\prime },\end{array}$$

$$\begin{array}{ccc}& x_{ij}\in \left\{0,1\right\}& \forall i\in \mathcal{I},\forall j\in \mathcal{J},\end{array}$$

$$\begin{array}{ccc}& v_{ik}\in \left\{0,1\right\}& \forall i\in \mathcal{I},\forall k\in \mathcal{K},\end{array}$$

$$\begin{array}{ccc}& {\varphi }_{jpt}\in \left\{0,1\right\}& \forall j\in \mathcal{J},\forall p\in \mathcal{P},\forall t\in \mathcal{T},\end{array}$$

$$\begin{array}{ccc}& y_{jpt}^a,y_{jpt}^n,y_{jpt}\in \mathbb{N}& \forall j\in \mathcal{J},\forall p\in \mathcal{P},\forall t\in \mathcal{T},\end{array}$$

$$\begin{array}{ccc}& {\psi }_{jpt}^a,{\psi }_{jpt}^n,{\psi }_{jpt}\in \mathbb{N}& \forall j\in \mathcal{J},\forall p\in \mathcal{P},\forall t\in \mathcal{T},\end{array}$$

$$\begin{array}{ccc}& {\psi }_{jpt}^{\prime }\in \mathbb{N}& \forall j\in \mathcal{J},\forall p\in {\mathcal{P}}^c,\forall t\in \mathcal{T},\end{array}$$

$$\begin{array}{ccc}& s_j,o_j,u_j\in \mathbb{N}& \forall j\in \mathcal{J},\end{array}$$

$$\begin{array}{ccc}& {\delta }_{j_1{j}_2}^{+},{\delta }_{j_1{j}_2}^{-}\in \mathbb{N}& \forall j_1,j_2\in \mathcal{J},j_1\ne j_2,\end{array}$$

$$\begin{array}{ccc}& w_{ip}\ge 0& \forall i\in \mathcal{I},\forall p\in {\mathcal{P}}_i,\\ & w_i\ge 0& \forall i\in \mathcal{I}.\end{array}$$

We can strengthen the MILO model formulation by adding a set of constraints for the inmates who have prescribed program(s) as follows:

$$\sum _{j\in \mathcal{J}}\sum _{t\in {\mathcal{T}}^{\prime }}{z}_{ijpt}=1\forall i\in \mathcal{I},\forall p\in {\mathcal{P}}_i.$$

Although these constraints are redundant, notably if we add them to the model, the solution time decreases significantly. Further, to generate a good solution quickly, we set the MILO solver to perform the highest level of preprocessing before starting the branch-and-bound algorithm, which further reduces the overall solution time.

Table A.1. Parameters of the IAP

Table A.1. Parameters of the IAP

Parameter	Definition
$\mathcal{I}$	The set of inmates who need to be assigned
$\mathcal{J}$	The set of the CIs
$\mathcal{K}$	The set of factors
$\mathcal{P}$	The set of programs
${\mathcal{P}}^o$	The set of open enrollment programs
${\mathcal{P}}^c$	The set of closed enrollment programs
$\mathcal{C}$	The set of program clusters
${\mathcal{P}}_i$	The set of the program(s) of inmate $i$
${\mathcal{P}}_c$	The set of closed enrollment programs of cluster $c$
${\mathcal{J}}_i^s$	The set of CIs from which inmate $i$ should be separated
${\mathcal{I}}^s$	The set of inmate pairs who should be separated from each other
$\mathcal{T}$	The set of the periods in the time horizon
${\mathcal{T}}^{\prime }$	$\mathcal{T}\cup \infty$
${\kappa }_{ik}$	1 if factor $k$ applies to inmate $i$
	0 otherwise
${\rho }_{jk}$	1 if CI $j$ can accommodate inmates with factor $k$
	0 otherwise
$d_p$	The duration of program $p$
${\widehat{t}}_{ip}$	The latest time that inmate $i$ can start program $p$ and finish it before his (her) scheduled board interview
${\tilde{t}}_{ip}$	The earliest time that inmate $i$ can start program $p$ based on the system regulations
${\alpha }_{ipt}$	1 if inmate $i$ should not start program $p$ later than time $t$
	0 otherwise
${\beta }_{ipt}$	1 if inmate $i$ can start program $p$ at time $t$
	0 otherwise
${\underset{¯}{q}}_{jpt}$	The number of inmates, already in facility $j$, who should have started program $p$ by time $t$ to be able to finish their programs before their parole board meetings; that is, the number of inmates with ${\widehat{t}}_{ip}\le t$
${\overline{q}}_{jpt}$	The maximum number of inmates, already in facility $j$, who can start program $p$ at time $t$; that is, the number of inmates with ${\tilde{t}}_{ip}\le t$
$R_{jpt}$	Number of spots available for open enrollment program $p$ in CI $j$ at time period $t$
$R_{jct}^{\prime }$	Number of groups available for cluster $c$ in CI $j$ at time period $t$
${\underset{¯}{G}}_p$	Maximum number of inmates in a group of program $p$
${\underset{¯}{G}}_p$	Minimum number of inmates needed to run program $p$
$d_{ij}$	The distance between the home county of inmate $i$ to facility $j$
$c_j$	Capacity of facility $j$
$c_j^{\min },c_j^{\max }$	Minimum and maximum capacity at facility $j$, which are functions of $c_j$

Table A.2. Decision Variables of the IAP

Table A.2. Decision Variables of the IAP

Parameter	Definition
$x_{ij}$	1 if inmate $i$ is assigned to CI $j$
	0 otherwise
$z_{ijpt}$	1 if inmate $i$ is assigned to CI $j$, starting program p at time t
	0 otherwise
$v_{ik}$	1 if inmate $i$ violates factor $k$
	0 otherwise
${\psi }_{jpt}$	The number of inmates starting program $p$ at $t$ in facility $j$
${\psi }_{jpt}^a$	The number of inmates already in facility $j$, starting program $p$ at time $t$
${\psi }_{jpt}^n$	The number of inmates assigned to facility $j$, starting program $p$ at time $t$
${\psi }_{jpt}^{\prime }$	The number of groups of closed program $p$ that start at time $t$ in facility $j$
$y_{jpt}$	The number of inmates at facility $j$ who are prescribed program $p$ and have to start it by time $t$ but cannot do so
$y_{jpt}^a$	The number of inmates already in facility $j$, who are prescribed program $p$ and have to start it by time $t$ but cannot do so
$y_{jpt}^n$	The number of inmates assigned to facility $j$, who are prescribed program $p$ and have to start it by time $t$, but cannot do so
${\varphi }_{jpt}$	1 if $y_{jpt}^a>0$
	0 otherwise
$w_{ip}$	The waiting time of inmate $i$ to start program $p$ from his (her) latest possible start time ${\widehat{t}}_{ip}$
$w_i^{\prime }$	The maximum waiting time of inmate $i$ to start his (her) program(s)
$s_j$	The total number of inmates assigned to facility $j$
$o_j$	The number of inmates assigned over the maximum capacity of facility $j$
$u_j$	The number of inmates assigned under the minimum capacity of facility $j$
${\delta }_{j_1{j}_2}^{+},{\delta }_{j_1{j}_2}^{-}$	Variables representing the difference in capacities between the CIs $j_1$ and $j_2$