Combinatorial Reverse Auction Based on Lagrangian Relaxation

In procurement, a buyer who wants to obtain some goods at the lowest possible cost can hold a reverse auction to try to obtain the goods from a set of sellers who can provide the goods. If there is complementarity or substitutability between the goods, a combinatorial reverse auction can be beneficial. Each seller places bids for each bundle of goods he can provide. The problem is to determine the winners. In this paper, we consider a winner determination problem in which a buyer wants to acquire items from a set of sellers to process the task on hand. The task requires a minimal set of items for executing the operations. Each seller owns a set of items to bid for the task. The problem is to determine the winners to minimize the total cost to acquire the required items. The main results include: (1) a problem formulation for the combinatorial reverse auction problem; (2) a solution methodology based on Lagrangian relaxation; (3) an economic interpretation and (4) specification of the requirements for the implementation of our solution algorithms.