Article

Learning the Empirical Hardness of Optimization Problems: The Case of Combinatorial Auctions

Authors:

Kevin Leyton-Brown,

Eugene Nudelman,

Yoav ShohamAuthors Info & Claims

CP '02: Proceedings of the 8th International Conference on Principles and Practice of Constraint Programming

Pages 556 - 572

Published: 09 September 2002 Publication History

Abstract

We propose a new approach for understanding the algorithm-specific empiricalh ardness of NP-Hard problems. In this work we focus on the empirical hardness of the winner determination problem--an optimization problem arising in combinatorial auctions--when solved by ILOG's CPLEX software. We consider nine widely-used problem distributions and sample randomly from a continuum of parameter settings for each distribution. We identify a large number of distribution-nonspecific features of data instances and use statisticalregression techniques to learn, evaluate and interpret a function from these features to the predicted hardness of an instance.

References

[1]

D. Achlioptas, C. Gomes, H. Kautz, and B. Selman. Generating satisfiable instances. In AAAI-00 , 2000.

[2]

A. Anderson, M. Tenhunen, and F. Ygge. Integer programming for combinatorial auction winner determination. In ICMAS , 2000.

[3]

P. Cheeseman, B. Kanefsky, and W. M. Taylor. Where the Really Hard Problems Are. In IJCAI-91 , 1991.

[4]

S. de Vries and R. Vohra. Combinatoriala uctions: A brief survey. Unpublished, 2000.

[5]

J. Friedman. Multivariate adaptive regression splines. Annals of Statistics , 19, 1991.

[6]

Y. Fujishima, K. Leyton-Brown, and Y. Shoham. Taming the computational complexity of combinatorial auctions: Optimal and approximate approaches. In IJCAI-99 , 1999.

[7]

Carla P. Gomes and Bart Selman. Problem structure in the presence of perturbations. In AAAI/IAAI , 1997.

[8]

R. Gonen and D. Lehmann. Optimal solutions for multi-unit combinatorial auctions: Branch and bound heuristics. In ACM Conference on Electronic Commerce , 2000.

[9]

T. Hastie, R. Tibshirani, and J. Friedman. Elements of Statistical Learning . Springer, 2001.

[10]

R. C. Holte. Combinatorial auctions, knapsack problems, and hill-climbing search. In Canadian Conference on AI , 2001.

[11]

H.H. Hoos and C. Boutilier. Solving combinatorial auctions using stochastic local search. In AAAI-00 , 2000.

[12]

E. Horvitz, Y. Ruan, C. Gomes, H. Kautz, B. Selman, and M. Chickering. A bayesian approach to tackling hard computational problems, 2001.

[13]

R. Kastner, C. Hsieh, M. Potkonjak, and M. Sarrafzadeh. On the sensitivity of incrementalal gorithms for combinatorial auctions, 2002. UCLA CS Tech. Report 020000.

[14]

R. Korf and M. Reid. Complexity analysis of admissible heuristic search. AAAI- 98 , 1998.

[15]

K. Leyton-Brown, M. Pearson, and Y. Shoham. Towards a universalt est suite for combinatorialau ction algorithms. In ACM Conference on Electronic Commerce , 2000.

[16]

K. Leyton-Brown, Yoav Shoham, and Moshe Tennenholtz. An algorithm for multiunit combinatoriala uctions. In Proceedings of AAAI-00 , 2000.

[17]

R. Monasson, R. Zecchina, S. Kirkpatrick, B. Selman, and L. Troyansky. Determining computationalc omplexity for characteristic 'phase transitions'. Nature , 400, 1998.

[18]

N. Nisan. Bidding and allocation in combinatorial auctions. In ACM Conference on Electronic Commerce , 2000.

[19]

D. C. Parkes. iBundle: An efficient ascending price bundle auction. In ACM Conference on Electronic Commerce , 1999.

[20]

M.H. Rothkopf, A. Pekec, and R. M. Harstad. Computationally manageable combinatoriala uctions. Management Science , 44(8), 1998.

[21]

T. Sandholm. An algorithm for optimal winner determination in combinatorial auctions. In IJCAI-99 , 1999.

[22]

T. Sandholm, S. Suri, A. Gilpin, and D. Levine. Cabob: A fast optimal algorithm for combinatorialau ctions. In IJCAI-01 , 2001.

[23]

Dale Schuurmans, Finnegan Southey, and Robert C. Holte. The exponentiated subgradient algorithm for heuristic boolean programming. In IJCAI-01 , 2001.

[24]

J. Slaney and T. Walsh. Backbones in optimization and approximation. In IJCAI- 01 , 2001.

[25]

W. Zhang. State-Space Search: Algorithms, Complexity, Extensions, and Applications . Springer, 1999.

Cited By

Zhang MArcuri A(2021)Adaptive Hypermutation for Search-Based System Test Generation: A Study on REST APIs with EvoMasterACM Transactions on Software Engineering and Methodology10.1145/346494031:1(1-52)Online publication date: 28-Sep-2021
https://dl.acm.org/doi/10.1145/3464940
Doerr CDreo JKerschke PAuger AStützle T(2019)Making a case for (Hyper-)parameter tuning as benchmark problemsProceedings of the Genetic and Evolutionary Computation Conference Companion10.1145/3319619.3326857(1755-1764)Online publication date: 13-Jul-2019
https://dl.acm.org/doi/10.1145/3319619.3326857
Belkhir NDréo JSavéant PSchoenauer MBosman P(2017)Per instance algorithm configuration of CMA-ES with limited budgetProceedings of the Genetic and Evolutionary Computation Conference10.1145/3071178.3071343(681-688)Online publication date: 1-Jul-2017
https://dl.acm.org/doi/10.1145/3071178.3071343
Show More Cited By

Recommendations

A discrete gravitational search algorithm for solving combinatorial optimization problems

Metaheuristics are general search strategies that, at the exploitation stage, intensively exploit areas of the solution space with high quality solutions and, at the exploration stage, move to unexplored areas of the solution space when necessary. The ...
Hardness of learning DNFs using halfspaces
STOC 2021: Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing

The problem of learning t-term DNF formulas (for t = O(1)) has been studied extensively in the PAC model since its introduction by Valiant (STOC 1984). A t-term DNF can be efficiently learnt using a t-term DNF only if t = 1 i.e., when it is an AND, ...
An empirical study of reserve price optimisation in real-time bidding
KDD '14: Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining

In this paper, we report the first empirical study and live test of the reserve price optimisation problem in the context of Real-Time Bidding (RTB) display advertising from an operational environment. A reserve price is the minimum that the auctioneer ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Guide Proceedings

CP '02: Proceedings of the 8th International Conference on Principles and Practice of Constraint Programming

September 2002

798 pages

ISBN:3540441204

Editor:
Pascal Van Hentenryck

Publisher

Springer-Verlag

Berlin, Heidelberg

Publication History

Published: 09 September 2002

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

31
Total Citations
View Citations
0
Total Downloads

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

Reflects downloads up to 19 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Zhang MArcuri A(2021)Adaptive Hypermutation for Search-Based System Test Generation: A Study on REST APIs with EvoMasterACM Transactions on Software Engineering and Methodology10.1145/346494031:1(1-52)Online publication date: 28-Sep-2021
https://dl.acm.org/doi/10.1145/3464940
Doerr CDreo JKerschke PAuger AStützle T(2019)Making a case for (Hyper-)parameter tuning as benchmark problemsProceedings of the Genetic and Evolutionary Computation Conference Companion10.1145/3319619.3326857(1755-1764)Online publication date: 13-Jul-2019
https://dl.acm.org/doi/10.1145/3319619.3326857
Belkhir NDréo JSavéant PSchoenauer MBosman P(2017)Per instance algorithm configuration of CMA-ES with limited budgetProceedings of the Genetic and Evolutionary Computation Conference10.1145/3071178.3071343(681-688)Online publication date: 1-Jul-2017
https://dl.acm.org/doi/10.1145/3071178.3071343
Gudu DJonker CMarsella SThangarajah JTuyls K(2016)MAS-based, Scalable Allocation of Resources in Large-scale, Dynamic EnvironmentsProceedings of the 2016 International Conference on Autonomous Agents & Multiagent Systems10.5555/2936924.2937240(1530-1531)Online publication date: 9-May-2016
https://dl.acm.org/doi/10.5555/2936924.2937240
Amadini RGabbrielli MMauro J(2016)Portfolio approaches for constraint optimization problemsAnnals of Mathematics and Artificial Intelligence10.1007/s10472-015-9459-576:1-2(229-246)Online publication date: 1-Feb-2016
https://dl.acm.org/doi/10.1007/s10472-015-9459-5
Hurley BO'Sullivan B(2015)Statistical regimes and runtime predictionProceedings of the 24th International Conference on Artificial Intelligence10.5555/2832249.2832293(318-324)Online publication date: 25-Jul-2015
https://dl.acm.org/doi/10.5555/2832249.2832293
Muñoz MSun YKirley MHalgamuge S(2015)Algorithm selection for black-box continuous optimization problemsInformation Sciences: an International Journal10.1016/j.ins.2015.05.010317:C(224-245)Online publication date: 1-Oct-2015
https://dl.acm.org/doi/10.1016/j.ins.2015.05.010
Fawcett CVallati MHutter FHoffmann JHoos HLeyton-Brown K(2014)Improved features for runtime prediction of domain-independent plannersProceedings of the Twenty-Fourth International Conferenc on International Conference on Automated Planning and Scheduling10.5555/3038794.3038837(355-359)Online publication date: 21-Jun-2014
https://dl.acm.org/doi/10.5555/3038794.3038837
Leyton-Brown KHoos HHutter FXu L(2014)Understanding the empirical hardness of NP-complete problemsCommunications of the ACM10.1145/2594413.259442457:5(98-107)Online publication date: 1-May-2014
https://dl.acm.org/doi/10.1145/2594413.2594424
Hutter FHoos HLeyton-Brown K(2013)Identifying Key Algorithm Parameters and Instance Features Using Forward SelectionRevised Selected Papers of the 7th International Conference on Learning and Intelligent Optimization - Volume 799710.1007/978-3-642-44973-4_40(364-381)Online publication date: 7-Jan-2013
https://dl.acm.org/doi/10.1007/978-3-642-44973-4_40
Show More Cited By

View Options

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

Media

Figures

Other

Tables

View Table of Contents