Title

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