Lucas Moschen

• Spatial microsimulation is an important tool for integrating geographical information into the evaluation of public policies and the analysis of social phenomena in urban regions. These models simulate the behavior and interaction between units of the region, such as individuals, households or firms, under specific conditions that may or not involve projections over time. This requires a representative base data set for their respective units. In this thesis, we focus on the geo-referencing step of the population in the construction of this data set, where we define the location of the individuals so that the allocation obtained is representative in relation to the population of the region. To do this, we consider the assignment of households to dwellings with specific coordinates by solving a maximum weight matching problem where side constraints are included so that the allocation obtained satisfies statistical structures intrinsic to the considered region. The model of this problem represents each feasible assignment of household to dwelling as a binary variable, which results in billions of variables for medium-sized municipalities such as the city of Trier, Germany. Therefore, standard solvers for mixed-integer linear optimization are not able to solve it due to their high time and memory consumption. Hence, we develop two approaches capable of producing high-quality allocations using a reasonable amount of computational resources, one based on specific decomposition algorithms, and the other characterized by the application of an approximation algorithm in the framework of Lagrangian relaxation of the side constraints. We theoretically explore the allocations obtained by both approaches and perform an extensive computational study using synthetic data sets and real-world data sets associated with the city of Trier. The results show that the developed methods are able to obtain near-optimal solutions using significantly less memory and time than the solver Gurobi, which enables them to tackle significantly larger instances, with approximately 100 000 households and dwellings. Furthermore, the allocations obtained for the real-world data sets correspond to a realistic population distribution, which strengthens the practical applicability of our methods.