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

Optimization models for targeted offers in direct marketing: Exact and heuristic algorithms

Author

Listed:
  • Talla Nobibon, Fabrice
  • Leus, Roel
  • Spieksma, Frits C.R.

Abstract

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.

Suggested Citation

  • 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.
    • Handle: RePEc:eee:ejores:v:210:y:2011:i:3:p:670-683
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0377-2217(10)00660-0
    Download Restriction: Full text for ScienceDirect subscribers only
    ---><---

    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. Laguna, Manuel & Kelly, James P. & Gonzalez-Velarde, JoseLuis & Glover, Fred, 1995. "Tabu search for the multilevel generalized assignment problem," European Journal of Operational Research, Elsevier, vol. 82(1), pages 176-189, April.
    2. Caprara, Alberto & Kellerer, Hans & Pferschy, Ulrich & Pisinger, David, 2000. "Approximation algorithms for knapsack problems with cardinality constraints," European Journal of Operational Research, Elsevier, vol. 123(2), pages 333-345, June.
    3. Martin Savelsbergh, 1997. "A Branch-and-Price Algorithm for the Generalized Assignment Problem," Operations Research, INFORMS, vol. 45(6), pages 831-841, December.
    4. Andrew Lim & Fan Wang & Zhou Xu, 2006. "A Transportation Problem with Minimum Quantity Commitment," Transportation Science, INFORMS, vol. 40(1), pages 117-129, February.
    5. Bert de Reyck & Zeger Degraeve, 2003. "Broadcast Scheduling for Mobile Advertising," Operations Research, INFORMS, vol. 51(4), pages 509-517, August.
    6. Tripathi, Arvind K. & Nair, Suresh K., 2007. "Narrowcasting of wireless advertising in malls," European Journal of Operational Research, Elsevier, vol. 182(3), pages 1023-1038, November.
    7. Prinzie, Anita & Van den Poel, Dirk, 2006. "Investigating purchasing-sequence patterns for financial services using Markov, MTD and MTDg models," European Journal of Operational Research, Elsevier, vol. 170(3), pages 710-734, May.
    8. Bose, Indranil & Chen, Xi, 2009. "Quantitative models for direct marketing: A review from systems perspective," European Journal of Operational Research, Elsevier, vol. 195(1), pages 1-16, May.
    9. A. Prinzie & D. Van Den Poel, 2007. "Predicting home-appliance acquisition sequences: Markov/Markov for Discrimination and survival analysis for modeling sequential information in NPTB models," Working Papers of Faculty of Economics and Business Administration, Ghent University, Belgium 07/442, Ghent University, Faculty of Economics and Business Administration.
    10. Peter M. Guadagni & John D. C. Little, 1983. "A Logit Model of Brand Choice Calibrated on Scanner Data," Marketing Science, INFORMS, vol. 2(3), pages 203-238.
    11. 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.
    12. Mankila, Merja, 2004. "Retaining students in retail banking through price bundling: Evidence from the Swedish market," European Journal of Operational Research, Elsevier, vol. 155(2), pages 299-316, June.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. 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.
    2. Konrad, Renata A., 2019. "Designing awareness campaigns to counter human trafficking: An analytic approach," Socio-Economic Planning Sciences, Elsevier, vol. 67(C), pages 86-93.
    3. Seret, Alex & Verbraken, Thomas & Versailles, Sébastien & Baesens, Bart, 2012. "A new SOM-based method for profile generation: Theory and an application in direct marketing," European Journal of Operational Research, Elsevier, vol. 220(1), pages 199-209.
    4. 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.
    5. Brandner, Hubertus & Lessmann, Stefan & Voß, Stefan, 2013. "A memetic approach to construct transductive discrete support vector machines," European Journal of Operational Research, Elsevier, vol. 230(3), pages 581-595.

    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. Fan, Zhi-Ping & Sun, Minghe, 2015. "Behavior-aware user response modeling in social media: Learning from diverse heterogeneous dataAuthor-Name: Chen, Zhen-Yu," European Journal of Operational Research, Elsevier, vol. 241(2), pages 422-434.
    2. Mutsunori Yagiura & Toshihide Ibaraki & Fred Glover, 2004. "An Ejection Chain Approach for the Generalized Assignment Problem," INFORMS Journal on Computing, INFORMS, vol. 16(2), pages 133-151, May.
    3. Malichan Thongkham & Sasitorn Kaewman, 2018. "Methodology to Solve the Combination of the Generalized Assignment Problem and the Vehicle Routing Problem: A Case Study in Drug and Medical Instrument Sales and Service," Administrative Sciences, MDPI, vol. 9(1), pages 1-21, December.
    4. Zäpfel, Günther & Bögl, Michael, 2012. "Two heuristic solution concepts for the vehicle selection problem in line haul transports," European Journal of Operational Research, Elsevier, vol. 217(2), pages 448-458.
    5. D. Thorleuchter & D. Van Den Poel, 2013. "Weak Signal Identification with Semantic Web Mining," Working Papers of Faculty of Economics and Business Administration, Ghent University, Belgium 13/860, Ghent University, Faculty of Economics and Business Administration.
    6. Vera Miguéis & Dirk Poel & Ana Camanho & João Falcão e Cunha, 2012. "Predicting partial customer churn using Markov for discrimination for modeling first purchase sequences," Advances in Data Analysis and Classification, Springer;German Classification Society - Gesellschaft für Klassifikation (GfKl);Japanese Classification Society (JCS);Classification and Data Analysis Group of the Italian Statistical Society (CLADAG);International Federation of Classification Societies (IFCS), vol. 6(4), pages 337-353, December.
    7. V. L. Miguéis & D. Van Den Poel & A.S. Camanho & J. Falcao E Cunha, 2012. "Modeling Partial Customer Churn: On the Value of First Product-Category Purchase Sequences," Working Papers of Faculty of Economics and Business Administration, Ghent University, Belgium 12/790, Ghent University, Faculty of Economics and Business Administration.
    8. Diaz, Juan A. & Fernandez, Elena, 2001. "A Tabu search heuristic for the generalized assignment problem," European Journal of Operational Research, Elsevier, vol. 132(1), pages 22-38, July.
    9. Woodcock, Andrew J. & Wilson, John M., 2010. "A hybrid tabu search/branch & bound approach to solving the generalized assignment problem," European Journal of Operational Research, Elsevier, vol. 207(2), pages 566-578, December.
    10. Robert M. Nauss, 2003. "Solving the Generalized Assignment Problem: An Optimizing and Heuristic Approach," INFORMS Journal on Computing, INFORMS, vol. 15(3), pages 249-266, August.
    11. Chen, Zhen-Yu & Fan, Zhi-Ping & Sun, Minghe, 2012. "A hierarchical multiple kernel support vector machine for customer churn prediction using longitudinal behavioral data," European Journal of Operational Research, Elsevier, vol. 223(2), pages 461-472.
    12. Alberto Ceselli & Giovanni Righini, 2006. "A Branch-and-Price Algorithm for the Multilevel Generalized Assignment Problem," Operations Research, INFORMS, vol. 54(6), pages 1172-1184, December.
    13. Özden Gür Ali & Yalçın Akçay & Serdar Sayman & Emrah Y?lmaz & M. Hamdi Özçelik, 2017. "Cross-Selling Investment Products with a Win-Win Perspective in Portfolio Optimization," Operations Research, INFORMS, vol. 65(1), pages 55-74, February.
    14. Jeet, V. & Kutanoglu, E., 2007. "Lagrangian relaxation guided problem space search heuristics for generalized assignment problems," European Journal of Operational Research, Elsevier, vol. 182(3), pages 1039-1056, November.
    15. Zhang, Jianqiang & He, Xiuli, 2019. "Targeted advertising by asymmetric firms," Omega, Elsevier, vol. 89(C), pages 136-150.
    16. Yagiura, Mutsunori & Ibaraki, Toshihide & Glover, Fred, 2006. "A path relinking approach with ejection chains for the generalized assignment problem," European Journal of Operational Research, Elsevier, vol. 169(2), pages 548-569, March.
    17. Osorio, Maria A. & Laguna, Manuel, 2003. "Logic cuts for multilevel generalized assignment problems," European Journal of Operational Research, Elsevier, vol. 151(1), pages 238-246, November.
    18. Katerina Shapoval & Thomas Setzer, 2018. "Next-Purchase Prediction Using Projections of Discounted Purchasing Sequences," Business & Information Systems Engineering: The International Journal of WIRTSCHAFTSINFORMATIK, Springer;Gesellschaft für Informatik e.V. (GI), vol. 60(2), pages 151-166, April.
    19. Özden Gür Ali & Yalçın Akçay & Serdar Sayman & Emrah Yılmaz & M. Hamdi Özçelik, 2017. "Cross-Selling Investment Products with a Win-Win Perspective in Portfolio Optimization," Operations Research, INFORMS, vol. 65(1), pages 55-74, February.
    20. Fan, Zhi-Ping & Sun, Minghe, 2016. "A multi-kernel support tensor machine for classification with multitype multiway data and an application to cross-selling recommendationsAuthor-Name: Chen, Zhen-Yu," European Journal of Operational Research, Elsevier, vol. 255(1), pages 110-120.

    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:210:y:2011:i:3:p:670-683. 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.