A column generation heuristic for districting the price of a financial product

Abstract

This paper studies a districting problem that arises in the context of financial product pricing. The challenge lies in partitioning a set of small geographical regions into a set of larger territories. In each territory, the customers will share a common price. These territories need to be contiguous, contain enough customers and be as homogeneous as possible in terms of customer value. To address this problem, we present a column generation-based heuristic where the subproblem generates contiguous territories taken into account a nonlinear objective function. Computational results indicate that the territories produced by this heuristic are about 35% more homogeneous than those previously used in practice. The developed algorithm has been transferred to a financial firm and is now used to help craft more competitive financial products.

Keywords:

• districting
• financial product pricing
• clustering
• column generation
• heuristic