Empirical hardness models

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Empirical hardness models: Methodology and a case study on combinatorial auctions

Full text

Pdf (1.66 MB)

Source

Journal of the ACM (JACM) archive
Volume 56 , Issue 4 (June 2009) table of contents

Article No. 22

Year of Publication: 2009

ISSN:0004-5411

Authors

Kevin Leyton-Brown	University of British Columbia, Vancouver, British Columbia, Canada
Eugene Nudelman	Stanford University, Stanford, California
Yoav Shoham	Stanford University, Stanford, California

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 19, Downloads (12 Months): 137, Citation Count: 0

Additional Information:

abstract references index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/1538902.1538906 What is a DOI?

ABSTRACT

Is it possible to predict how long an algorithm will take to solve a previously-unseen instance of an NP-complete problem? If so, what uses can be found for models that make such predictions? This article provides answers to these questions and evaluates the answers experimentally.

We propose the use of supervised machine learning to build models that predict an algorithm's runtime given a problem instance. We discuss the construction of these models and describe techniques for interpreting them to gain understanding of the characteristics that cause instances to be hard or easy. We also present two applications of our models: building algorithm portfolios that outperform their constituent algorithms, and generating test distributions that emphasize hard problems.

We demonstrate the effectiveness of our techniques in a case study of the combinatorial auction winner determination problem. Our experimental results show that we can build very accurate models of an algorithm's running time, interpret our models, build an algorithm portfolio that strongly outperforms the best single algorithm, and tune a standard benchmark suite to generate much harder problem instances.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	Dimitris Achlioptas, Lower bounds for random 3-SAT via differential equations, Theoretical Computer Science, v.265 n.1_2, p.159-185, 08/28/2001 [doi>10.1016/S0304-3975(01)00159-1]
	2	Dimitris Achlioptas , Paul Beame , Michael Molloy, A sharp threshold in proof complexity yields lower bounds for satisfiability search, Journal of Computer and System Sciences, v.68 n.2, p.238-268, March 2004 [doi>10.1016/j.jcss.2003.07.011]
	3	Dimitris Achlioptas , Carla P. Gomes , Henry A. Kautz , Bart Selman, Generating Satisfiable Problem Instances, Proceedings of the Seventeenth National Conference on Artificial Intelligence and Twelfth Conference on Innovative Applications of Artificial Intelligence, p.256-261, July 30-August 03, 2000
	4	Achlioptas, D., Jia, H., and Moore, C. 2005. Hiding satisfying assignments: Two are better than one. J. Artif. Intell. Res. 24, 623--639.
	5	Integer Programming for Combinatorial Auction Winner Determination, Proceedings of the Fourth International Conference on MultiAgent Systems (ICMAS-2000), p.39, July 10-12, 2000
	6	Paul Beame , Richard Karp , Toniann Pitassi , Michael Saks, On the complexity of unsatisfiability proofs for random k-CNF formulas, Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.561-571, May 24-26, 1998, Dallas, Texas, United States [doi>10.1145/276698.276870]
	7	Eric Allen Brewer , William E. Weihl, Portable high-performance supercomputing: high-level platform-dependent optimization, Massachusetts Institute of Technology, 1994
	8	Eric A. Brewer, High-level optimization via automated statistical modeling, Proceedings of the fifth ACM SIGPLAN symposium on Principles and practice of parallel programming, p.80-91, July 19-21, 1995, Santa Barbara, California, United States
	9	Carchrae, T., and Beck, J. C. 2005. Applying machine learning to low knowledge control of optimization algorithms. Computat. Intell. 21, 4, 372--387.
	10	Chaloner, K., and Verdinelli, I. 1995. Bayesian experimental design: A review. Statist. Sci. 10, 273--304.
	11	Cheeseman, P., Kanefsky, B., and Taylor, W. M. 1991. Where the really hard problems are. In IJCAI: Proceedings of the International Joint Conference on Artificial Intelligence. 331--337.
	12	Simona Cocco , Rémi Monasson, Heuristic average-case analysis of the backtrack resolution of random 3-satisfiability instances, Theoretical Computer Science, v.320 n.2-3, p.345-372, June 14, 2004 [doi>10.1016/j.tcs.2004.02.034]
	13	Peter Cramton , Yoav Shoham , Richard Steinberg, Combinatorial Auctions, The MIT Press, 2006
	14	de Farias, D. P., and Megiddo, N. 2004. How to combine expert (or novice) advice when actions impact the environment. In NIPS: Proceedings of the Neural Information Processing Systems Conference.
	15	Sven de Vries , Rakesh V. Vohra, Combinatorial Auctions: A Survey, INFORMS Journal on Computing, v.15 n.3, p.284-309, July 2003 [doi>10.1287/ijoc.15.3.284.16077]
	16	Diao, Y., Eskesen, F., Proehlich, S., Hellerstein, J., Spainhower, L., and Surendra, M. 2003. Generic online optimization of multiple configuration parameters with application to a database server. Proceedings of the IFIP/IEEE International Workshop on Distributed Systems: Operations and Man- agement.
	17	Doucet, A., de Freitas, N., and Gorden, N. (Eds.) 2001. Sequential Monte Carlo Methods in Practice. Springer-Verlag.
	18	O. Dubois , Y. Boufkhad, A general upper bound for the satisfiability threshold of random r-SAT formulae, Journal of Algorithms, v.24 n.2, p.395-420, Aug. 1997 [doi>10.1006/jagm.1997.0867]
	19	Olivier Dubois , Yacine Boufkhad , Jacques Mandler, Typical random 3-SAT formulae and the satisfiability threshold, Proceedings of the eleventh annual ACM-SIAM symposium on Discrete algorithms, p.126-127, January 09-11, 2000, San Francisco, California, United States
	20	Efron, B., Hastie, T., Johnstone, I., and Tibshirani, R. 2004. Least angle regression. Ann. Stat. 32, 407--451.
	21	Susan L. Epstein , Eugene C. Freuder , Richard Wallace , Anton Morozov , Bruce Samuels, The Adaptive Constraint Engine, Proceedings of the 8th International Conference on Principles and Practice of Constraint Programming, p.525-542, September 09-13, 2002
	22	John Franco, Results related to threshold phenomena research in satisfiability: lower bounds, Theoretical Computer Science, v.265 n.1_2, p.147-157, 08/28/2001 [doi>10.1016/S0304-3975(01)00158-X]
	23	Friedman, J. 1991. Multivariate adaptive regression splines. Ann. Stat. 19, 1, 1--141.
	24	Alan Frieze , Stephen Suen, Analysis of two simple heuristics on a random instance of k-SAT, Journal of Algorithms, v.20 n.2, p.312-355, March 1996 [doi>10.1006/jagm.1996.0016]
	25	Yuzo Fujishima , Kevin Leyton-Brown , Yoav Shoham, Taming the Computational Complexity of Combinatorial Auctions: Optimal and Approximate Approaches, Proceedings of the Sixteenth International Joint Conference on Artificial Intelligence, p.548-553, July 31-August 06, 1999
	26	Matteo Gagliolo , Jürgen Schmidhuber, Learning dynamic algorithm portfolios, Annals of Mathematics and Artificial Intelligence, v.47 n.3-4, p.295-328, August 2006 [doi>10.1007/s10472-006-9036-z]
	27	Gebruers, C., and Guerri, A. 2004. Machine learning for portfolio selection using structure at the instance level. In Principles and Practice of Constraint Programming, Doctoral Consortium.
	28	Gebruers, C., Guerri, A., Hnich, B., and Milano, M. 2004. Making choices using structure at the instance level within a case based reasoning framework. In CPAIOR: Proceedings of the International Conference on Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems. 380--386.
	29	Gebruers, C., Hnich, B., Bridge, D., and Freuder, E. 2005. Using CBR to select solution strategies in constraint programming. In ICCBR: Proceedings of the International Conference on Case-Based Reasoning. 222--236.
	30	Simon F. Goldsmith , Alex S. Aiken , Daniel S. Wilkerson, Measuring empirical computational complexity, Proceedings of the the 6th joint meeting of the European software engineering conference and the ACM SIGSOFT symposium on The foundations of software engineering, September 03-07, 2007, Dubrovnik, Croatia [doi>10.1145/1287624.1287681]
	31	Goldszmidt, M. 2007. Making life better one large system at a time: Challenges for UAI research. In UAI: Proceedings of the Conference on Uncertainty in Artificial Intelligence.
	32	Gomes, C., Fernández, C., Selman, B., and Bessière, C. 2004. Statistical regimes across constrainedness regions. In CP: Proceedings of the International Conference on Principles and Practice of Constraint Programming.
	33	Carla P. Gomes , Bart Selman, Algorithm portfolios, Artificial Intelligence, v.126 n.1-2, p.43-62, Feb., 2001 [doi>10.1016/S0004-3702(00)00081-3]
	34	Carla P. Gomes , Bart Selman , Nuno Crato , Henry Kautz, Heavy-Tailed Phenomena in Satisfiability and Constraint Satisfaction Problems, Journal of Automated Reasoning, v.24 n.1-2, p.67-100, February 2000 [doi>10.1023/A:1006314320276]
	35	Gomes, C. P., and Selman, B. 1997. Problem structure in the presence of perturbations. In AAAI: Proceedings of the AAAI Conference on Artif. Intell. 221--226.
	36	Rica Gonen , Daniel Lehmann, Optimal solutions for multi-unit combinatorial auctions: branch and bound heuristics, Proceedings of the 2nd ACM conference on Electronic commerce, p.13-20, October 17-20, 2000, Minneapolis, Minnesota, United States [doi>10.1145/352871.352873]
	37	Gonen, R., and Lehmann, D. 2001. Linear programming helps solving large multi-unit combinatorial auctions. Tech. Rep. TR-2001-8, Leibniz Center for Research in Computer Science. April.
	38	Guo, H., and Hsu, W. 2007. A machine learning approach to algorithm selection for NP-hard optimization problems. Ann. Oper. Res. 156, 1 (Dec.), 61--82.
	39	Hastie, T., Tibshirani, R., and Friedman, J. 2001. Elements of Statistical Learning. Springer-Verlang, Berlin, Germany.
	40	Holger H. Hoos , Craig Boutilier, Solving Combinatorial Auctions Using Stochastic Local Search, Proceedings of the Seventeenth National Conference on Artificial Intelligence and Twelfth Conference on Innovative Applications of Artificial Intelligence, p.22-29, July 30-August 03, 2000
	41	Holger H. Hoos , Thomas Stützle, Towards a characterisation of the behaviour of stochastic local search algorithms for SAT, Artificial Intelligence, v.112 n.1-2, p.213-232, Aug. 1999 [doi>10.1016/S0004-3702(99)00048-X]
	42	Holger Hoos , Thomas Sttzle, Stochastic Local Search: Foundations & Applications, Morgan Kaufmann Publishers Inc., San Francisco, CA, 2004
	43	Eric Horvitz , Yongshao Ruan , Carla P. Gomes , Henry A. Kautz , Bart Selman , David Maxwell Chickering, A Bayesian Approach to Tackling Hard Computational Problems, Proceedings of the 17th Conference in Uncertainty in Artificial Intelligence, p.235-244, August 02-05, 2001
	44	Huberman, B., Lukose, R., and Hogg, T. 1997. An economics approach to hard computational problems. Science 265, 51--54.
	45	Hutter, F., Hamadi, Y., Hoos, H. H., and Leyton-Brown, K. 2006. Performance prediction and automated tuning of randomized and parametric algorithms. In CP: Proceedings of the International Conference on Principles and Practice of Constraint Programming. Lecture Notes in Computer Science, vol. 4204. Springer-Verlag, Berlin, Germany, 213--228.
	46	Jia, H., Moore, C., and Selman, B. 2004. From spin glasses to hard satisfiable formulas. In SAT: Proceedings of the International Conference on Theory and Applications of Satisfiability Testing. 199--210.
	47	Jia, H., Moore, C., and Strain, D. 2007. Generating hard satisfiable formulas by hiding solutions deceptively. J. Artif. Intell. Res. 28, 107--118.
	48	Knuth, D. 1975. Estimating the efficiency of backtrack programs. Math. Comput. 29, 129, 121--136.
	49	Ron Kohavi , George H. John, Wrappers for feature subset selection, Artificial Intelligence, v.97 n.1-2, p.273-324, Dec. 1997 [doi>10.1016/S0004-3702(97)00043-X]
	50	Kolaitis, P. 2003. Constraint satisfaction, databases and logic. In IJCAI: Proceedings of the International Joint Conference on Artificial Intelligence. 1587--1595.
	51	Richard E. Korf , Michael Reid, Complexity analysis admissible heuristic search, Proceedings of the fifteenth national/tenth conference on Artificial intelligence/Innovative applications of artificial intelligence, p.305-310, July 1998, Madison, Wisconsin, United States
	52	Michail G. Lagoudakis , Michael L. Littman, Algorithm Selection using Reinforcement Learning, Proceedings of the Seventeenth International Conference on Machine Learning, p.511-518, June 29-July 02, 2000
	53	Lagoudakis, M., and Littman, M. 2001. Learning to select branching rules in the DPLL procedure for satisfiability. In SAT: Proceedings of the International Conference on Theory and Applications of Satisfiability Testing. 344--359.
	54	Leyton-Brown, K., Nudelman, E., Andrew, G., McFadden, J., and Shoham, Y. 2003a. Boosting as a metaphor for algorithm design. In CP: Proceedings of the International Conference on Principles and Practice of Constraint Programming. 899--903.
	55	Leyton-Brown, K., Nudelman, E., Andrew, G., McFadden, J., and Shoham, Y. 2003b. A portfolio approach to algorithm selection. In IJCAI: Proceedings of the International Joint Conference on Artificial Intelligence. 1542--1543.
	56	Kevin Leyton-Brown , Eugene Nudelman , Yoav Shoham, Learning the Empirical Hardness of Optimization Problems: The Case of Combinatorial Auctions, Proceedings of the 8th International Conference on Principles and Practice of Constraint Programming, p.556-572, September 09-13, 2002
	57	Leyton-Brown, K., Nudelman, E., and Shoham, Y. 2006. Empirical hardness models for combinatorial auctions. In Combinatorial Auctions. MIT Press, Cambridge, Chap. 19, 479--504.
	58	Kevin Leyton-Brown , Mark Pearson , Yoav Shoham, Towards a universal test suite for combinatorial auction algorithms, Proceedings of the 2nd ACM conference on Electronic commerce, p.66-76, October 17-20, 2000, Minneapolis, Minnesota, United States [doi>10.1145/352871.352879]
	59	Kevin Leyton-Brown , Yoav Shoham , Moshe Tennenholtz, An Algorithm for Multi-Unit Combinatorial Auctions, Proceedings of the Seventeenth National Conference on Artificial Intelligence and Twelfth Conference on Innovative Applications of Artificial Intelligence, p.56-61, July 30-August 03, 2000
	60	Lionel Lobjois , Michel Lemaître, Branch and bound algorithm selection by performance prediction, Proceedings of the fifteenth national/tenth conference on Artificial intelligence/Innovative applications of artificial intelligence, p.353-358, July 1998, Madison, Wisconsin, United States
	61	Mason, R. L., Gunst, R. F., and Hess, J. L. 2003. Statistical Design and Analysis of Experiments. Wiley-Interscience, New York.
	62	Monasson, R., Zecchina, R., Kirkpatrick, S., Selman, B., and Troyansky, L. 1998. Determining computational complexity for characteristic ‘phase transitions’. Nature 400, 133--137.
	63	Noam Nisan, Bidding and allocation in combinatorial auctions, Proceedings of the 2nd ACM conference on Electronic commerce, p.1-12, October 17-20, 2000, Minneapolis, Minnesota, United States [doi>10.1145/352871.352872]
	64	Nudelman, E., Leyton-Brown, K., Devkar, A., Shoham, Y., and Hoos, H. H. 2004a. SATzilla: An algorithm portfolio for SAT. In Proceedings of the International Conference on Theory and Applications of Satisfiability Testing, SAT 2004 Competition: Solver Descriptions. 13--14.
	65	Nudelman, E., Leyton-Brown, K., Devkar, A., Shoham, Y., and Hoos, H. H. 2004b. Understanding random SAT: Beyond the clauses-to-variables ratio. In CP: Proceedings of the International Conference on Principles and Practice of Constraint Programming. 438--452.
	66	Rice, J. R. 1976. The algorithm selection problem. Adv. Comput. 15, 65--118.
	67	Michael H. Rothkopf , Aleksandar Pekec , Ronald M. Harstad, Computationally Manageable Combinational Auctions, Management Science, v.44 n.8, p.1131-1147, August 1998 [doi>10.1287/mnsc.44.8.1131]
	68	Yongshao Ruan , Eric Horvitz , Henry A. Kautz, Restart Policies with Dependence among Runs: A Dynamic Programming Approach, Proceedings of the 8th International Conference on Principles and Practice of Constraint Programming, p.573-586, September 09-13, 2002
	69	Tuomas Sandholm, An Algorithm for Optimal Winner Determination in Combinatorial Auctions, Proceedings of the Sixteenth International Joint Conference on Artificial Intelligence, p.542-547, July 31-August 06, 1999
	70	Tuomas Sandholm, Algorithm for optimal winner determination in combinatorial auctions, Artificial Intelligence, v.135 n.1-2, p.1-54, 02/01/2002 [doi>10.1016/S0004-3702(01)00159-X]
	71	Sandholm, T., Suri, S., Gilpin, A., and Levine, D. 2001. CABOB: A fast optimal algorithm for combinatorial auctions. In IJCAI: Proceedings of the International Joint Conference on Artificial Intelligence. 1102--1108.
	72	Sandholm, T., Suri, S., Gilpin, A., and Levine, D. 2005. CABOB: A fast optimal algorithm for winner determination in combinatorial auctions. Manage. Sci. 51, 3, 374--390.
	73	Robert E. Schapire, The Strength of Weak Learnability, Machine Learning, v.5 n.2, p.197-227, Jun. 1990 [doi>10.1023/A:1022648800760]
	74	Schmee, J., and Hahn, G. J. 1979. A simple method for regression analysis with censored data. Technometrics 21, 4, 417--432.
	75	Bart Selman , David G. Mitchell , Hector J. Levesque, Generating hard satisfiability problems, Artificial Intelligence, v.81 n.1-2, p.17-29, March 1996 [doi>10.1016/0004-3702(95)00045-3]
	76	Slaney, J., and Walsh, T. 2001. Backbones in optimization and approximation. In IJCAI: Proceedings of the International Joint Conference on Artificial Intelligence. 254--259.
	77	Streeter, M., Golovin, D., and Smith, S. F. 2007. Combining multiple heuristics online. In AAAI: Proceedings of the AAAI Conference on Artificial Intelligence. 1197--1203.
	78	Williams, R., Gomes, C., and Selman, B. 2003. Backdoors to typical case complexity. In IJCAI: Proceedings of the International Joint Conference on Artificial Intelligence. 1173--1178.
	79	Xu, L., Hoos, H. H., and Leyton-Brown, K. 2007a. Hierarchical hardness models for SAT. In CP: Proceedings of the International Conference on Principles and Practice of Constraint Programming. Lecture Notes in Computer Science, vol. 4741. Springer-Verlag, Berlin, Germany, 696--711.
	80	Xu, L., Hutter, F., Hoos, H. H., and Leyton-Brown, K. 2007b. SATzilla-07: The design and analysis of an algorithm portfolio for SAT. In CP: Proceedings of the International Conference on Principles and Practice of Constraint Programming. Lecture Notes in Computer Science, vol. 4741. Springer-Verlag, Berlin, Germany, 712--727.
	81	Xu, L., Hutter, F., Hoos, H. H., and Leyton-Brown, K. 2008. SATzilla: Portfolio-based algorithm selection for SAT. J. Artif. Intell. Res. 32, 565--606.
	82	Zhang, W. 1999. State-Space Search: Algorithms, Complexity, Extensions, and Applications. Springer-Verlag, Berlin, Germany.
	83	Weixiong Zhang, Phase Transitions and Backbones of 3-SAT and Maximum 3-SAT, Proceedings of the 7th International Conference on Principles and Practice of Constraint Programming, p.153-167, November 26-December 01, 2001
	84	Zheng, A., Jordan, M., Liblit, B., and Aiken, A. 2003. Statistical debugging of sampled programs. In NIPS: Proceedings of the Neural Information Processing Systems Conference.