Eiter, Thomas and Erdem, Esra and Erdoğan, Halit and Fink, Michael
(2013)
*Finding similar/diverse solutions in answer set programming.*
Theory and Practice of Logic Programming, 13
(3).
pp. 303-359.
ISSN 1471-0684 (Print) 1475-3081 (Online)

Official URL: http://dx.doi.org/10.1017/S1471068411000548

## Abstract

For some computational problems (e.g., product configuration, planning, diagnosis, query answering, phylogeny reconstruction), computing a set of similar/diverse solutions may be desirable for better decision-making. With this motivation, we have studied several decision/optimization versions of this problem in the context of Answer set programming (ASP), analyzed their computational complexity, and introduced offline/online methods to compute similar/diverse solutions of such computational problems with respect to a given distance function. All these methods rely on the idea of computing solutions to a problem by means of finding the answer sets for an ASP program that describes the problem. The offline methods compute all solutions of a problem in advance using the ASP formulation of the problem with an existing ASP solver, like clasp, and then identify similar/diverse solutions using some clustering methods (possibly in ASP as well). The online methods compute similar/diverse solutions of a problem following one of the three approaches: by reformulating the ASP representation of the problem to compute similar/diverse solutions at once using an existing ASP solver; by computing similar/diverse solutions iteratively (one after the other) using an existing ASP solver; by modifying the search algorithm of an ASP solver to compute similar/diverse solutions incrementally. All these methods are sound; the offline method and the first online method are complete whereas the others are not. We have modified clasp to implement the last online method and called it clasp-nk. In the first two online methods, the given distance function is represented in ASP; in the last one, however, it is implemented in C++. We have shown the applicability and the effectiveness of these methods using clasp or clasp-nk on two sorts of problems with different distance measures: on a real-world problem in phylogenetics (i.e., reconstruction of similar/diverse phylogenies for Indo-European languages), and on several planning problems in a well-known domain (i.e., Blocks World). We have observed that in terms of computational efficiency (both time and space), the last online method outperforms the others; also, it allows us to compute similar/diverse solutions when the distance function cannot be represented in ASP (e.g., due to some mathematical functions not supported by the ASP solvers) but can be easily implemented in C++.

Item Type: | Article |
---|---|

Uncontrolled Keywords: | similar/diverse solutions; answer set programming; similar/diverse phylogenies; similar/diverse plans |

Divisions: | Faculty of Engineering and Natural Sciences > Academic programs > Computer Science & Eng. Faculty of Engineering and Natural Sciences |

Depositing User: | Esra Erdem |

Date Deposited: | 05 Jan 2012 16:28 |

Last Modified: | 30 Jul 2019 16:07 |

URI: | https://research.sabanciuniv.edu/id/eprint/18163 |