Title: Benders-based winner determination algorithm for volume discount procurement auctions

Authors: S. Kameshwaran, Y. Narahari

Addresses: Centre for Global Logistics and Manufacturing Strategies, Indian School of Business, Hyderabad 500032, India. ' Department of Computer Science and Automation, Indian Institute of Science, Bangalore 560012, India

Abstract: This paper considers an industrial procurement of large volume of a single good, such as a raw material or a subcomponent. The procurement is implemented using volume discount auctions, in which the bids are nonconvex piecewise linear cost functions. The winner determination problem faced by the buyer is an NP-hard nonlinear knapsack problem. We propose a mixed integer linear formulation for the problem which has the following primal structure: if the integer variables are fixed at some feasible values, then solving the remaining linear variables is a continuous knapsack problem. Exploiting this feature, Benders| decomposition algorithm is developed and various techniques are proposed to accelerate the convergence of the algorithm. Experimental results for the random test data show the efficacy of the accelerating techniques.

Keywords: volume discount auctions; nonlinear knapsack problems; piecewise linear cost; mixed integer linear programming; Benders decomposition; dual cuts generation; industrial procurement.

DOI: 10.1504/IJLSM.2009.021643

International Journal of Logistics Systems and Management, 2009 Vol.5 No.1/2, pp.21 - 40

Published online: 30 Nov 2008 *

Full-text access for editors Access for subscribers Purchase this article Comment on this article