Using a Lagrangian Heuristic for a Combinatorial Auction Problem

• Main Authors: GUO, Yunsong, LIM, Andrew, RODRIGUES, Brian
• Format: text
• Language: English
• Published: Institutional Knowledge at Singapore Management University 2005
• Subjects: Operations and Supply Chain Management
• Online Access: https://ink.library.smu.edu.sg/lkcsb_research/592; https://doi.org/10.1109/ICTAI.2005.126
• Institution: Singapore Management University

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...