Title :
Using a Lagrangian heuristic for a combinatorial auction problem
Author :
Guo, Y. ; Lim, A. ; Rodrigues, B. ; Tang, J.
Author_Institution :
Sch. of Comput., National Univ. of Singapore, Kent Ridge
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
Keywords :
bin packing; commerce; computational complexity; optimisation; relaxation theory; CATS test sets; Lagrangian heuristic; Lagrangian relaxation; NP-complete set packing problem; combinatorial auction problem; heuristic algorithm; Benchmark testing; Cats; Heuristic algorithms; Iterative algorithms; Lagrangian functions; Large-scale systems; Linear programming; NP-complete problem; Stochastic processes; Technology management;
Conference_Titel :
Tools with Artificial Intelligence, 2005. ICTAI 05. 17th IEEE International Conference on
Conference_Location :
Hong Kong
Print_ISBN :
0-7695-2488-5
DOI :
10.1109/ICTAI.2005.126
