University of SaskatchewanHARVEST
  • Login
  • Submit Your Research
  • About
    • About HARVEST
    • Guidelines
    • Browse
      • All of HARVEST
      • Communities & Collections
      • By Issue Date
      • Authors
      • Titles
      • Subjects
      • This Collection
      • By Issue Date
      • Authors
      • Titles
      • Subjects
    • My Account
      • Login
      JavaScript is disabled for your browser. Some features of this site may not work without it.
      View Item 
      • HARVEST
      • Electronic Theses and Dissertations
      • Graduate Theses and Dissertations
      • View Item
      • HARVEST
      • Electronic Theses and Dissertations
      • Graduate Theses and Dissertations
      • View Item

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

      Thumbnail
      View/Open
      GANTAN-THESIS.pdf (884.4Kb)
      Date
      2011-09-19
      Author
      Gantan, Xiaonuo
      Type
      Thesis
      Degree Level
      Masters
      Metadata
      Show full item record
      Abstract
      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 Science
      Program
      Computer Science
      Supervisor
      Horsch, Michael C.
      Committee
      Kusalik, Anthony J.; Stanley, Kevin
      Copyright Date
      August 2011
      URI
      http://hdl.handle.net/10388/ETD-2011-08-53
      Subject
      Constraint Optimization
      Soft Arc Consistency
      xAC
      Collections
      • Graduate Theses and Dissertations
      University of Saskatchewan

      University Library

      © University of Saskatchewan
      Contact Us | Disclaimer | Privacy