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.
