@article{EiterEEF11,
  author    = {Thomas Eiter and
               Esra Erdem and
               Halit Erdogan and
               Michael Fink},
  title     = {Finding Similar/Diverse Solutions in Answer Set Programming},
  journal   = {Theory and Practice of Logic Programming (TPLP)},
  year      = {2011},
  note      = {To appear},
  ee        =
{http://journals.cambridge.org/action/displayAbstract?fromPage=online&aid=8419989&fulltextType=RA&fileId=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 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 showed 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++.
}
}

{"_id":{"_str":"51f597c528e84a503b000302"},"__v":20,"authorIDs":["5456f0758b01c81930000081","5457257c2abc8e9f370000e3","54597963b43425b7720005c1","546a3dcdbc7d6a460d001844"],"author_short":["Eiter, T.","Erdem, E.","Erdogan, H.","Fink, M."],"bibbaseid":"eiter-erdem-erdogan-fink-findingsimilardiversesolutionsinanswersetprogramming-2011","bibdata":{"bibtype":"article","type":"article","author":[{"firstnames":["Thomas"],"propositions":[],"lastnames":["Eiter"],"suffixes":[]},{"firstnames":["Esra"],"propositions":[],"lastnames":["Erdem"],"suffixes":[]},{"firstnames":["Halit"],"propositions":[],"lastnames":["Erdogan"],"suffixes":[]},{"firstnames":["Michael"],"propositions":[],"lastnames":["Fink"],"suffixes":[]}],"title":"Finding Similar/Diverse Solutions in Answer Set Programming","journal":"Theory and Practice of Logic Programming (TPLP)","year":"2011","note":"To appear","ee":"http://journals.cambridge.org/action/displayAbstract?fromPage=online&aid=8419989&fulltextType=RA&fileId=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 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 showed 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++. ","bibtex":"@article{EiterEEF11,\n author = {Thomas Eiter and\n Esra Erdem and\n Halit Erdogan and\n Michael Fink},\n title = {Finding Similar/Diverse Solutions in Answer Set Programming},\n journal = {Theory and Practice of Logic Programming (TPLP)},\n year = {2011},\n note = {To appear},\n ee =\n{http://journals.cambridge.org/action/displayAbstract?fromPage=online&aid=8419989&fulltextType=RA&fileId=S1471068411000548},\n abstract = {For some computational problems (e.g., product configuration,\nplanning, diagnosis, query answering, phylogeny reconstruction)\ncomputing a set of similar/diverse solutions may be desirable for\nbetter decision-making. With this motivation, we have studied\nseveral decision/optimization versions of this problem in the\ncontext of Answer Set Programming (ASP), analyzed their\ncomputational complexity, and introduced offline/online methods to\ncompute similar/diverse solutions of such computational problems\nwith respect to a given distance function. All these methods rely on\nthe idea of computing solutions to a problem by means of finding the\nanswer sets for an ASP program that describes the problem. The\noffline methods compute all solutions of a problem in advance using\nthe ASP formulation of the problem with an existing ASP solver, like\nClasp, and then identify similar/diverse solutions using some\nclustering methods (possibly in ASP as well). The online methods\ncompute similar/diverse solutions of a problem following one of the\nthree approaches: by reformulating the ASP representation of the\nproblem to compute similar/diverse solutions at once using an\nexisting ASP solver; by computing similar/diverse solutions\niteratively (one after other) using an existing ASP solver; by\nmodifying the search algorithm of an ASP solver to compute\nsimilar/diverse solutions incrementally. All these methods are\nsound; the offline method and the first online method are complete\nwhereas the others are not. We have modified Clasp to implement\nthe last online method and called it Clasp-NK. In the first two\nonline methods, the given distance function is represented in ASP;\nin the last one however it is implemented in C++. We have showed the\napplicability and the effectiveness of these methods using Clasp\nor Clasp-NK on two sorts of problems with different distance\nmeasures: on a real-world problem in phylogenetics (i.e.,\nreconstruction of similar/diverse phylogenies for Indo-European\nlanguages), and on several planning problems in a well-known domain\n(i.e., Blocks World). We have observed that in terms of\ncomputational efficiency (both time and space) the last online\nmethod outperforms the others; also it allows us to compute\nsimilar/diverse solutions when the distance function cannot be\nrepresented in ASP (e.g., due to some mathematical functions not\nsupported by the ASP solvers) but can be easily implemented in C++.\n}\n}\n\n\n\n","author_short":["Eiter, T.","Erdem, E.","Erdogan, H.","Fink, M."],"key":"EiterEEF11","id":"EiterEEF11","bibbaseid":"eiter-erdem-erdogan-fink-findingsimilardiversesolutionsinanswersetprogramming-2011","role":"author","urls":{"Link":"http://journals.cambridge.org/action/displayAbstract?fromPage=online&aid=8419989&fulltextType=RA&fileId=S1471068411000548"},"downloads":1,"html":""},"bibtype":"article","biburl":"http://cogrobo.sabanciuniv.edu/krrpublicationsnew.bib","downloads":1,"keywords":[],"search_terms":["finding","similar","diverse","solutions","answer","set","programming","eiter","erdem","erdogan","fink"],"title":"Finding Similar/Diverse Solutions in Answer Set Programming","title_words":["finding","similar","diverse","solutions","answer","set","programming"],"year":2011,"dataSources":["tGZRHJKguQssAob5Z"]}