Instance Structure-Based Portfolio Selection - Abstract


Many large scale combinatorial problems have a complex structure that prevents a single algorithm and a single technology to outperform all the others on all instances. Therefore algorithms portfolios can be defined embedding more that one approach to the same problem. How do we choose among algorithms when all instances share the same problem structure? This paper is a first attempt to answer this question by using a machine learning technique, namely decision trees, for selecting the best approach given the instance to be solved. We will show that structural instance features provide a clear indication on the best approach to be used. We have extensively tested our conjecture on a case study: the Bid Evaluation Problem in combinatorial auctions, a well known e-commerce application. We will show that, for the problem considered, the computed decision tree identifies the best approach for the 90% of the instances by using a small set of instance features. We believe this result can be extended to a large variety of combinatorial problems.






Quick Links
 Last updated Mar. 21, 2004