A Microstructure Based Approach to Constraint Satisfaction Optimisation Problems
2005 (English)In: The 18th International FLAIRS Conference,2005, Menlo Park, CA, USA: AAAI Press , 2005, 155- p.Conference paper (Refereed)
We study two constraint satisfaction optimisation problems: The Max Value problem for CSPs, which, somewhat simplified, aims at
maximising the sum of the (weighted) variable values in the solution, and the Max Ind problem, where the goal is to find a satisfiable subinstance of the original instance containing as many variables as possible. Both problems are NP-hard to approximate
within n^(1-e), e>0, where n is the number of variables in the problems, which implies that it is of interest to find exact algorithms. By exploiting properties of the microstructure, we construct algorithms for solving instances of these problems with small domain sizes, and then, using a probabilistic reasoning, we show how to get algorithms for more general versions of the problems. The resulting algorithms have running times of O((0.585d)^n) for Max Value (d,2)-CSP, and O((0.503d)^n) for MaxInd (d,2)-CSP. Both algorithms represent the best known theoretical bounds for their respective problem, and, more importantly, the methods used are applicable to a wide range of optimisation problems.
Place, publisher, year, edition, pages
Menlo Park, CA, USA: AAAI Press , 2005. 155- p.
Tvärvetenskap, artificial intelligence, constraint satisfaction, microstructure
IdentifiersURN: urn:nbn:se:liu:diva-24610Local ID: 6786OAI: oai:DiVA.org:liu-24610DiVA: diva2:244932