Skip to main content
SpringerLink
Log in

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

  • General Paper
  • Published:
Journal of the Operational Research Society

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.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Figure 1

Similar content being viewed by others

References

  • Aloise D (2009). Exact minimum sum of square clustering. PhD Thesis, École Polytechnique de Montréal.

  • Apostol TM and Mnatsakanian MA (2003). Sums of squares of distances in m-space. American Mathematical Monthly 110 (2): 516–526.

    Article  Google Scholar 

  • Bação F, Lobo V and Painho M (2005). Applying genetic algorithms to zone design. Soft Computing 9 (5): 341–348.

    Article  Google Scholar 

  • Bergey PK, Ragsdale CT and Hoskote M (2003a). A decision support system for the electrical power districting problem. Decision Support Systems 36 (1): 1–17.

    Article  Google Scholar 

  • Bergey PK, Ragsdale CT and Hoskote M (2003b). A simulated annealing genetic algorithm for the electrical power districting problem. Annals of Operations Research 121 (1–4): 33–55.

    Article  Google Scholar 

  • Blais M, Lapierre S and Laporte G (2003). Solving a home-care districting problem in an urban setting. The Journal of the Operational Research Society 54 (11): 1141–1147.

    Article  Google Scholar 

  • Bozkaya B, Erkut E and Laporte G (2003). A tabu search heuristic and adaptive memory procedure for political districting. European Journal of Operational Research 144 (1): 12–26.

    Article  Google Scholar 

  • D’Amico SJ, Wang SJ, Batta R and Rump CM (2002). A simulated annealing approach to police district design. Computers & Operations Research 29 (6): 667–684.

    Article  Google Scholar 

  • Dantzig GB and Wolfe P (1960). Decomposition principle for linear programs. Operations Research 8 (1): 101–111.

    Article  Google Scholar 

  • de la Poix de Fréminville P (2012). Partitionnement d’une zone géographique en territoires homogénes et contigus. PhD Thesis, École Polytechnique de Montréal.

  • Desaulniers G, Desrosiers J and Solomon MM (2005). Column Generation. Springer-Verlag: New York.

    Book  Google Scholar 

  • Duan R (2010). New data structures for subgraph connectivity. ICALP 2010: 37th International Colloquium on Automata, Languages and Programming. Bordeaux, France, pp. 201–212.

  • Duan R (2011). Algorithms and dynamic data structures for basic graph optimization problems. PhD Thesis, University of Michigan.

  • Duque JC (2004). Design of homogeneous territorial units: A methodological proposal and applications. PhD Thesis, University of Barcelona.

  • Duque JC, Ramos R and Surinach J (2007). Supervised regionalization methods: A survey. International Regional Science Review 30 (3): 195–220.

    Article  Google Scholar 

  • Duque JC, Church RL and Middleton R (2011). The p-regions problem. Geographical Analysis 43 (3): 104–106.

    Article  Google Scholar 

  • Duque JC, Anselin L and Rey S (2012). The max-p-regions problem. Journal of Regional Science 52 (3): 397–419.

    Article  Google Scholar 

  • Ferland JA and Guénette G (1990). Decision support system for the school districting problem. Operations Research 38 (1): 15–21.

    Article  Google Scholar 

  • Garfinkel RS and Nemhauser GL (1970). Optimal political districting by implicit enumeration techniques. Management Science Series B—Application 16 (8): 495–508.

    Google Scholar 

  • Gilmore PC and Gomory RE (1961). A linear programming approach to the cutting-stock problem. Operations Research 9 (6): 849–859.

    Article  Google Scholar 

  • Guo D (2008). Regionalization with dynamically constrained agglomerative clustering and partitioning (REDCAP). International Journal of Geographical Information Science 22 (7): 801–823.

    Article  Google Scholar 

  • Guo D and Wang H (2011). Automatic region building for spatial analysis. Transactions in GIS 15 (1): 29–45.

    Article  Google Scholar 

  • Hansen P and Mladenovich N (2001). J-Means: A new local search heuristic for minimum sum of squares clustering. Pattern Recognition 34 (2): 405–413.

    Article  Google Scholar 

  • Hansen P, Jaumard B, Meyer C, Simeone B and Doring V (2003). Maximum split clustering under connectivity constraints. Journal of Classification 20 (2): 143–180.

    Article  Google Scholar 

  • Hess SW, Weaver JB, Siegfeld HJ, Whelan JN and Zitlau PA (1965). Nonpartisan political redistricting by computer. Operations Research 13 (6): 998–1006.

    Article  Google Scholar 

  • Horn ME (1995). Solution techniques for large regional partitioning problems. Geographical Analysis 27 (3): 230–248.

    Article  Google Scholar 

  • Macmillan W (2001). Redistricting in a GIS environment: An optimization algorithm using switching-points. Journal of Geographical Systems 3 (2): 167–180.

    Article  Google Scholar 

  • MacQueen J (1967). Some methods for classification and analysis of multivariate observations. In: Proceedings of 5th Berkeley Symposium on Mathematical Statistics and Probability, University of California, USA, Vol. 1, pp 281–297.

  • Margules C, Faith D and Belbin L (1985). An adjacency constraint in agglomerative hierarchical classifications of geographic data. Environment and Planning 17 (3): 397–412.

    Article  Google Scholar 

  • Mehrotra A, Johnson E and Nemhauser GL (1998). An optimization based heuristic for political districting. Management Science 44 (8): 1100–1114.

    Article  Google Scholar 

  • Muyldermans L, Cattrysse D, Oudheusden V and Lotan T (2002). Districting for salt spreading operations. European Journal of Operational Research 139 (3): 521–532.

    Article  Google Scholar 

  • Nagel S (1965). Simplified bipartisan computer redistricting. Stanford Law Review 17 (5): 863–899.

    Article  Google Scholar 

  • Openshaw S (1977). A geographical solution to scale and aggregation problems in region-building, partitioning and spatial modelling. Transactions of the Institute of British Geographers 2 (4): 459–472.

    Article  Google Scholar 

  • Openshaw S (1978). An optimal zoning approach to the study of spatially aggregated data. In: Masser I and Brown PJB (eds). Spatial Representation and Spatial Interaction. Springer Science+Business Media, Dordrecht, The Netherlands, pp 95–113.

    Chapter  Google Scholar 

  • Openshaw S and Rao L (1995). Algorithms for reengineering 1991 census geography. Environment and Planning 27 (3): 425–446.

    Article  Google Scholar 

  • Openshaw S and Wymer C (1995). Classifying and regionalizing census data. In: Openshaw S (ed). Census Users Handbook. GeoInformation International, Cambridge, UK, pp 239–270.

    Google Scholar 

  • Ricca F, Scozzari A and Simeone B (2011). Political districting: From classical models to recent approaches. 4OR: A Quarterly Journal of Operations Research 9 (3): 223–254.

    Article  Google Scholar 

  • Ricca F and Simeone B (2008). Local search algorithms for political districting. European Journal of Operations Research 189 (3): 1409–1426.

    Article  Google Scholar 

  • Tavares-Pereira F, Figueira J, Mousseau V and Roy B (2007). Multiple criteria districting problems. Annals of Operations Research 154 (1): 69–92.

    Article  Google Scholar 

  • Vickrey W (1961). On the prevention of gerrymandering. Political Science Quarterly 76 (1): 105–110.

    Article  Google Scholar 

  • Wise SM, Haining RP and Ma J (1997). Regionalisation tools for exploratory spatial analysis of health data. In: Fischer MM and Getis A (eds). Recent Developments in Spatial Analysis: Spatial Statistics, Behavioural Modelling, and Computational Intelligence. Springer; Berlin Heidelberg, pp 83–100.

    Chapter  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Artelys, Paris, France

    Pierre de la Poix de Fréminville

  2. Department of Mathematics and Industrial Engineering, Polytechnique Montréal, Montréal, Canada

    Guy Desaulniers & Louis-Martin Rousseau

  3. GERAD, Montréal, Canada

    Guy Desaulniers & Sylvain Perron

  4. CIRRELT, Montréal, Canada

    Louis-Martin Rousseau

  5. Department of Management Sciences, HEC Montréal, Montréal, Canada

    Sylvain Perron

Authors
  1. Pierre de la Poix de Fréminville
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Guy Desaulniers
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Louis-Martin Rousseau
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Sylvain Perron
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Louis-Martin Rousseau.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

de Fréminville, P., Desaulniers, G., Rousseau, LM. et al. A column generation heuristic for districting the price of a financial product. J Oper Res Soc 66, 965–978 (2015). https://doi.org/10.1057/jors.2014.64

Download citation

  • Received:

  • Revised:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1057/jors.2014.64

Keywords

Search

Navigation