Acquiring local preferences of Weighted Partial MaxSAT
Loading...
Files
Date
2017-11
Authors
Huang, Hong
Climent, Laura
O'Sullivan, Barry
Journal Title
Journal ISSN
Volume Title
Publisher
Institute of Electrical and Electronics Engineers, IEEE
Published Version
Abstract
Many 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.
Description
Keywords
Acquiring preferences , Configuration problems , Weighted Partial MaxSAT , Task analysis , Linear programming , Matrix converters , Heuristic algorithms , Benchmark testing , Mathematical model
Citation
Huang, 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.00163
Link to publisher’s version
Copyright
© 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 works