Instance-Specific Algorithm Configuration as a Method for Non-Model-Based Portfolio Generation | SpringerLink
Skip to main content
Springer Nature Link
Log in

Instance-Specific Algorithm Configuration as a Method for Non-Model-Based Portfolio Generation

  • Conference paper
Integration of AI and OR Techniques in Contraint Programming for Combinatorial Optimzation Problems (CPAIOR 2012)

Part of the book series: Lecture Notes in Computer Science ((LNTCS,volume 7298))

Abstract

Instance-specific algorithm configuration generalizes both instance-oblivious algorithm tuning as well as algorithm portfolio generation. ISAC is a recently proposed non-model-based approach for tuning solver parameters dependent on the specific instance that needs to be solved. While ISAC has been compared with instance-oblivious algorithm tuning systems before, to date a comparison with portfolio generators and other instance-specific algorithm configurators is crucially missing. In this paper, among others, we provide a comparison with SATzilla, as well as three other algorithm configurators: Hydra, DCM and ArgoSmart. Our experimental comparison shows that non-model-based ISAC significantly outperforms prior state-of-the-art algorithm selectors and configurators. The following study was the foundation for the best sequential portfolio at the 2011 SAT Competition.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
JPY 3498
Price includes VAT (Japan)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
JPY 5719
Price includes VAT (Japan)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
JPY 7149
Price includes VAT (Japan)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

References

  1. Adenso-Diaz, B., Laguna, M.: Fine-tuning of Algorithms using Fractional Experimental Design and Local Search. Operations Research 54(1), 99–114 (2006)

    Article  MATH  Google Scholar 

  2. Ansótegui, C., Sellmann, M., Tierney, K.: A Gender-Based Genetic Algorithm for the Automatic Configuration of Algorithms. In: Gent, I.P. (ed.) CP 2009. LNCS, vol. 5732, pp. 142–157. Springer, Heidelberg (2009)

    Chapter  Google Scholar 

  3. ArgoSAT, http://argo.matf.bg.ac.rs/software/

  4. Biere, A.: Picosat version 535. Solver description. SAT Competition (2007)

    Google Scholar 

  5. Bregman, D.R., Mitchell, D.G.: The SAT Solver MXC, version 0.75. Solver description. SAT Race Competition (2008)

    Google Scholar 

  6. Breiman, L.: Bagging Predictors. Machine Learning 24(2), 123–140 (1996)

    MathSciNet  MATH  Google Scholar 

  7. Dequen, G., Dubois, O.: Dubois. kcnfs. Solver description. SAT Competition (2007)

    Google Scholar 

  8. Gomes, C.P., Selman, B.: Algorithm Portfolios. Artificial Intelligence 126(1-2), 43–62 (2001)

    Article  MathSciNet  MATH  Google Scholar 

  9. Hamerly, G., Elkan, C.: Learning the K in K-Means. In: NIPS (2003)

    Google Scholar 

  10. Heule, M., Dufour, M., van Zwieten, J.E., van Maaren, H.: March_eq: Implementing Additional Reasoning into an Efficient Look-Ahead SAT Solver. In: H. Hoos, H., Mitchell, D.G. (eds.) SAT 2004. LNCS, vol. 3542, pp. 345–359. Springer, Heidelberg (2005)

    Chapter  Google Scholar 

  11. Hoos, H.H.: Adaptive Novelty+: Novelty+ with adaptive noise. In: AAAI (2002)

    Google Scholar 

  12. Hutter, F., Tompkins, D., Hoos, H.H.: RSAPS: Reactive Scaling And Probabilistic Smoothing. In: CP (2002)

    Google Scholar 

  13. Hutter, F., Hamadi, Y.: Parameter Adjustment Based on Performance Prediction: Towards an Instance-Aware Problem Solver. Technical Report, MSR-TR-2005-125, Microsoft Research Cambridge (2005)

    Google Scholar 

  14. Hutter, F., Hamadi, Y., Hoos, H.H., Leyton-Brown, K.: Performance Prediction and Automated Tuning of Randomized and Parametric Algorithms. In: Benhamou, F. (ed.) CP 2006. LNCS, vol. 4204, pp. 213–228. Springer, Heidelberg (2006)

    Chapter  Google Scholar 

  15. Hutter, F., Hoos, H.H., Leyton-Brown, K., Stuetzle, T.: ParamILS: An Automatic Algorithm Configuration Framework. JAIR 36, 267–306 (2009)

    MATH  Google Scholar 

  16. Kadioglu, S., Malitsky, Y., Sellmann, M., Tierney, K.: ISAC – Instance-Specific Algorithm Configuration. In: ECAI, pp. 751–756 (2010)

    Google Scholar 

  17. KhudaBukhsh, A.R., Xu, L., Hoos, H.H., Leyton-Brown, K.: SATenstein: Automatically Building Local Search SAT Solvers From Components. In: IJCAI (2009)

    Google Scholar 

  18. Leyton-Brown, K., Nudelman, E., Andrew, G., McFadden, J., Shoham, Y.: A Portfolio Approach to Algorithm Selection. In: IJCAI, pp. 1542–1543 (2003)

    Google Scholar 

  19. Li, C.M., Huang, W.Q.: G2WSAT: Gradient-based Greedy WalkSAT. In: Bacchus, F., Walsh, T. (eds.) SAT 2005. LNCS, vol. 3569, pp. 158–172. Springer, Heidelberg (2005)

    Chapter  Google Scholar 

  20. Nikolić, M., Marić, F., Janičić, P.: Instance-Based Selection of Policies for SAT Solvers. In: Kullmann, O. (ed.) SAT 2009. LNCS, vol. 5584, pp. 326–340. Springer, Heidelberg (2009)

    Chapter  Google Scholar 

  21. O’Mahony, E., Hebrard, E., Holland, A., Nugent, C., O’Sullivan, B.: Using Case-based Reasoning in an Algorithm Portfolio for Constraint Solving. In: Irish Conference on Artificial Intelligence and Cognitive Science (2008)

    Google Scholar 

  22. Pham, D.N., Anbulagan: ranov. Solver description. SAT Competition (2007)

    Google Scholar 

  23. Pham, D.N., Gretton, C.: gnovelty+. Solver description. SAT Competition (2007)

    Google Scholar 

  24. Prestwich, S.: VW: Variable Weighting Scheme. In: SAT (2005)

    Google Scholar 

  25. SAT Competition, http://www.satcomptition.org

  26. Smith-Miles, K.A.: Cross-disciplinary perspectives on meta-learning for algorithm selection. ACM Comput. Surv. 41(1), 6:1–6:25 (2009)

    Article  Google Scholar 

  27. Silverthorn, B., Miikkulainen, R.: Latent Class Models for Algorithm Portfolio Methods. In: AAAI (2010)

    Google Scholar 

  28. Thornton, J., Pham, D.N., Bain, S., Ferreira, V.: Additive versus multiplicative clause weighting for SAT. In: PRICAI, pp. 405–416 (2008)

    Google Scholar 

  29. Tompkins, D.A.D., Hutter, F., Hoos, H.H.: saps. Solver description. SAT Competition (2007)

    Google Scholar 

  30. Wei, W., Li, C.M., Zhang, H.: Combining adaptive noise and promising decreasing variables in local search for SAT. Solver description. SAT Competition (2007)

    Google Scholar 

  31. Wei, W., Li, C.M., Zhang, H.: Deterministic and random selection of variables in local search for SAT. Solver description. SAT Competition (2007)

    Google Scholar 

  32. Wei, W., Li, C.M., Zhang, H.: adaptg2wsatp. Solver description. SAT Competition (2007)

    Google Scholar 

  33. Xu, L., Hoos, H.H., Leyton-Brown, K.: Hydra: Automatically Configuring Algorithms for Portfolio-Based Selection. In: AAAI (2010)

    Google Scholar 

  34. Xu, L., Hutter, F., Hoos, H.H., Leyton-Brown, K.: SATzilla2009: an Automatic Algorithm Portfolio for SAT. Solver description. SAT Competition (2009)

    Google Scholar 

  35. Xu, L., Hutter, F., Hoos, H.H., Leyton-Brown, K.: SATzilla: Portfolio-based Algorithm Selection for SAT. JAIR 32(1), 565–606 (2008)

    MATH  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Computer Science, Brown University, USA

    Yuri Malitsky

  2. IBM Research Watson, USA

    Meinolf Sellmann

Authors
  1. Yuri Malitsky
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Meinolf Sellmann
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Editors and Affiliations

  1. École des Mines de Nantes, 4, rue Alfred Kastler, 44307, Nantes Cedex 3, France

    Nicolas Beldiceanu

  2. École des Mines de Nantes, 4 rue Alfred Kastler, 44307, Nantes Cedex 3, France

    Narendra Jussien

  3. Institut de Mathématiques Appliquées, 44 rue Rabelais, 49008, Angers Cedex 01, France

    Éric Pinson

Rights and permissions

Reprints and permissions

Copyright information

© 2012 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Malitsky, Y., Sellmann, M. (2012). Instance-Specific Algorithm Configuration as a Method for Non-Model-Based Portfolio Generation. In: Beldiceanu, N., Jussien, N., Pinson, É. (eds) Integration of AI and OR Techniques in Contraint Programming for Combinatorial Optimzation Problems. CPAIOR 2012. Lecture Notes in Computer Science, vol 7298. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-29828-8_16

Download citation

  • DOI: https://doi.org/10.1007/978-3-642-29828-8_16

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-642-29827-1

  • Online ISBN: 978-3-642-29828-8

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation