EUVIMEDEUVIMED entdecken
Open Access · CC BY 4.0

Computational Methods for the Household Assignment Problem

Ulf Friedrich, Lucas Moschen, Ralf Münnich, Martin Schmidt

Mathematical Methods of Operations Research · 14.08.2026

DOI: 10.1007/s00186-026-00933-7 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Mathematical Methods of Operations Research, online erschienen am 14.08.2026. Verfasst von Ulf Friedrich und 3 weiteren Autor:innen. Die Arbeit nennt 52 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0). Gefördert von: Deutsche Forschungsgemeinschaft.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

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$$ 10 9 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.

Förderung

  • Deutsche Forschungsgemeinschaft

Zitieren

APA

Friedrich, U., Moschen, L., Münnich, R., & Schmidt, M. (2026). Computational Methods for the Household Assignment Problem. Mathematical Methods of Operations Research. https://doi.org/10.1007/s00186-026-00933-7

Vancouver

Friedrich U, Moschen L, Münnich R, Schmidt M. Computational Methods for the Household Assignment Problem. Mathematical Methods of Operations Research. 2026. doi:10.1007/s00186-026-00933-7

BibTeX
@article{Friedrich2026,
  author = {Friedrich, Ulf and Moschen, Lucas and Münnich, Ralf and Schmidt, Martin},
  title = {Computational Methods for the Household Assignment Problem},
  journal = {Mathematical Methods of Operations Research},
  year = {2026},
  doi = {10.1007/s00186-026-00933-7}
}
Kostenlos starten →