2005 | OriginalPaper | Buchkapitel
On Solving Soft Temporal Constraints Using SAT Techniques
verfasst von : Hossein M. Sheini, Bart Peintner, Karem A. Sakallah, Martha E. Pollack
Erschienen in: Principles and Practice of Constraint Programming - CP 2005
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
In this paper, we present an algorithm for finding utilitarian optimal solutions to Simple and Disjunctive Temporal Problems with Preferences (STPPs and DTPPs) based on Benders’ decomposition and adopting SAT techniques. In our approach, each temporal constraint is replaced by a Boolean
indicator
variable and the decomposed problem is solved by a tightly integrated STP solver and SAT solver. Several hybridization techniques that take advantage of each solver’s strengths are introduced. Finally, empirical evidence is presented to demonstrate the effectiveness of our method compared to other algorithms.