Branch-and-Cut Algorithms for Winner Determination in Discount Auctions

Authors

  • Sampath Kameshwaran Indian School of Business
  • Lyes Benyoucef INRIA
  • Xiaolan Xie ENSM de Saint-Etienne

Keywords:

Discount auctions, integer programming, linear relaxation, valid inequalities, branch-and-cut, transportation problem

Abstract

Discount auction is a procurement mechanism for buying M indivisible heterogeneous items. The bidders are suppliers and a bid consists of individual cost for each of the items and a nondecreasing discount function defined over the number of items. The winner determination problem faced by the buyer is to determine the winning suppliers and their corresponding winning items that minimizes the total procurement cost, subject to the supply, demand, and discount constraints. We show that this problem is NP-hard upon reduction from the set covering problem. An integer programming formulation is presented and valid inequalities are derived, which serve as cuts to the linear relaxation. A suite of branch-and-cut algorithms are developed with different cut addition techniques and branching strategies. The performance of the proposed algorithms for different problem types are studied with extensive computational experiments.

Downloads

Published

2007-09-02

How to Cite

Kameshwaran, S., Benyoucef, L., & Xie, X. (2007). Branch-and-Cut Algorithms for Winner Determination in Discount Auctions. Algorithmic Operations Research, 2(2), 112. Retrieved from https://journals.lib.unb.ca/index.php/AOR/article/view/2792

Issue

Vol. 2 No. 2 (2007)

Section

Articles

License

The copyright of the submitted article is hereby transferred to “Preeminent Academic Facets Inc. (the “publisher”) to the extent possible by the laws in the respective countries of the author(s). The author(s) retain all other rights including the following: 1. Any patents and trademark rights. 2. Right to post a pre-print version of the paper on the author’s personal website which is not used for commercial purposes. The author(s) warrant that the work is original, it has not been published elsewhere, it is not currently under consideration for publication in any form, and it does not infringe any copyright laws. The signing author or agent further warrants that all authors, if applicable, have been informed of the terms of this agreement and obtained the approval and authority to sign the agreement.