We consider the household assignment problem as it occurs in the geo-referencing step of spatial microsimulation models. The resulting model is a maximum weight matching problem with additional side constraints. For real-world instances such as the one for the city of Trier in Germany, the number of binary variables exceeds 10^9, and the resulting instances are far from being solvable with standard solvers for mixed-integer linear optimization. Hence, we derive two methods to compute feasible points of good quality - one based on the Lagrangian relaxation of the side constraints and the other one based on problem-tailored decomposition strategies. For both, we theoretically analyze the obtained feasible points. Moreover, we extensively test the two proposed methods on real-world and synthetic data sets and compare it with Gurobi as a benchmark. Our results show that the methods are significantly faster while computing points that are very close to being optimal. The methods are also much more efficient in terms of memory usage, which renders the application of classic branch-and-bound solvers impossible for real-world instances. Finally, our results for the city of Trier also show a realistic demographic distribution, which illustrates the applicability of our approach in practice.
Article
View Computational Methods for the Household Assignment Problem