Weighted-sequence problem: ASP vs CASP and declarative vs problem oriented solving

Yuliya Lierler; Shaden Smith; Miroslaw Truszczynski; Alex Westlund

Weighted-sequence problem: ASP vs CASP and declarative vs problem oriented solving

Yuliya Lierler, Shaden Smith, Miroslaw Truszczynski, Alex Westlund

Computer Science

Research output: Contribution to conference › Paper › peer-review

Abstract

We define the weighted-sequence problem inspired by an important industrial problem in oracle query optimization. We evaluate several approaches to solving this problem using answer set programming (ASP) system clingo and constraint answer set programming (CASP) solver clingcon. The focus of this paper is an experimental evaluation of search procedures behind clingo and clingcon. We used instances of the weighted-sequence problem where integer parameters were quite small so that grounding was not an issue and we could focus on comparison of the effectiveness of the clingo and clingcon solvers. Our key finding is that the effectiveness of the search procedure used by clingcon lags behind that of clingo. It points to the need for further research on the integration of ASP and CSP technologies.

Original language	English
State	Published - 2011
Event	4th Workshop on Answer Set Programming and Other Computing Paradigms, ASPOCP 2011, collocated with the 27th International Conference on Logic Programming, ICLP 2011 - Lexington, United States Duration: Jul 10 2011 → …

Conference

Conference	4th Workshop on Answer Set Programming and Other Computing Paradigms, ASPOCP 2011, collocated with the 27th International Conference on Logic Programming, ICLP 2011
Country/Territory	United States
City	Lexington
Period	7/10/11 → …

Bibliographical note

Publisher Copyright:
© 2011 Computing Research Repository (CoRR). All rights reserved.

Funding

We are grateful to Philip Cannata for bringing the problem of finding an optimal join order in query optimization to our attention, and to Vladimir Lifschitz and Yuanlin Zhang for useful discussions related to the topic of this work. Yuliya Lierler was supported by a CRA/NSF 2010 Computing Innovation Fellowship, Miroslaw Truszczynski by the NSF grant IIS-0913459, and Shaden Smith and Alex Westlund by the NSF REU Supplement to that grant.

Funders	Funder number
CRA/NSF
National Science Foundation (NSF)	IIS-0913459

ASJC Scopus subject areas

Theoretical Computer Science
Computational Theory and Mathematics
Software
Hardware and Architecture
Artificial Intelligence

Cite this

@conference{b1f94fdb38964d0eb884e32942aaec05,

title = "Weighted-sequence problem: ASP vs CASP and declarative vs problem oriented solving",

abstract = "We define the weighted-sequence problem inspired by an important industrial problem in oracle query optimization. We evaluate several approaches to solving this problem using answer set programming (ASP) system clingo and constraint answer set programming (CASP) solver clingcon. The focus of this paper is an experimental evaluation of search procedures behind clingo and clingcon. We used instances of the weighted-sequence problem where integer parameters were quite small so that grounding was not an issue and we could focus on comparison of the effectiveness of the clingo and clingcon solvers. Our key finding is that the effectiveness of the search procedure used by clingcon lags behind that of clingo. It points to the need for further research on the integration of ASP and CSP technologies.",

author = "Yuliya Lierler and Shaden Smith and Miroslaw Truszczynski and Alex Westlund",

note = "Publisher Copyright: {\textcopyright} 2011 Computing Research Repository (CoRR). All rights reserved.; 4th Workshop on Answer Set Programming and Other Computing Paradigms, ASPOCP 2011, collocated with the 27th International Conference on Logic Programming, ICLP 2011 ; Conference date: 10-07-2011",

year = "2011",

language = "English",

}

Weighted-sequence problem: ASP vs CASP and declarative vs problem oriented solving. / Lierler, Yuliya; Smith, Shaden; Truszczynski, Miroslaw et al.
2011. Paper presented at 4th Workshop on Answer Set Programming and Other Computing Paradigms, ASPOCP 2011, collocated with the 27th International Conference on Logic Programming, ICLP 2011, Lexington, United States.

Research output: Contribution to conference › Paper › peer-review

TY - CONF

T1 - Weighted-sequence problem

T2 - 4th Workshop on Answer Set Programming and Other Computing Paradigms, ASPOCP 2011, collocated with the 27th International Conference on Logic Programming, ICLP 2011

AU - Lierler, Yuliya

AU - Smith, Shaden

AU - Truszczynski, Miroslaw

AU - Westlund, Alex

PY - 2011

Y1 - 2011

N2 - We define the weighted-sequence problem inspired by an important industrial problem in oracle query optimization. We evaluate several approaches to solving this problem using answer set programming (ASP) system clingo and constraint answer set programming (CASP) solver clingcon. The focus of this paper is an experimental evaluation of search procedures behind clingo and clingcon. We used instances of the weighted-sequence problem where integer parameters were quite small so that grounding was not an issue and we could focus on comparison of the effectiveness of the clingo and clingcon solvers. Our key finding is that the effectiveness of the search procedure used by clingcon lags behind that of clingo. It points to the need for further research on the integration of ASP and CSP technologies.

AB - We define the weighted-sequence problem inspired by an important industrial problem in oracle query optimization. We evaluate several approaches to solving this problem using answer set programming (ASP) system clingo and constraint answer set programming (CASP) solver clingcon. The focus of this paper is an experimental evaluation of search procedures behind clingo and clingcon. We used instances of the weighted-sequence problem where integer parameters were quite small so that grounding was not an issue and we could focus on comparison of the effectiveness of the clingo and clingcon solvers. Our key finding is that the effectiveness of the search procedure used by clingcon lags behind that of clingo. It points to the need for further research on the integration of ASP and CSP technologies.

UR - http://www.scopus.com/inward/record.url?scp=85084012286&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85084012286&partnerID=8YFLogxK

M3 - Paper

AN - SCOPUS:85084012286

Y2 - 10 July 2011

ER -

Weighted-sequence problem: ASP vs CASP and declarative vs problem oriented solving

Abstract

Conference

Bibliographical note

Funding

ASJC Scopus subject areas

Other files and links

Fingerprint

Cite this