×

Optimization models for targeted offers in direct marketing: exact and heuristic algorithms. (English) Zbl 1213.90149

Summary: This paper presents an optimization model for the selection of sets of clients that will receive an offer for one or more products during a promotion campaign. We show that the problem is strongly NP-hard and that it is unlikely that a constant-factor approximation algorithm can be proposed for solving this problem. We propose an alternative set-covering formulation and develop a branch-and-price algorithm to solve it. We also describe eight heuristics to approximate an optimal solution, including a depth-first branch-and-price heuristic and a tabu-search algorithm. We perform extensive computational experiments both with the exact as well as with the heuristic algorithms. Based on our experiments, we suggest the use of optimal algorithms for small and medium-size instances, while heuristics (especially tabu search and branch-and-price-based routines) are preferable for large instances and when time is an important factor.

MSC:

90B60 Marketing, advertising
90C10 Integer programming
90C59 Approximation methods and heuristics in mathematical programming
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] (Aarts, E.; Lenstra, J. K., Local Search in Combinatorial Optimization (1997), Wiley) · Zbl 0869.00019
[2] Barnhart, C.; Johnson, E.; Savelsbergh, M., Branch-and-price: Column generation for solving huge integer programs, Operations Research, 46, 316-329 (1998) · Zbl 0979.90092
[3] Bernstel, J. B., Smart move: Creating ‘intelligent’ database, ABA Bank Marketing, 34, 14-19 (2002)
[4] Bhaskar, T.; Sundararajan, R.; Krishnan, P. G., A fuzzy mathematical programming approach for cross-sell optimization in retail banking, Journal of the Operational Research Society, 60, 717-727 (2009) · Zbl 1171.90568
[5] Bose, I.; Chen, X., Quantitative models for direct marketing: A review from a systems perspective, European Journal of Operational Research, 195, 1-16 (2009) · Zbl 1159.90434
[6] Bruner, R. C.; Eades, K. M.; Harris, R. S.; Higgins, R. C., Best practices in estimating the cost of capital: Survey and synthesis, Financial Practice and Education, 8, 13-28 (1998)
[7] Caprara, A.; Kellerer, H.; Pferschy, U.; Pisinger, D., Approximation algorithms for knapsack problems with cardinality constraints, European Journal of Operational Research, 123, 333-345 (2000) · Zbl 0961.90131
[8] Cohen, M., Exploiting response models - Optimizing cross-sell and up-sell opportunities in banking, Information Systems, 29, 327-341 (2004)
[9] De Reyck, B.; Degraeve, Z., Broadcast scheduling for mobile advertising, Operations Research, 51, 509-517 (2003) · Zbl 1165.90559
[10] Dwyer, F. R., Customer lifetime valuation to support marketing decision making, Journal of Direct Marketing, 11, 6-13 (1997)
[11] Garey, M. R.; Johnson, D. S., Computers and Intractability: A Guide to the Theory of NP-Completeness (1979), W.H. Freeman and Co. · Zbl 0411.68039
[12] Gerson, V., Right on target, ABA Bank Marketing, 30, 277-293 (1998)
[13] Air Transport Action Group, The Economic and Social Benefits of Air Transport, Technical Report, December 2007.; Air Transport Action Group, The Economic and Social Benefits of Air Transport, Technical Report, December 2007.
[14] Guadagni, P. M.; Little, J. D.C., A logit model of brand choice calibrated on scanner data, Marketing Science, 2, 203-238 (1983)
[15] Guiltinan, J. P., The price bundling of services: A normative framework, Journal of Marketing, 51, 74-85 (1987)
[16] Hanssens, D. M.; Leeflang, P. S.H.; Wittink, D. R., Market response models and marketing practice, Applied Stochastic Models in Business and Industry, 21, 423-434 (2005) · Zbl 1126.90370
[17] E. Hellinckx, Customer Relationship Management: De optimalisatie van de Planning van campagnes, Master’s Thesis, Department of Applied Economics, KULeuven, 2004 (in Dutch).; E. Hellinckx, Customer Relationship Management: De optimalisatie van de Planning van campagnes, Master’s Thesis, Department of Applied Economics, KULeuven, 2004 (in Dutch).
[18] Kellerer, H.; Pferschy, U.; Pisinger, D., Knapsack Problems (2004), Springer · Zbl 1103.90003
[19] Knott, A.; Hayes, A.; Neslin, S. A., Next-product-to-buy models for cross-selling applications, Journal of Interactive Marketing, 16, 59-75 (2002)
[20] Kotler, P.; Armstrong, G., Principles of Marketing (2006), Pearson Prentice Hall
[21] Kumar, V.; Ramani, G.; Bohling, T., Customer lifetime value approaches and best practice applications, Journal of Interactive Marketing, 18, 60-72 (2004)
[22] Laguna, M.; Kelly, J. P.; González-Velarde, J. L.; Glover, F., Tabu search for the multilevel generalized assignment problem, European Journal of Operational Research, 82, 176-189 (1995) · Zbl 0905.90122
[23] Li, S.; Sun, B.; Wilcox, R. T., Cross-selling sequentially ordered products: An application to consumer banking services, Journal of Marketing Research, XLII, 233-239 (2005)
[24] Lim, A.; Wang, F.; Xu, Z., On the selection and assignment with minimum quantity commitments, Lecture Notes in Computer Science, 3106, 102-111 (2004) · Zbl 1091.90529
[25] Lim, A.; Wang, F.; Xu, Z., A transportation problem with minimum quantity commitment, Transportation Science, 40, 117-129 (2006)
[26] Lim, A.; Xu, Z., The bottleneck problem with minimum quantity commitment, Naval Research Logistics, 53, 91-100 (2006) · Zbl 1112.90069
[27] Z. Luo, L. Tang, W. Zhang, Using branch-and-price algorithm to solve raw materials logistics planning problem in iron and steel industry, in: 2007 International Conference on Management Science and Engineering, 2007, pp. 529-536.; Z. Luo, L. Tang, W. Zhang, Using branch-and-price algorithm to solve raw materials logistics planning problem in iron and steel industry, in: 2007 International Conference on Management Science and Engineering, 2007, pp. 529-536.
[28] Mankila, M., Retaining students in retail banking through price bundling: Evidence from the swedish market, European Journal of Operational Research, 155, 299-316 (2004) · Zbl 1043.91518
[29] Martello, S.; Toth, P., Knapsack Problems: Algorithms and Computer Implementation (1990), John Wiley and Sons
[30] Nemhauser, G. L.; Wolsey, L. A., Integer and Combinatorial Optimization (1988), Wiley · Zbl 0469.90052
[31] Prinzie, A.; Van Den Poel, D., Investigating purchasing-sequence patterns for financial services using Markov, MTD and MTDg models, European Journal of Operational Research, 170, 710-734 (2006) · Zbl 1091.90527
[32] Prinzie, A.; Van Den Poel, D., Predicting home-appliance acquisition sequences: Markov/Markov for discrimination and survival analysis for modeling sequential information in NPTB models, Decision Support Systems, 44, 28-45 (2007)
[33] Reinartz, W.; Thomas, J. S.; Kumar, V., Balancing acquisition and retention resources to maximize customer profitability, Journal of Marketing, 69, 63-79 (2005)
[34] Ryals, L., Making customer relationship management work: The measurement and the profitable management of customer relationships, Journal of Marketing, 69, 252-261 (2005)
[35] Savelsbergh, M., A branch-and-price algorithm for the generalized assignment problem, Operations Research, 45, 831-841 (1997) · Zbl 0895.90161
[36] Stone, B.; Jacobs, R., Successful Direct Marketing Methods: Interactive, Database, and Customer-based Marketing for Digital Age (2008), McGraw-Hill Professional
[37] F. Talla Nobibon, R. Leus, F.C.R. Spieksma, Models for the Optimization of Promotion Campaigns: Exact and Heuristic Algorithms, Research Report KBI_0814, Katholieke Universiteit Leuven, 2008.; F. Talla Nobibon, R. Leus, F.C.R. Spieksma, Models for the Optimization of Promotion Campaigns: Exact and Heuristic Algorithms, Research Report KBI_0814, Katholieke Universiteit Leuven, 2008. · Zbl 1213.90149
[38] Tripathi, A. K.; Nair, S. K., Narrowcasting of wireless advertising in malls, European Journal of Operational Research, 182, 1023-1038 (2007) · Zbl 1121.90081
[39] Van Den Akker, J. M.; Hoogeveen, J. A.; Van Kempen, J. W., Parallel machine scheduling through column generation: Minimax objectives (extended abstract), Lecture Notes in Computer Science, 4168, 648-659 (2006) · Zbl 1131.90366
[40] N. Van Praag, Optimization of Promotion Campaigns Using Tabu Search, Master’s Thesis, Faculty of Business and Economics, KULeuven, 2010.; N. Van Praag, Optimization of Promotion Campaigns Using Tabu Search, Master’s Thesis, Faculty of Business and Economics, KULeuven, 2010.
[41] P.H. Vance, A. Atamturk, C. Barnhart, E. Gelman, E.L. Johnson, A. Krishna, G.L. Nemhauser, R. Rebello, A Heuristic Branch-and-Price Approach for the Airline Crew Pairing Problem, Technical Report LEC-97-06, Georgia Institute of Technology, 1997.; P.H. Vance, A. Atamturk, C. Barnhart, E. Gelman, E.L. Johnson, A. Krishna, G.L. Nemhauser, R. Rebello, A Heuristic Branch-and-Price Approach for the Airline Crew Pairing Problem, Technical Report LEC-97-06, Georgia Institute of Technology, 1997.
[42] Wolsey, L. A., Integer Programming (1998), Wiley · Zbl 0299.90012
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.