Acquiring local preferences of Weighted Partial MaxSAT

dc.contributor.authorHuang, Hong
dc.contributor.authorCliment, Laura
dc.contributor.authorO'Sullivan, Barry
dc.contributor.funderScience Foundation Irelanden
dc.description.abstractMany real-life problems can be formulated as boolean satisfiability (SAT). In addition, in many of these problems, there are some hard clauses that must be satisfied but also some other soft clauses that can remain unsatisfied at some cost. These problems are referred to as Weighted Partial Maximum Satisfiability (WPMS). For solving them, the challenge is to find a solution that minimizes the total sum of costs of the unsatisfied clauses. Configuration problems are real-life examples of these, which involve customizing products according to a user's specific requirements. In the literature there exist many efficient techniques for finding solutions having minimum total cost. However, less attention has been paid to the fact that in many real-life problems the associated weights for soft clauses can be unknown. An example of such situations is when users cannot provide local preferences but instead express global preferences over complete assignments. In these cases, the acquisition of preferences can be the key for finding the best solution. In this paper, we propose a method to formalize the acquisition of local preferences. The process involves solving the associated system of linear equations for a set of complete assignments and their costs. Furthermore, we formalize the characteristics and size of the complete assignments required to acquire all local weights. We present an heuristic algorithm that searches for such assignments which performs promisingly on many benchmarks from the literature.en
dc.description.statusPeer revieweden
dc.description.versionAccepted Versionen
dc.identifier.citationHuang, H., Climent, L. and O'Sullivan, B. (2017) 'Acquiring Local Preferences of Weighted Partial MaxSAT'. 2017 IEEE 29th International Conference on Tools with Artificial Intelligence (ICTAI), Boston MA, 6-8 Nov, pp. 1065-1072. doi: 10.1109/ICTAI.2017.00163en
dc.publisherInstitute of Electrical and Electronics Engineers, IEEEen
dc.relation.projectinfo:eu-repo/grantAgreement/SFI/SFI Research Centres/12/RC/2289/IE/INSIGHT - Irelands Big Data and Analytics Research Centre/en
dc.rights© 2017, IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all other uses, in any current or future media, including reprinting/republishing this material for advertising or promotional purposes, creating new collective works, for resale or redistribution to servers or lists, or reuse of any copyrighted component of this work in other worksen
dc.subjectAcquiring preferencesen
dc.subjectConfiguration problemsen
dc.subjectWeighted Partial MaxSATen
dc.subjectTask analysisen
dc.subjectLinear programmingen
dc.subjectMatrix convertersen
dc.subjectHeuristic algorithmsen
dc.subjectBenchmark testingen
dc.subjectMathematical modelen
dc.titleAcquiring local preferences of Weighted Partial MaxSATen
dc.typeConference itemen
Original bundle
Now showing 1 - 1 of 1
Thumbnail Image
283.16 KB
Adobe Portable Document Format
Accepted version
License bundle
Now showing 1 - 1 of 1
Thumbnail Image
2.71 KB
Item-specific license agreed upon to submission