@article{amai11,
  author = {Duygu Cakmak and
               Esra Erdem and
               Halit Erdogan},
  journal = {Annals of Mathematics and Artificial Intelligence (Journal)},
  year = {2011},
  title = {Computing Weighted Solutions in ASP: Representation-Based Method vs. Search-Based Method},
  abstract = {Abstract For some problems with too many solutions, one way to obtain the more desirable
ones is to assign each solution a weight that characterizes its importance quantitatively,
and then compute the solutions whose weights are over (resp. below) a given threshold. For
instance, consider the problem of reconstructing phylogenies to be able to analyze evolutionary
relationships between species. If each phylogeny is assigned a weight that characterizes
the expected groupings with respect to some archeological evidence, then finding a phylogeny
of higher weight over some threshold might be more desirable. This paper studies
problems related to computing weighted solutions in the context of Answer Set Programming
(ASP), and in particular investigates two sorts of methods for computing weighted
solutions: one method suggests modifying the ASP representation of the problem to compute
weighted solutions using an existing ASP solver and the other suggests modifying the
search algorithm of the answer set solver to compute weighted solutions incrementally. We
have applied these methods on two real-world problems: reconstructing weighted phylogenies
for Indo-European languages and for Quercus species. For experiments, we have
used the answer set solver CLASP with the representation-based method; and we have modified
the search algorithm of CLASP (and called it CLASP-W) for the search-based method.
In the representation-based method, a given weight function is represented in ASP; in the
search-based method however it is implemented in C++. We have defined two novel weight
functions for phylogenies that can incorporate domain-specific information about simple
(resp. hierarchical) groupings; the weight function that incorporates information about hierarchical
groupings cannot be represented in ASP due to some mathematical functions not
supported by the ASP solvers. To compare the representation-based method with the searchbased
method, we have experimented with Indo-European languages with the weight measure
that can be represented in ASP. We have observed that the search-based method outperforms
the representation-based method in terms of computational efficiency (both time
and space). To show the applicability and modularity of the search-based method (and thus
CLASP-W), we have experimented with Quercus species considering the other weight function.
We have observed that, for weight functions that cannot be represented in ASP, the
search-based method provides a tool for computing weighted solutions in ASP; and the
search algorithm for CLASP-W does not need any problem/function-specific modifications. 
As for effectiveness, with both approaches, plausible phylogenies among many can be found
without computing all phylogenies and then requiring historical linguists to go over all possible
phylogenies manually; in that sense, our methods contribute to phylogenetics studies
as well.}
}

{"_id":{"_str":"534224d0ecd21cdc070007cc"},"__v":31,"authorIDs":["5456f0758b01c81930000081","54597963b43425b7720005c1","545eb6896aaec20d23000936","5df0b7a08367c8de010000ce","5df87bbedb7d9ddf01000044","5e4957a916841dde01000031","u493trvfaXuB4g9PZ"],"author_short":["Cakmak, D.","Erdem, E.","Erdogan, H."],"bibbaseid":"cakmak-erdem-erdogan-computingweightedsolutionsinasprepresentationbasedmethodvssearchbasedmethod-2011","bibdata":{"bibtype":"article","type":"article","author":[{"firstnames":["Duygu"],"propositions":[],"lastnames":["Cakmak"],"suffixes":[]},{"firstnames":["Esra"],"propositions":[],"lastnames":["Erdem"],"suffixes":[]},{"firstnames":["Halit"],"propositions":[],"lastnames":["Erdogan"],"suffixes":[]}],"journal":"Annals of Mathematics and Artificial Intelligence (Journal)","year":"2011","title":"Computing Weighted Solutions in ASP: Representation-Based Method vs. Search-Based Method","abstract":"Abstract For some problems with too many solutions, one way to obtain the more desirable ones is to assign each solution a weight that characterizes its importance quantitatively, and then compute the solutions whose weights are over (resp. below) a given threshold. For instance, consider the problem of reconstructing phylogenies to be able to analyze evolutionary relationships between species. If each phylogeny is assigned a weight that characterizes the expected groupings with respect to some archeological evidence, then finding a phylogeny of higher weight over some threshold might be more desirable. This paper studies problems related to computing weighted solutions in the context of Answer Set Programming (ASP), and in particular investigates two sorts of methods for computing weighted solutions: one method suggests modifying the ASP representation of the problem to compute weighted solutions using an existing ASP solver and the other suggests modifying the search algorithm of the answer set solver to compute weighted solutions incrementally. We have applied these methods on two real-world problems: reconstructing weighted phylogenies for Indo-European languages and for Quercus species. For experiments, we have used the answer set solver CLASP with the representation-based method; and we have modified the search algorithm of CLASP (and called it CLASP-W) for the search-based method. In the representation-based method, a given weight function is represented in ASP; in the search-based method however it is implemented in C++. We have defined two novel weight functions for phylogenies that can incorporate domain-specific information about simple (resp. hierarchical) groupings; the weight function that incorporates information about hierarchical groupings cannot be represented in ASP due to some mathematical functions not supported by the ASP solvers. To compare the representation-based method with the searchbased method, we have experimented with Indo-European languages with the weight measure that can be represented in ASP. We have observed that the search-based method outperforms the representation-based method in terms of computational efficiency (both time and space). To show the applicability and modularity of the search-based method (and thus CLASP-W), we have experimented with Quercus species considering the other weight function. We have observed that, for weight functions that cannot be represented in ASP, the search-based method provides a tool for computing weighted solutions in ASP; and the search algorithm for CLASP-W does not need any problem/function-specific modifications. As for effectiveness, with both approaches, plausible phylogenies among many can be found without computing all phylogenies and then requiring historical linguists to go over all possible phylogenies manually; in that sense, our methods contribute to phylogenetics studies as well.","bibtex":"@article{amai11,\n author = {Duygu Cakmak and\n Esra Erdem and\n Halit Erdogan},\n journal = {Annals of Mathematics and Artificial Intelligence (Journal)},\n year = {2011},\n title = {Computing Weighted Solutions in ASP: Representation-Based Method vs. Search-Based Method},\n abstract = {Abstract For some problems with too many solutions, one way to obtain the more desirable\nones is to assign each solution a weight that characterizes its importance quantitatively,\nand then compute the solutions whose weights are over (resp. below) a given threshold. For\ninstance, consider the problem of reconstructing phylogenies to be able to analyze evolutionary\nrelationships between species. If each phylogeny is assigned a weight that characterizes\nthe expected groupings with respect to some archeological evidence, then finding a phylogeny\nof higher weight over some threshold might be more desirable. This paper studies\nproblems related to computing weighted solutions in the context of Answer Set Programming\n(ASP), and in particular investigates two sorts of methods for computing weighted\nsolutions: one method suggests modifying the ASP representation of the problem to compute\nweighted solutions using an existing ASP solver and the other suggests modifying the\nsearch algorithm of the answer set solver to compute weighted solutions incrementally. We\nhave applied these methods on two real-world problems: reconstructing weighted phylogenies\nfor Indo-European languages and for Quercus species. For experiments, we have\nused the answer set solver CLASP with the representation-based method; and we have modified\nthe search algorithm of CLASP (and called it CLASP-W) for the search-based method.\nIn the representation-based method, a given weight function is represented in ASP; in the\nsearch-based method however it is implemented in C++. We have defined two novel weight\nfunctions for phylogenies that can incorporate domain-specific information about simple\n(resp. hierarchical) groupings; the weight function that incorporates information about hierarchical\ngroupings cannot be represented in ASP due to some mathematical functions not\nsupported by the ASP solvers. To compare the representation-based method with the searchbased\nmethod, we have experimented with Indo-European languages with the weight measure\nthat can be represented in ASP. We have observed that the search-based method outperforms\nthe representation-based method in terms of computational efficiency (both time\nand space). To show the applicability and modularity of the search-based method (and thus\nCLASP-W), we have experimented with Quercus species considering the other weight function.\nWe have observed that, for weight functions that cannot be represented in ASP, the\nsearch-based method provides a tool for computing weighted solutions in ASP; and the\nsearch algorithm for CLASP-W does not need any problem/function-specific modifications. \nAs for effectiveness, with both approaches, plausible phylogenies among many can be found\nwithout computing all phylogenies and then requiring historical linguists to go over all possible\nphylogenies manually; in that sense, our methods contribute to phylogenetics studies\nas well.}\n}\n\n","author_short":["Cakmak, D.","Erdem, E.","Erdogan, H."],"key":"amai11","id":"amai11","bibbaseid":"cakmak-erdem-erdogan-computingweightedsolutionsinasprepresentationbasedmethodvssearchbasedmethod-2011","role":"author","urls":{},"metadata":{"authorlinks":{}}},"bibtype":"article","biburl":"http://pages.cs.wisc.edu/~halit/papers/haliterdoganpub.bib","downloads":0,"keywords":[],"search_terms":["computing","weighted","solutions","asp","representation","based","method","search","based","method","cakmak","erdem","erdogan"],"title":"Computing Weighted Solutions in ASP: Representation-Based Method vs. Search-Based Method","year":2011,"dataSources":["h6pbJnSkCa6JsKHC7","FnnA3hAZggjATcKDh"]}