Using a Lagrangian Heuristic for a Combinatorial Auction Problem
Publication Type
Conference Proceeding Article
Publication Date
2005
Abstract
In this paper, a combinatorial auction problem is modeled as a NP-complete set packing problem and a Lagrangian relaxation based heuristic algorithm is proposed. Extensive experiments are conducted using benchmark CATS test sets and more complex test sets. The algorithm provides optimal solutions for most test sets and is always 1% from the optimal solutions for all CATS test sets. Comparisons with CPLEX 8.0 are also provided, which show that the algorithm provides good solutions.
Discipline
Operations and Supply Chain Management
Research Areas
Operations Management
Publication
ICTAI 2005: 17th IEEE International Conference on Tools with Artificial Intelligence, 14-16 November 2005, Hong Kong
First Page
1082
Last Page
1082
ISBN
9780769524887
Identifier
10.1109/ICTAI.2005.126
Publisher
IEEE
City or Country
Hong Kong
Citation
GUO, Yunsong; LIM, Andrew; and RODRIGUES, Brian.
Using a Lagrangian Heuristic for a Combinatorial Auction Problem. (2005). ICTAI 2005: 17th IEEE International Conference on Tools with Artificial Intelligence, 14-16 November 2005, Hong Kong. 1082-1082.
Available at: https://ink.library.smu.edu.sg/lkcsb_research/592