A filtering method for algorithm configuration based on consistency techniques

Ignacio Araya, María Cristina Riff

Research output: Contribution to journalArticlepeer-review

1 Scopus citations

Abstract

Heuristic based algorithms are typically constructed following an iterative process in which the designer gradually introduces or modifies components or strategies whose performance is then tested by empirical evaluation on one or more sets of benchmark problems. This process often starts with some generic or broadly applicable problem solving method (e.g., metaheuristics, backtracking search), a new algorithmic idea or even an algorithm suggested by theoretical considerations. Then, through an iterative process, various combinations of components, methods and strategies are implemented/improved and tested. Even experienced designers often have to spend substantial amounts of time exploring and experimenting with different alternatives before obtaining an effective algorithm for a given problem. In this work, we are interested in assisting the designer in this task. Considering that components, methods and strategies are generally associated with parameters and parameter values, we propose a method able to detect, through a fine-tuning process, ineffective and redundant components/strategies of an algorithm. The approach is a model-free method and applies simple consistency techniques in order to discard values from the domain of the parameters. We validate our approach with two algorithms for solving SAT and MIP problems.

Original languageEnglish
Pages (from-to)73-81
Number of pages9
JournalKnowledge-Based Systems
Volume60
DOIs
StatePublished - Apr 2014
Externally publishedYes

Keywords

  • Algorithm configuration
  • Algorithm design
  • Consistency techniques
  • Constraint satisfaction problems
  • Parameter tuning

Fingerprint

Dive into the research topics of 'A filtering method for algorithm configuration based on consistency techniques'. Together they form a unique fingerprint.

Cite this