Article ID: | iaor20084218 |
Country: | Netherlands |
Volume: | 178 |
Issue: | 2 |
Start Page Number: | 603 |
End Page Number: | 625 |
Publication Date: | Apr 2007 |
Journal: | European Journal of Operational Research |
Authors: | Spieksma Frits C.R., Klundert Joris van de, Goossens D.R., Maas A.J.T. |
Keywords: | programming: branch and bound |
In this paper, we study the procurement problem faced by a buyer who needs to purchase a variety of goods from suppliers applying a so-called total quantity discount policy. This policy implies that every supplier announces a number of volume intervals and that the volume interval in which the total amount ordered lies determines the discount. Moreover, the discounted prices apply to all goods bought from the supplier, not only to those goods exceeding the volume threshold. We refer to this cost-minimization problem as the total quantity discount (TQD) problem. We give a mathematical formulation for this problem and argue that not only it is NP-hard, but also that there exists no polynomial-time approximation algorithm with a constant ratio (unless