ECAI 2004 Conference Paper

[full paper]

Learning techniques for Automatic Algorithm Portfolio Selection

Alessio Guerri, Michela Milano

The purpose of this paper is to show that a well known machine learning technique based on Decision Trees can be effectively used to select the best approach (in terms of efficiency) in an algorithm portfolio for a particular case study. In particular, we are interested in deciding when to use a Constraint Programming (CP) approach and when an Integer Programming (IP) approach, on the basis of the structure of the instance considered. Different instances of the same problem present different features and structure, and one aspect (e.g. feasibility or optimality) can prevail on the other. As a case study, we use the Bid Evaluation Problem (BEP) arising in Combinatorial Auctions. We have extracted from a set of BEP instances, a number of parameters representing the instance structure. Some of them (few indeed) precisely identify the best strategy and its corresponding tuning to be used to face that instance. We will show that this approach is very promising, since it achieves the correct identification in the 90% of the cases.

Keywords: Constraint Satisfaction and Optimization Problem, Algorithm Portfolio, Machine Learning, Combinatorial Auction

Citation: Alessio Guerri, Michela Milano: Learning techniques for Automatic Algorithm Portfolio Selection. In R.López de Mántaras and L.Saitta (eds.): ECAI2004, Proceedings of the 16th European Conference on Artificial Intelligence, IOS Press, Amsterdam, 2004, pp.475-479.