Under consideration for publication in Theory and Practice of Logic Programming 1 Finding Similar/Diverse Solutions in Answer Set Programming∗

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 complex-ity, 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 comput-ing 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 for-mulation 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 solu