Constraint programming (CP) and Integer Linear Programming (IP) are both
highly successful technologies for solving a wide variety of combinatorial optimization problems. When modelling a combinatorial optimization problem, there
is often a choice about what technology to use to solve that problem. For
instance in the Bid Evaluation problem (BEP) - a combinatorial optimization
problem arising in combinatorial auctions - both CP and IP can successfully
be used. While there exist domains where one can easily predict what technology will excel, in many domains it is not clear
which will be more effective. The BEP falls into the latter case.
How do we choose among technologies when all instances share the same
problem structure? We are currently investigating machine learning
methodologies to explore structure at the instance level as a means to distinguish whether to
use CP or IP to solve instances of the BEP.
Here we investigate an approach based on Case Based Reasoning (CBR),
a technique arising within Artificial Intelligence, as a framework within which to carry out this exploration.
CBR utilises similarity between problems to determine when to reuse
past experiences to solve new problems. An experience in this context is what
technology to use to solve an instance of the BEP. Using a representation that
distinguishes problems at the instance level, and a similarity function to
compare problems expressed in this representation, enables us to determine
what technology to use on a new problem instance.
