Making Choices Using Structure at the Instance Level exploiting Case Based Reasoning - Abstract


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.






Quick Links
 Last updated Mar. 21, 2004