A filtering method for algorithm configuration based on consistency techniques

摘要

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.