Finding similar/diverse solutions in answer set programming

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)

Full text not available from this repository. (Request a copy)


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

Actions (login required)

View Item
View Item