Résumés
Abstract
Discount auction is a procurement mechanism for buying M indivisible heterogeneous items. The bidders are suppliers and a bid consists of two entities: individual cost for each of the items and a non-decreasing 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 N P-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 collection 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.
Keywords:
- Discount auctions,
- integer programming,
- linear relaxation,
- valid inequalities,
- branch-and-cut,
- transportation problem
Veuillez télécharger l’article en PDF pour le lire.
Télécharger