Bid Evaluation in Procurement Auctions with Piece-Wise Linear Supply Curves

Consider a marketplace operated by a buyer who wishes to procure large quanti-ties
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 also assumed that the submitted supply curves are piece-wise linear
as they often are in practice. This has an added advantage in that any non-linear curve
can be approximated with a family of piece-wise linear functions, and the algorithm
developed in this paper can be applied. The bid evaluation problem faced by the pro-curer
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 sup-pliers
may be awarded. These requirements may result in interdependencies between
the commodities which leads to suboptimal results if the commodities are traded in
independent auctions rather than simultaneously. Even without the additional busi-ness
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.