Refugee resettlement is the process of relocating individuals who have fled their home country, have had their asylum claims vetted, and need a durable solution, such as relocation to a third country. In the United States, this process is typically carried out by nine resettlement agencies that partner with federal agencies and work with refugees to secure housing, employment, healthcare, and education. This process has traditionally been done manually by expert resettlement staff with in-depth knowledge of the communities in which they work, yet limited knowledge of the individual refugees arriving at any given time.

To partially automate this process and better match refugees to communities, we developed advanced analytical methods using machine learning and optimization. Our goal was to empower resettlement staff with recommendations for refugee-community matches that would improve the chances of successful resettlement outcomes. To do this, we used predictive models to estimate the likelihood of employment for incoming refugees across different communities in the United States. These likelihood estimates were then used in constrained optimization problems to match refugees to communities in a way that maximizes the total expected employment. The constrained optimization problems we formulated were multiple multidimensional knapsack problems, ensuring that community capabilities and capacities for refugees were respected.

While knapsack problems are computationally challenging, we were able to develop solvable prescriptive optimization models that were embedded in decision support software. This software was deployed and is currently in active use at a major US resettlement agency. It provides complete autonomy to the decision-making process, by recommending refugee-community matches and yet allowing interactivity to refine placement recommendations through expert judgement, and subsequently re-optimize to converge upon a final match outcome. Our computational studies estimate that our approach resulted in gains of nearly 30% over the manual placement process.

In addition to automating the refugee matching process, we also extended our software to incorporate dynamic capacity management. This is important because while resettlement agencies place refugees into communities on a roughly weekly basis, community capacity is set annually by the Federal government. By simulating future arrivals throughout the rest of the year, we were able to estimate the marginal value of an additional slot of capacity and adjust the value obtained for placing a refugee into a community in the current placement period. This allowed us to effectively manage community capacity that is particularly valuable, such as those where employment tends to be more likely, throughout the year. Our methods were able to obtain over 98% of the hindsight optimal total employment. The figure below depicts a view of the developed interactive optimization software.

We also explored new approaches for solving integer programs using level set approaches based on integral monoids. These approaches are useful for integer optimization problems where right-hand sides, such as capacity, are uncertain. In such cases, it can be helpful to consider the integer programming value function, which is defined as the optimal objective function of an integer optimization problem parameterized by its right-hand side. For problems like the multiple multidimensional knapsack problems we considered, the structure formed by the constraints can be leveraged to store solution information, which enables us to solve the problems more efficiently. The figure below depicts the integer programming value function for an integer program with two constraints, as the value of the right-hand side in each dimension is incremented. The knowledge of how beneficial additional units of capacity can be on the optimal objective function value can inform decision-makers on the benefits of expanding capacity.

Throughout this project, we were able to support four undergraduate REU students and three female PhD students through research assistantships and internships. These students were able to gain valuable experience in the field of refugee resettlement and contribute to the development of our advanced analytical methods and software. We are grateful for the opportunity to work with such talented and dedicated individuals, and we believe that the skills and knowledge they gained through this project will be valuable in their future careers.

Research outcomes were disseminated in major media outlets and leading peer-reviewed journals in the fields of operations research, computer science, and social science, highlighting the importance of our research in addressing the challenges of refugee resettlement and the potential impact of our approach on improving the lives of refugees. The results of this award have had a significant impact on the field of refugee resettlement, both in terms of the practical tools we have developed and the new insights and techniques we have introduced.

Last Modified: 12/23/2022
Modified by: Andrew C Trapp