## Clustering Models and Algorithms for Land Consolidation

People: | Prof. Dr. Peter Gritzmann, Dr. Steffen Borgwardt |
---|---|

Partners: | Prof. Dr. Andreas Brieden ^{}, Dr. Paul-Michael Rintelen |

Period: | 2003 - today |

## Summary

In many agricultural regions, a small number of farmers cultivates a large number of small lots that are scattered over an extended area. Due to this, they have high driving costs, and cannot use heavy machinery profitably. We develop mathematical models and algorithms that do not share the issues of a classical land consolidation process. The central idea is that the lot structure of the region is kept as is. Some of these lots are fixed by the farmers, and the remaining ones are reassigned combinatorially, according to some objective function. During this process, each farmer has to obtain a set of lots that totals to about his original total size and value of lots. The lots differ with respect to both size and bonity, and due to this, we obtain a difficult constrained clustering problem: Deciding whether there is another distribution of the lots such that these constraints are satisfied already is an NP-complete problem. Still, using methods of combinatorial optimization, we obtain provably good and efficient approximation algorithms. The scope of this project is twofold, to continually improve on the mathematical model representing the real-world problem of land consolidation, and to develop improved algorithms for these models. |

## Selected Publications

- Steffen Borgwardt, Andreas Brieden and Peter Gritzmann (2009) Constrained Minimum-k-Star Clustering and its application to the consolidation of farmland
^{}, in Operational Research Volume 11, Number 1, pp. 1-17, Special Issue: Optimization in Agriculture (Part II) - Andreas Brieden and Peter Gritzmann (2004). A quadratic optimization model for the consolidation of farmland by means of lend-lease agreements. In: Operations Research Proceedings 2003: Selected Papers of the International Conference on Operations Research (OR 2003), (ed. by Ahr, D., Fahrion, R. , Oswald, M., and Reinelt, G.), Springer, Heidelberg, pp. 324-331.