Computational Methods for the Household Assignment Problem

Abstract We consider the problem of assigning the entries of a household data set to real-world address data. This household assignment problem occurs in the geo-referencing step of spatial microsimulation models. The resulting combinatorial optimization model is a maximum weight matching problem with additional side constraints. Even for real-world instances of medium size, such as the city of Trier in Germany, the number of binary variables in the model exceeds $$10^9$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msup> <mml:mn>10</mml:mn> <mml:mn>9</mml:mn> </mml:msup> </mml:math> and the resulting instances are computationally intractable for 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. We theoretically analyze the feasible points obtained by both methods. Moreover, we extensively test the two proposed methods on both real-world and synthetic data sets. Our results show that the proposed methods are significantly faster than applied to the original mixed-integer problem while computing near-optimal points. The methods are more efficient in terms of memory usage, which is extremely high for solvers such as when applied to realistic instances, rendering their application to real-world instances infeasible. Finally, our results for the city of Trier show a realistic demographic distribution, which illustrates the applicability of our approach in practice.