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

An exact algorithm for the Capacitated Total Quantity Discount Problem

Author

Listed:
  • Manerba, Daniele
  • Mansini, Renata

Abstract

In this paper we analyze the procurement problem of a company that needs to purchase a number of products from a set of suppliers to satisfy demand. The suppliers offer total quantity discounts and the company aims at selecting a set of suppliers so to satisfy product demand at minimum purchasing cost. The problem, known as Total Quantity Discount Problem (TQDP), is strongly NP-hard. We study different families of valid inequalities and provide a branch-and-cut approach to solve the capacitated variant of the problem (Capacitated TQDP) where the quantity available for a product from a supplier is limited. A hybrid algorithm, called HELP (Heuristic Enhancement from LP), is used to provide an initial feasible solution to the exact approach. HELP exploits information provided by the continuous relaxation problem to construct neighborhoods optimally searched through the solution of mixed integer subproblems. A streamlined version of the proposed exact method can optimally solve in a reasonable amount of time instances with up to 100 suppliers and 500 products, and largely outperforms an existing approach available in the literature and CPLEX 12.2 that frequently runs out of memory before completing the search.

Suggested Citation

  • Manerba, Daniele & Mansini, Renata, 2012. "An exact algorithm for the Capacitated Total Quantity Discount Problem," European Journal of Operational Research, Elsevier, vol. 222(2), pages 287-300.
    • Handle: RePEc:eee:ejores:v:222:y:2012:i:2:p:287-300
    DOI: 10.1016/j.ejor.2012.04.028
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0377221712003360
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.ejor.2012.04.028?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. Weber, Charles A. & Current, John R. & Benton, W. C., 1991. "Vendor selection criteria and methods," European Journal of Operational Research, Elsevier, vol. 50(1), pages 2-18, January.
    2. Kameshwaran, S. & Narahari, Y. & Rosa, Charles H. & Kulkarni, Devadatta M. & Tew, Jeffrey D., 2007. "Multiattribute electronic procurement using goal programming," European Journal of Operational Research, Elsevier, vol. 179(2), pages 518-536, June.
    3. Munson, C.L. & Hu, J., 2010. "Incorporating quantity discounts and their inventory impacts into the centralized purchasing decision," European Journal of Operational Research, Elsevier, vol. 201(2), pages 581-592, March.
    4. Zhang, Ju-liang & Zhang, Ming-yu, 2011. "Supplier selection and purchase problem with fixed cost and constrained order quantities under stochastic demand," International Journal of Production Economics, Elsevier, vol. 129(1), pages 1-7, January.
    5. Burke, Gerard J. & Carrillo, Janice E. & Vakharia, Asoo J., 2007. "Single versus multiple supplier sourcing strategies," European Journal of Operational Research, Elsevier, vol. 182(1), pages 95-112, October.
    6. Gilbert Laporte & Jorge Riera-Ledesma & Juan-José Salazar-González, 2003. "A Branch-and-Cut Algorithm for the Undirected Traveling Purchaser Problem," Operations Research, INFORMS, vol. 51(6), pages 940-951, December.
    7. Joris van de Klundert & Jeroen Kuipers & Frits C. R. Spieksma & Maarten Winkels, 2005. "Selecting Telecommunication Carriers to Obtain Volume Discounts," Interfaces, INFORMS, vol. 35(2), pages 124-132, April.
    8. Crama, Y. & Pascual J., R. & Torres, A., 2004. "Optimal procurement decisions in the presence of total quantity discounts and alternative product recipes," European Journal of Operational Research, Elsevier, vol. 159(2), pages 364-378, December.
    9. Parlar, Mahmut & Wang, Dan, 1993. "Diversification under yield randomness in inventory models," European Journal of Operational Research, Elsevier, vol. 66(1), pages 52-64, April.
    10. Seifert, Ralf W. & Thonemann, Ulrich W. & Hausman, Warren H., 2004. "Optimal procurement strategies for online spot markets," European Journal of Operational Research, Elsevier, vol. 152(3), pages 781-799, February.
    11. Mansini, Renata & Savelsbergh, Martin W.P. & Tocchella, Barbara, 2012. "The supplier selection problem with quantity discounts and truckload shipping," Omega, Elsevier, vol. 40(4), pages 445-455.
    12. Ravi Anupindi & Ram Akella, 1993. "Diversification Under Supply Uncertainty," Management Science, INFORMS, vol. 39(8), pages 944-963, August.
    13. Degraeve, Zeger & Labro, Eva & Roodhooft, Filip, 2000. "An evaluation of vendor selection models from a total cost of ownership perspective," European Journal of Operational Research, Elsevier, vol. 125(1), pages 34-58, August.
    14. Chauhan, Satyaveer Singh & Proth, Jean-Marie, 2003. "The concave cost supply problem," European Journal of Operational Research, Elsevier, vol. 148(2), pages 374-383, July.
    15. Maqbool Dada & Nicholas C. Petruzzi & Leroy B. Schwarz, 2007. "A Newsvendor's Procurement Problem when Suppliers Are Unreliable," Manufacturing & Service Operations Management, INFORMS, vol. 9(1), pages 9-32, August.
    16. Awasthi, A. & Chauhan, S.S. & Goyal, S.K. & Proth, Jean-Marie, 2009. "Supplier selection problem for a single manufacturing unit under stochastic demand," International Journal of Production Economics, Elsevier, vol. 117(1), pages 229-233, January.
    17. Roodhooft, Filip & Konings, Jozef, 1997. "Vendor selection and evaluation an Activity Based Costing approach," European Journal of Operational Research, Elsevier, vol. 96(1), pages 97-102, January.
    18. Meir J. Rosenblatt & Yale T. Herer & Ilan Hefter, 1998. "Note. An Acquisition Policy for a Single Item Multi-Supplier System," Management Science, INFORMS, vol. 44(11-Part-2), pages 96-100, November.
    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. Jackson, Jonathan E. & Munson, Charles L., 2016. "Shared resource capacity expansion decisions for multiple products with quantity discounts," European Journal of Operational Research, Elsevier, vol. 253(3), pages 602-613.
    2. Yang, Liu & Millstein, Mitch A. & Campbell, James F., 2022. "Unlocking cost savings hidden in hospital tier contracts," Omega, Elsevier, vol. 113(C).
    3. Li, Zhaolin & Ou, Jinwen & Liang, Guitian, 2021. "Optimizing hospital drug procurement with rebate contracts," Omega, Elsevier, vol. 105(C).
    4. Kirschstein, Thomas & Meisel, Frank, 2019. "A multi-period multi-commodity lot-sizing problem with supplier selection, storage selection and discounts for the process industry," European Journal of Operational Research, Elsevier, vol. 279(2), pages 393-406.
    5. Nguyen, H.N. & Rainwater, C.E. & Mason, S.J. & Pohl, E.A., 2014. "Quantity discount with freight consolidation," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 66(C), pages 66-82.
    6. Manerba, Daniele & Mansini, Renata & Perboli, Guido, 2018. "The Capacitated Supplier Selection problem with Total Quantity Discount policy and Activation Costs under uncertainty," International Journal of Production Economics, Elsevier, vol. 198(C), pages 119-132.
    7. Manerba, Daniele & Mansini, Renata & Riera-Ledesma, Jorge, 2017. "The Traveling Purchaser Problem and its variants," European Journal of Operational Research, Elsevier, vol. 259(1), pages 1-18.
    8. Li, Xin & Ventura, José A. & Venegas, Bárbara B. & Kweon, Sang Jin & Hwang, Seong Wook, 2018. "An integrated acquisition policy for supplier selection and lot sizing considering total quantity discounts and a quality constraint," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 119(C), pages 19-40.
    9. Chung, Wenming & Talluri, Srinivas & Narasimhan, Ram, 2015. "Optimal pricing and inventory strategies with multiple price markdowns over time," European Journal of Operational Research, Elsevier, vol. 243(1), pages 130-141.
    10. Maheswar Singh Mahapatra & Pravash Chandra Pradhan & J. K. Jha, 2022. "Sourcing decisions with order allocation under supply disruption risk considering quantitative and qualitative criteria," Operational Research, Springer, vol. 22(4), pages 3291-3333, September.
    11. Bianchessi, N. & Mansini, R. & Speranza, M.G., 2014. "The distance constrained multiple vehicle traveling purchaser problem," European Journal of Operational Research, Elsevier, vol. 235(1), pages 73-87.
    12. Aria Shahsavar & Nima Zoraghi & Babak Abbasi, 2018. "Integration of resource investment problem with quantity discount problem in material ordering for minimizing resource costs of projects," Operational Research, Springer, vol. 18(2), pages 315-342, July.
    13. Mohammad Khosroabadi & Jafar Gheidar-Kheljani & Mohammad Hosein Karimi Gavareshki, 2024. "Utilizing Multi-vehicle Traveling Purchaser Problem for Multiple-Supplier Selection and Multi-period Lot-Sizing in a Fuzzy Demand Environment," SN Operations Research Forum, Springer, vol. 5(4), pages 1-28, December.
    14. Riccardo Giusti & Chiara Iorfida & Yuanyuan Li & Daniele Manerba & Stefano Musso & Guido Perboli & Roberto Tadei & Shuai Yuan, 2019. "Sustainable and De-Stressed International Supply-Chains Through the SYNCHRO-NET Approach," Sustainability, MDPI, vol. 11(4), pages 1-26, February.
    15. Song, Zhuzhu & Tang, Wansheng & Zhao, Ruiqing, 2019. "Encroachment and canvassing strategy in a sea-cargo service chain with empty container repositioning," European Journal of Operational Research, Elsevier, vol. 276(1), pages 175-186.

    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. Mansini, Renata & Savelsbergh, Martin W.P. & Tocchella, Barbara, 2012. "The supplier selection problem with quantity discounts and truckload shipping," Omega, Elsevier, vol. 40(4), pages 445-455.
    2. Xu, Jianjun & Keblis, Matthew F. & Feng, Youyi & Chang, Yanling, 2017. "Optimal sourcing from a pool of suppliers with nonidentical salvage values," International Journal of Production Economics, Elsevier, vol. 193(C), pages 392-405.
    3. Manerba, Daniele & Mansini, Renata & Perboli, Guido, 2018. "The Capacitated Supplier Selection problem with Total Quantity Discount policy and Activation Costs under uncertainty," International Journal of Production Economics, Elsevier, vol. 198(C), pages 119-132.
    4. Zhang, Ju-liang & Zhang, Ming-yu, 2011. "Supplier selection and purchase problem with fixed cost and constrained order quantities under stochastic demand," International Journal of Production Economics, Elsevier, vol. 129(1), pages 1-7, January.
    5. Bianchessi, N. & Mansini, R. & Speranza, M.G., 2014. "The distance constrained multiple vehicle traveling purchaser problem," European Journal of Operational Research, Elsevier, vol. 235(1), pages 73-87.
    6. Ali Ekici & Baṣak Altan & Okan Örsan Özener, 2016. "Pricing decisions in a strategic single retailer/dual suppliers setting under order size constraints," International Journal of Production Research, Taylor & Francis Journals, vol. 54(7), pages 1887-1898, April.
    7. Pritee Ray & Mamata Jenamani, 2016. "Sourcing decision under disruption risk with supply and demand uncertainty: A newsvendor approach," Annals of Operations Research, Springer, vol. 237(1), pages 237-262, February.
    8. Pritee Ray & Mamata Jenamani, 2016. "Sourcing decision under disruption risk with supply and demand uncertainty: A newsvendor approach," Annals of Operations Research, Springer, vol. 237(1), pages 237-262, February.
    9. Omid Jadidi & Fatemeh Firouzi & John S. Loucks & Yong Shin Park, 2022. "Multi-criteria supplier selection problem with fuzzy demand: a newsvendor model," Computational Management Science, Springer, vol. 19(3), pages 375-394, July.
    10. Faiza Hamdi & Ahmed Ghorbel & Faouzi Masmoudi & Lionel Dupont, 2018. "Optimization of a supply portfolio in the context of supply chain risk management: literature review," Journal of Intelligent Manufacturing, Springer, vol. 29(4), pages 763-788, April.
    11. Svoboda, Josef & Minner, Stefan & Yao, Man, 2021. "Typology and literature review on multiple supplier inventory control models," European Journal of Operational Research, Elsevier, vol. 293(1), pages 1-23.
    12. Schöll, Michaela, 2017. "Three Essays on Sustainable Supply Chain Management – Towards Sustainable Supplier Selection and Sustainable Sourcing," EconStor Theses, ZBW - Leibniz Information Centre for Economics, number 172463, September.
    13. Ekici, Ali, 2013. "An improved model for supplier selection under capacity constraint and multiple criteria," International Journal of Production Economics, Elsevier, vol. 141(2), pages 574-581.
    14. Mohammadivojdan, Roshanak & Merzifonluoglu, Yasemin & Geunes, Joseph, 2022. "Procurement portfolio planning for a newsvendor with supplier delivery uncertainty," European Journal of Operational Research, Elsevier, vol. 297(3), pages 917-929.
    15. Preetam Basu & Soumita Ghosh & Milan Kumar, 2019. "Supplier ratings and dynamic sourcing strategies to mitigate supply disruption risks," DECISION: Official Journal of the Indian Institute of Management Calcutta, Springer;Indian Institute of Management Calcutta, vol. 46(1), pages 41-57, March.
    16. Guo, Cong & Li, Xueping, 2014. "A multi-echelon inventory system with supplier selection and order allocation under stochastic demand," International Journal of Production Economics, Elsevier, vol. 151(C), pages 37-47.
    17. Yang, Liu & Millstein, Mitch A. & Campbell, James F., 2022. "Unlocking cost savings hidden in hospital tier contracts," Omega, Elsevier, vol. 113(C).
    18. Bin Zhang & Zekai Lai & Qiangqiang Wang, 2021. "Multi-product dual sourcing problem with limited capacities," Operational Research, Springer, vol. 21(3), pages 2055-2075, September.
    19. Eng, Shao Wei Lester & Chew, Ek Peng & Lee, Loo Hay, 2014. "Impacts of supplier knowledge sharing competences and production capacities on radical innovative product sourcing," European Journal of Operational Research, Elsevier, vol. 232(1), pages 41-51.
    20. Tan, Tarkan & Alp, Osman, 2016. "Optimal sourcing from alternative capacitated suppliers with general cost structures," Omega, Elsevier, vol. 58(C), pages 26-32.

    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:222:y:2012:i:2:p:287-300. 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.