Using a Lagrangian Heuristic for a Combinatorial Auction Problem

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

Full description

Saved in:

Bibliographic Details
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
Tags:	Add Tag No Tags, Be the first to tag this record!
Institution:	Singapore Management University
Language:	English

id	sg-smu-ink.lkcsb_research-1591
record_format	dspace
spelling	sg-smu-ink.lkcsb_research-15912010-09-23T06:24:04Z Using a Lagrangian Heuristic for a Combinatorial Auction Problem GUO, Yunsong LIM, Andrew RODRIGUES, Brian 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. 2005-11-14T08:00:00Z text https://ink.library.smu.edu.sg/lkcsb_research/592 info:doi/10.1109/ICTAI.2005.126 https://doi.org/10.1109/ICTAI.2005.126 Research Collection Lee Kong Chian School Of Business eng Institutional Knowledge at Singapore Management University Operations and Supply Chain Management
institution	Singapore Management University
building	SMU Libraries
continent	Asia
country	Singapore Singapore
content_provider	SMU Libraries
collection	InK@SMU
language	English
topic	Operations and Supply Chain Management
spellingShingle	Operations and Supply Chain Management GUO, Yunsong LIM, Andrew RODRIGUES, Brian Using a Lagrangian Heuristic for a Combinatorial Auction Problem
description	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.
format	text
author	GUO, Yunsong LIM, Andrew RODRIGUES, Brian
author_facet	GUO, Yunsong LIM, Andrew RODRIGUES, Brian
author_sort	GUO, Yunsong
title	Using a Lagrangian Heuristic for a Combinatorial Auction Problem
title_short	Using a Lagrangian Heuristic for a Combinatorial Auction Problem
title_full	Using a Lagrangian Heuristic for a Combinatorial Auction Problem
title_fullStr	Using a Lagrangian Heuristic for a Combinatorial Auction Problem
title_full_unstemmed	Using a Lagrangian Heuristic for a Combinatorial Auction Problem
title_sort	using a lagrangian heuristic for a combinatorial auction problem
publisher	Institutional Knowledge at Singapore Management University
publishDate	2005
url	https://ink.library.smu.edu.sg/lkcsb_research/592 https://doi.org/10.1109/ICTAI.2005.126
_version_	1770569621174222848

Using a Lagrangian Heuristic for a Combinatorial Auction Problem

Similar Items