Gerard J. Burke, Joseph Geunes, H. Edwin Romeijn, Asoo J. Vakharia
Allocating procurement to multiple capacitated suppliers: concave separable minimization over a knapsack constraint
We consider a problem in which a producer must procure a quantity of raw materials from a set
of capacitated suppliers. Each supplier offers a quantity discount price structure, and the producer
seeks to obtain its required materials at minimum cost. The resulting problem takes the form
of a continuous knapsack problem involving the minimization of separable concave functions. We
identify practical special cases of this NP-Hard problem that are polynomially solvable, and provide
a fully-polynomial-time approximation scheme for the general problem.