Empirical evaluation of Soft Arc Consistency algorithms for solving Constraint Optimization Problems

View/ Open
Date
2011-09-19Author
Gantan, Xiaonuo
Type
ThesisDegree Level
MastersMetadata
Show full item recordAbstract
A large number of problems in Artificial Intelligence and other areas of science can be viewed as special cases of constraint satisfaction or optimization problems. Various approaches have been widely studied, including search, propagation, and heuristics. There are still challenging real-world COPs that cannot be solved using current methods. We implemented and compared several consistency propagation algorithms, which include W-AC*2001, EDAC, VAC, and xAC. Consistency propagation is a classical method to reduce the search space in CSPs, and has been adapted to COPs. We compared several consistency propagation algorithms, based on the resemblance between the optimal value ordering and the approximate value ordering generated by them. The results showed that xAC generated value orderings of higher quality than W-AC*2001 and EDAC. We evaluated some novel hybrid methods for solving COPs. Hybrid methods combine consistency propagation and search in order to reach a good solution as soon as possible and prune the search space as much as possible. We showed that the hybrid method which combines the variant TP+OnOff and branch-and-bound search performed fewer constraint checks and searched fewer nodes than others in solving random and real-world COPs.
Degree
Master of Science (M.Sc.)Department
Computer ScienceProgram
Computer ScienceSupervisor
Horsch, Michael C.Committee
Kusalik, Anthony J.; Stanley, KevinCopyright Date
August 2011Subject
Constraint Optimization
Soft Arc Consistency
xAC