Using a Lagrangian Heuristic for a Combinatorial Auction Problem

Publication Type

Journal Article

Publication Date

7-2006

Abstract

Combinatorial auctions allow bidders to bid for items leading to more efficient allocations, but determining winners in auctions is $\mathcal{NP}$-complete. In this work, a simple yet effective Lagrangian relaxation based heuristic algorithm is presented. Extensive computational experiments using standard benchmark data (CATS) as well as newly generated more realistic test sets were conducted which showed the heuristic was able to provide optimal solutions for most test cases and is within 1% from the optimums for the rest within very short times. Experiements comparing CPLEX 8.0, the fastest current algorithm, showed the heuristic was able to provide equally godd or better solutions often requring less than 1% of the time required by CPLEX 8.0.

Keywords

Combinatorial auction, Langrange relaxation, heuristic

Discipline

Operations and Supply Chain Management

Research Areas

Operations Management

Publication

International Journal of Artificial Intelligence Tools

Volume

15

Issue

3

First Page

481

Last Page

489

ISSN

0218-2130

Identifier

10.1142/S0218213006002771

Publisher

World Scientific

Additional URL

https://doi.org/10.1142/S0218213006002771

Link to Full Text

Share

COinS