Groupe d’études et de recherche en analyse des décisions

G-2013-22

A Column Generation Heuristic for Districting the Price of a Financial Product

, , et

This paper studies a districting problem which 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 non linear 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.

, 20 pages