Bid evaluation in procurement auctions with piecewise linear supply curves

Consider a marketplace operated by a buyer who wishes to procure large quantities of several heterogeneous products. Suppliers submit price curves for each of the commodities indicating the price charged as a function of the supplied quantity. The total amount paid to a supplier is the sum of the prices charged for the individual commodities. It is assumed that the submitted supply curves are piecewise linear as they often are in practice. The bid evaluation problem faced by the procurer is to determine how much of each commodity to buy from each of the suppliers so as to minimize the total purchase price. In addition to meeting the demand, the buyer may impose additional business requirements that restrict which contracts suppliers may be awarded. These requirements may result in interdependencies between the commodities which lead to suboptimal results if the commodities are traded in independent auctions rather than simultaneously. Even without the additional business constraints the bid evaluation problem is NP-hard. The main contribution of our study is a flexible column generation based heuristics that provides near-optimal solutions to the procurer's bid evaluation problem. Our method scales very well due to the Branch-and-Price technology it is built on. We employ sophisticated rounding and local improvement heuristics to obtain quality solutions. We also developed a test data generator that produces realistic problems and allows control over the difficulty level of the problems using parameters.