More Web Proxy on the site http://driver.im/

tutorial

Stochastic Hyper-Heuristic for the Winner Determination Problem in combinatorial auctions

Authors:

Dalila Boughaci,

Mourad LassouaouiAuthors Info & Claims

MEDES '14: Proceedings of the 6th International Conference on Management of Emergent Digital EcoSystems

Pages 62 - 66

https://doi.org/10.1145/2668260.2668268

Published: 15 September 2014 Publication History

Abstract

In this paper, we propose a stochastic hyper-heuristic (SHH) for combining heuristics for solving the winner determination problem (WDP) in combinatorial auctions. The hyper-heuristics vary for the choice of the underlying heuristics. The choice function hyper-heuristic uses a selection function while the random hyper-heuristic selects randomly the underlying heuristics. In this paper, we propose a new idea for hyper-heuristics by combining choice function and randomness strategies. The two strategies in the proposed approach are controlled by using a walk probability as done in stochastic local search. The proposed method is evaluated on various benchmark problems. The numerical results show that the SHH performs better in almost all cases and the comparison is done with the choice function hyper-heuristic, the random hyper-heuristic and the well-known Stochastic Local Search (SLS).

References

[1]

Anderson, A., Tenhunen, M. and Ygge, F. (2000), 'Integer programming for combinatorial auction winner determination', Proceedings of 4th International Conference on Multi-Agent Systems, IEEE Computer Society Press, July, pp: 39--46.

Digital Library

[2]

Bean. J.C, (1994). 'Genetics and random keys for sequencing and optimization', ORSA Journal of Computing, vol 6, nÂř2, pp: 154--160.

[3]

Boughaci. D, Benhamou. B and Drias. H. (2009), 'A Memetic Algorithm for the Optimal Winner Determination Problem, In Soft Computing, vol 13, numbers 8-9, pp: 905-- 917.

Digital Library

[4]

Boughaci. D. (2010), 'A Differential Evolution Algorithm for the Winner Determination Problem in Combinatorial Auctions'. in Electronic Notes in Discrete Mathematics, vol 36, pp: 535--542.

[5]

Boughaci. D, Belaid Benhamou, Habiba Drias. (2010) 'Local Search Methods for the Optimal Winner Determination Problem in Combinatorial Auctions. Journal of Mathematical. Modelling and Algorithms, 9(2): 165--180.

[6]

Edmund K. Burke, Matthew Hyde, Graham Kendall, Gabriela Ochoa, Ender Ozcan, and John R. Woodward.(2010), 'A classification of hyper-heuristic Approaches', in International Series in Operations Research and Management Science.

[7]

Edmund K. Burke, Mathew R. Hyde, Graham Kendall, Gabriela Ochoa, Ender Ozcan, and John R. Woodward. (2009), 'Exploring Hyper-heuristic Methodologies with Genetic Programming', in Collaborative Computational Intelligence.

[8]

Edmund K. Burke, Mathew R. Hyde, Graham Kendall, Gabriela Ochoa, Ender Ozcan, and Rong. Qu. (2010), 'Hyper-heuristics: A Survey of the State of the Art'. Technical Report, School of Computer Science and Information Technology, University of Nottingham.

[9]

Fujishima Y, Leyton-Brown K, Shoham Y. (1999) 'Taming the computational complexity of combinatorial auctions: optimal and approximate approaches', Sixteenth international joint conference on artificial intelligence, pp: 48--53.

Digital Library

[10]

Guo Y, Lim A, Rodrigues B, Zhu Y, (2006). 'Heuristics for a bidding problem'. In Computers and Operations Research, vol 33, Issue 8, August 2006, pp: 2179--2188.

Digital Library

[11]

Hoos HH, Boutilier C. (2000), 'Solving combinatorial auctions using stochastic local search', In Proceedings of the 17th national conference on artificial intelligence, pp: 22--29.

Digital Library

[12]

Hoos HH (2002) An Adaptive Noise Mechanism for WalkSAT. In: Proceedings of the 19 th national conference on artificial intelligence AAAI/IAAI 2002, pp 655--660.

Digital Library

[13]

Lassouaoui. M, Boughaci. D (2013), 'A Choice Function Hyper-heuristic for the Winner Determination Problem'. NICSO 2013 pp: 303--314.

[14]

Lau HC, Goh, YG (2002). 'An intelligent brokering system to support multi-agent web-based 4th-party logistics', In Proceedings of the 14th international conference on tools with artificial intelligence, pp: 54--61.

Digital Library

[15]

Leyton-Brown K, Tennenholtz M, Shoham Y (2000). 'An Algorithm for Multi-Unit Combinatorial Auctions', In Proceedings of the 17th national conference on artificial intelligence, Austin, Games-2000, Bilbao, and ISMP-2000, Atlanta.

Digital Library

[16]

Nisan, N. (2000), 'Bidding and allocation in combinatorial auctions', In Proceedings of ACM Conference on Electronic Commerce (EC'00), Minneapolis: ACM SIGecom, ACM Press, October, pp: 1--12.

Digital Library

[17]

Rothkopf, M.H., Pekee, A. and Ronald, M. (1998) 'Computationally manageable combinatorial auctions', In Management Science, vol. 44, No. 8, pp: 1131--1147.

Digital Library

[18]

Sandholm, T(1999). 'Algorithms for Optimal Winner Determination in Combinatorial Auctions', In Artificial Intelligence, vol 135, (1-2), pp: 1--54.

Digital Library

[19]

Sandholm T, Suri S, Gilpin A, Levine D. (2001), 'CABoB: a fast optimal algorithm for combinatorial auctions'. In Proceedings of the International joint conferences on artificial intelligence, pp: 1102--1108.

Digital Library

[20]

Sandholm T, Suri S, (2000). 'Improved Optimal Algorithm for Combinatorial Auctions and Generalizations'. In Proceedings of the 17th national conference on artificial intelligence, pp: 90--97.

Digital Library

Cited By

Lassouaoui MBoughaci DBenhamou B(2019)A multilevel synergy Thompson sampling hyper-heuristic for solving Max-SATIntelligent Decision Technologies10.3233/IDT-180036(1-18)Online publication date: 4-Apr-2019
https://doi.org/10.3233/IDT-180036
Epitropakis MBurke E(2018)Hyper-heuristicsHandbook of Heuristics10.1007/978-3-319-07153-4_32-1(1-57)Online publication date: 10-Feb-2018
https://doi.org/10.1007/978-3-319-07153-4_32-1
Epitropakis MBurke E(2018)Hyper-heuristicsHandbook of Heuristics10.1007/978-3-319-07124-4_32(489-545)Online publication date: 14-Aug-2018
https://doi.org/10.1007/978-3-319-07124-4_32

Index Terms

Stochastic Hyper-Heuristic for the Winner Determination Problem in combinatorial auctions
1. Computing methodologies
  1. Artificial intelligence
    1. Search methodologies
      1. Heuristic function construction

Recommendations

A Multi-Agent based Hyper-Heuristic Algorithm for the Winner Determination Problem

In this paper, we propose a Multi-Agent based Hyper-Heuristic algorithm for the Winner Determination Problem named MAH2-WDP. This algorithm explores a set of cooperating agents to select the appropriate operation using learning techniques. MAH2-WDP is ...
Winner Determination Algorithms for Combinatorial Auctions with Sub-cardinality Constraints

We examine the winner determination problem for combinatorial auctions with sub-cardinality constraints (WDP-SC). In this type of auction, bidders submit bids for packages of items of interest together with a specific number of items they want. All ...
Solving the winner determination problem via a weighted maximum clique heuristic

The winner determination problem (WDP) is a key issue in combinatorial auctions with many applications.We recast the WDP to a clique problem (MWCP) and solve it with a recent clique heuristic.The approach is assessed on three test suites of 530 ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Other conferences

MEDES '14: Proceedings of the 6th International Conference on Management of Emergent Digital EcoSystems

September 2014

225 pages

ISBN:9781450327671

DOI:10.1145/2668260

Conference Chairs:
Obaid Al Motairy
Qassim University, KSA
,
Richard Chbeir
University of Pau and Adour Countries, France
,
Mohammed Alodib
Qassim University, KSA
,
Lamri Laouamer
Qassim University, KSA
,
Youakim Badr
INSA De Lyon, France
,
Program Chairs:
Morad Benyoucef
University of Ottawa, Canada
,
Saad Harous
United Arab Emirates University
,
Ismail Biskri

Copyright © 2014 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

In-Cooperation

SIGAPP: ACM Special Interest Group on Applied Computing

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 15 September 2014

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Tutorial
Research
Refereed limited

Conference

MEDES '14

MEDES '14: The 6th International Conference on Management of Emergent Digital EcoSystems

September 15 - 17, 2014

Al Qassim, Buraidah, Saudi Arabia

Acceptance Rates

Overall Acceptance Rate 267 of 682 submissions, 39%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

3
Total Citations
View Citations
67
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 25 Feb 2025

Other Metrics

View Author Metrics

Citations

Cited By

Lassouaoui MBoughaci DBenhamou B(2019)A multilevel synergy Thompson sampling hyper-heuristic for solving Max-SATIntelligent Decision Technologies10.3233/IDT-180036(1-18)Online publication date: 4-Apr-2019
https://doi.org/10.3233/IDT-180036
Epitropakis MBurke E(2018)Hyper-heuristicsHandbook of Heuristics10.1007/978-3-319-07153-4_32-1(1-57)Online publication date: 10-Feb-2018
https://doi.org/10.1007/978-3-319-07153-4_32-1
Epitropakis MBurke E(2018)Hyper-heuristicsHandbook of Heuristics10.1007/978-3-319-07124-4_32(489-545)Online publication date: 14-Aug-2018
https://doi.org/10.1007/978-3-319-07124-4_32

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Table of Conten