IDEAS home Printed from https://ideas.repec.org/a/eee/ejores/v304y2023i2p689-708.html
   My bibliography  Save this article

A matheuristic for a customer assignment problem in direct marketing

Author

Listed:
  • Bigler, T.
  • Kammermann, M.
  • Baumann, P.

Abstract

In direct marketing, companies use sales campaigns to target their customers with personalized product offers. The effectiveness of direct marketing greatly depends on the assignment of customers to campaigns. In this paper, we consider a real-world planning problem of a major telecommunications company that assigns its customers to individual activities of its direct marketing campaigns. Various side constraints, such as budgets and sales targets, must be met. Conflict constraints ensure that individual customers are not assigned too frequently to similar activities. Related problems have been addressed in the literature; however, none of the existing approaches cover all the side constraints considered here. To close this gap, we develop a matheuristic that employs a new decomposition strategy to cope with the large number of conflict constraints in typical problem instances. In a computational experiment, we compare the performance of the proposed matheuristic to the performance of two mixed-binary linear programs on a test set that includes large-scale real-world instances. The matheuristic derives near-optimal solutions in short running times for small- to medium-sized instances and scales to instances of practical size comprising millions of customers and hundreds of activities. The deployment of the matheuristic at the company has considerably increased the overall effectiveness of its direct marketing campaigns.

Suggested Citation

  • Bigler, T. & Kammermann, M. & Baumann, P., 2023. "A matheuristic for a customer assignment problem in direct marketing," European Journal of Operational Research, Elsevier, vol. 304(2), pages 689-708.
  • Handle: RePEc:eee:ejores:v:304:y:2023:i:2:p:689-708
    DOI: 10.1016/j.ejor.2022.04.009
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0377221722003071
    Download Restriction: Full text for ScienceDirect subscribers only

    File URL: https://libkey.io/10.1016/j.ejor.2022.04.009?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Ma, Shaohui & Fildes, Robert, 2017. "A retail store SKU promotions optimization model for category multi-period profit maximization," European Journal of Operational Research, Elsevier, vol. 260(2), pages 680-692.
    2. Şuvak, Zeynep & Altınel, İ. Kuban & Aras, Necati, 2020. "Exact solution algorithms for the maximum flow problem with additional conflict constraints," European Journal of Operational Research, Elsevier, vol. 287(2), pages 410-437.
    3. Ma, Shaohui & Hou, Lu & Yao, Wensong & Lee, Baozhen, 2016. "A nonhomogeneous hidden Markov model of response dynamics and mailing optimization in direct marketing," European Journal of Operational Research, Elsevier, vol. 253(2), pages 514-523.
    4. Vera L. Miguéis & Ana S. Camanho & José Borges, 2017. "Predicting direct marketing response in banking: comparison of class imbalance methods," Service Business, Springer;Pan-Pacific Business Association, vol. 11(4), pages 831-849, December.
    5. Filiz Cetin & Cigdem Alabas-Uslu, 2017. "Heuristic solution to the product targeting problem based on mathematical programming," International Journal of Production Research, Taylor & Francis Journals, vol. 55(1), pages 3-17, January.
    6. Nair, Suresh K. & Tarasewich, Peter, 2003. "A model and solution method for multi-period sales promotion design," European Journal of Operational Research, Elsevier, vol. 150(3), pages 672-687, November.
    7. Ruslan Sadykov & François Vanderbeck, 2013. "Bin Packing with Conflicts: A Generic Branch-and-Price Algorithm," INFORMS Journal on Computing, INFORMS, vol. 25(2), pages 244-255, May.
    8. T Bhaskar & R Sundararajan & P G Krishnan, 2009. "A fuzzy mathematical programming approach for cross-sell optimization in retail banking," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 60(5), pages 717-727, May.
    9. Marshall L. Fisher, 1985. "An Applications Oriented Guide to Lagrangian Relaxation," Interfaces, INFORMS, vol. 15(2), pages 10-21, April.
    10. S Delanote & R Leus & F Talla Nobibon, 2013. "Optimization of the annual planning of targeted offers in direct marketing," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 64(12), pages 1770-1779, December.
    11. Marshall L. Fisher, 1981. "The Lagrangian Relaxation Method for Solving Integer Programming Problems," Management Science, INFORMS, vol. 27(1), pages 1-18, January.
    12. Coniglio, Stefano & Furini, Fabio & San Segundo, Pablo, 2021. "A new combinatorial branch-and-bound algorithm for the Knapsack Problem with Conflicts," European Journal of Operational Research, Elsevier, vol. 289(2), pages 435-455.
    13. Jose L. Walteros & Austin Buchanan, 2020. "Why Is Maximum Clique Often Easy in Practice?," Operations Research, INFORMS, vol. 68(6), pages 1866-1895, November.
    14. Samir Elhedhli & Lingzi Li & Mariem Gzara & Joe Naoum-Sawaya, 2011. "A Branch-and-Price Algorithm for the Bin Packing Problem with Conflicts," INFORMS Journal on Computing, INFORMS, vol. 23(3), pages 404-415, August.
    15. Sun, Minghe, 2002. "The transportation problem with exclusionary side constraints and two branch-and-bound algorithms," European Journal of Operational Research, Elsevier, vol. 140(3), pages 629-647, August.
    16. Ramasubramanian Sundararajan & Tarun Bhaskar & Abhinanda Sarkar & Sridhar Dasaratha & Debasis Bal & Jayanth K. Marasanapalle & Beata Zmudzka & Karolina Bak, 2011. "Marketing Optimization in Retail Banking," Interfaces, INFORMS, vol. 41(5), pages 485-505, October.
    17. Talla Nobibon, Fabrice & Leus, Roel & Spieksma, Frits C.R., 2011. "Optimization models for targeted offers in direct marketing: Exact and heuristic algorithms," European Journal of Operational Research, Elsevier, vol. 210(3), pages 670-683, May.
    18. Andrea Bettinelli & Valentina Cacchiani & Enrico Malaguti, 2017. "A Branch-and-Bound Algorithm for the Knapsack Problem with Conflict Graph," INFORMS Journal on Computing, INFORMS, vol. 29(3), pages 457-473, August.
    Full references (including those not matched with items on IDEAS)

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Orlando Rivera Letelier & François Clautiaux & Ruslan Sadykov, 2022. "Bin Packing Problem with Time Lags," INFORMS Journal on Computing, INFORMS, vol. 34(4), pages 2249-2270, July.
    2. Şuvak, Zeynep & Altınel, İ. Kuban & Aras, Necati, 2020. "Exact solution algorithms for the maximum flow problem with additional conflict constraints," European Journal of Operational Research, Elsevier, vol. 287(2), pages 410-437.
    3. Lijun Wei & Zhixing Luo, & Roberto Baldacci & Andrew Lim, 2020. "A New Branch-and-Price-and-Cut Algorithm for One-Dimensional Bin-Packing Problems," INFORMS Journal on Computing, INFORMS, vol. 32(2), pages 428-443, April.
    4. Saharnaz Mehrani & Carlos Cardonha & David Bergman, 2022. "Models and Algorithms for the Bin-Packing Problem with Minimum Color Fragmentation," INFORMS Journal on Computing, INFORMS, vol. 34(2), pages 1070-1085, March.
    5. San Segundo, Pablo & Furini, Fabio & Álvarez, David & Pardalos, Panos M., 2023. "CliSAT: A new exact algorithm for hard maximum clique problems," European Journal of Operational Research, Elsevier, vol. 307(3), pages 1008-1025.
    6. Coniglio, Stefano & Furini, Fabio & San Segundo, Pablo, 2021. "A new combinatorial branch-and-bound algorithm for the Knapsack Problem with Conflicts," European Journal of Operational Research, Elsevier, vol. 289(2), pages 435-455.
    7. Ogbe, Emmanuel & Li, Xiang, 2017. "A new cross decomposition method for stochastic mixed-integer linear programming," European Journal of Operational Research, Elsevier, vol. 256(2), pages 487-499.
    8. Mahsa Samsami & Ralf Wagner, 2021. "Investment Decisions with Endogeneity: A Dirichlet Tree Analysis," JRFM, MDPI, vol. 14(7), pages 1-19, July.
    9. Mazzola, Joseph B. & Neebe, Alan W., 1999. "Lagrangian-relaxation-based solution procedures for a multiproduct capacitated facility location problem with choice of facility type," European Journal of Operational Research, Elsevier, vol. 115(2), pages 285-299, June.
    10. Andrea Bettinelli & Valentina Cacchiani & Enrico Malaguti, 2017. "A Branch-and-Bound Algorithm for the Knapsack Problem with Conflict Graph," INFORMS Journal on Computing, INFORMS, vol. 29(3), pages 457-473, August.
    11. Eva Ascarza & Scott A. Neslin & Oded Netzer & Zachery Anderson & Peter S. Fader & Sunil Gupta & Bruce G. S. Hardie & Aurélie Lemmens & Barak Libai & David Neal & Foster Provost & Rom Schrift, 2018. "In Pursuit of Enhanced Customer Retention Management: Review, Key Issues, and Future Directions," Customer Needs and Solutions, Springer;Institute for Sustainable Innovation and Growth (iSIG), vol. 5(1), pages 65-81, March.
    12. Huisman, D. & Jans, R.F. & Peeters, M. & Wagelmans, A.P.M., 2003. "Combining Column Generation and Lagrangian Relaxation," ERIM Report Series Research in Management ERS-2003-092-LIS, Erasmus Research Institute of Management (ERIM), ERIM is the joint research institute of the Rotterdam School of Management, Erasmus University and the Erasmus School of Economics (ESE) at Erasmus University Rotterdam.
    13. J. E. Beasley, 1990. "A lagrangian heuristic for set‐covering problems," Naval Research Logistics (NRL), John Wiley & Sons, vol. 37(1), pages 151-164, February.
    14. Lawrence V. Snyder & Mark S. Daskin, 2005. "Reliability Models for Facility Location: The Expected Failure Cost Case," Transportation Science, INFORMS, vol. 39(3), pages 400-416, August.
    15. X-Y Li & Y P Aneja & F Baki, 2010. "An ant colony optimization metaheuristic for single-path multicommodity network flow problems," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 61(9), pages 1340-1355, September.
    16. Renatha Capua & Yuri Frota & Luiz Satoru Ochi & Thibaut Vidal, 2018. "A study on exponential-size neighborhoods for the bin packing problem with conflicts," Journal of Heuristics, Springer, vol. 24(4), pages 667-695, August.
    17. Ahmadi, Reza H. & Kouvelis, Panagiotis, 1999. "Design of electronic assembly lines: An analytical framework and its application," European Journal of Operational Research, Elsevier, vol. 115(1), pages 113-137, May.
    18. Beasley, J. E. & Cao, B., 1996. "A tree search algorithm for the crew scheduling problem," European Journal of Operational Research, Elsevier, vol. 94(3), pages 517-526, November.
    19. Ojeong Kwon & Donghan Kang & Kyungsik Lee & Sungsoo Park, 1999. "Lagrangian relaxation approach to the targeting problem," Naval Research Logistics (NRL), John Wiley & Sons, vol. 46(6), pages 640-653, September.
    20. Ali Diabat & Jean-Philippe Richard & Craig Codrington, 2013. "A Lagrangian relaxation approach to simultaneous strategic and tactical planning in supply chain design," Annals of Operations Research, Springer, vol. 203(1), pages 55-80, March.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:eee:ejores:v:304:y:2023:i:2:p:689-708. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Catherine Liu (email available below). General contact details of provider: http://www.elsevier.com/locate/eor .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.