A Machine Learning System to Improve the Performance of ASP Solving Based on Encoding Selection

Liu Liu; Mirek Truszczynski; Yuliya Lierler

doi:10.1007/978-3-031-15707-3_32

A Machine Learning System to Improve the Performance of ASP Solving Based on Encoding Selection

Liu Liu
, Mirek Truszczynski
, Yuliya Lierler

Computer Science

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

4 Scopus citations

Abstract

Answer set programming (ASP) has long been used for modeling and solving hard search problems. Experience shows that the performance of ASP tools on different ASP encodings of the same problem may vary greatly from instance to instance and it is rarely the case that one encoding outperforms all others. We describe a system and its implementation that given a set of encodings and a training set of instances, builds performance models for the encodings, predicts the execution time of these encodings on new instances, and uses these predictions to select an encoding for solving.

Original language	English
Title of host publication	Logic Programming and Nonmonotonic Reasoning - 16th International Conference, LPNMR 2022, Proceedings
Editors	Georg Gottlob, Daniela Inclezan, Marco Maratea
Pages	415-428
Number of pages	14
DOIs	https://doi.org/10.1007/978-3-031-15707-3_32
State	Published - 2022
Event	16th International Conference on Logic Programming and Nonmonotonic Reasoning, LPNMR 2022 - Genoa, Italy Duration: Sep 5 2022 → Sep 9 2022

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	13416 LNAI
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	16th International Conference on Logic Programming and Nonmonotonic Reasoning, LPNMR 2022
Country/Territory	Italy
City	Genoa
Period	9/5/22 → 9/9/22

Bibliographical note

Publisher Copyright:
© 2022, The Author(s), under exclusive license to Springer Nature Switzerland AG.

Funding

The authors acknowledge the support of the NSF grant IIS 1707371. support of the NSF grant IIS

Funders	Funder number
U.S. Department of Energy Chinese Academy of Sciences Guangzhou Municipal Science and Technology Project Oak Ridge National Laboratory Extreme Science and Engineering Discovery Environment National Science Foundation National Energy Research Scientific Computing Center National Natural Science Foundation of China	IIS, IIS 1707371
U.S. Department of Energy Chinese Academy of Sciences Guangzhou Municipal Science and Technology Project Oak Ridge National Laboratory Extreme Science and Engineering Discovery Environment National Science Foundation National Energy Research Scientific Computing Center National Natural Science Foundation of China

Keywords

answer set programming
encoding selection
machine learning

ASJC Scopus subject areas

Theoretical Computer Science
General Computer Science

Access to Document

10.1007/978-3-031-15707-3_32

Cite this

Liu, L., Truszczynski, M., & Lierler, Y. (2022). A Machine Learning System to Improve the Performance of ASP Solving Based on Encoding Selection. In G. Gottlob, D. Inclezan, & M. Maratea (Eds.), Logic Programming and Nonmonotonic Reasoning - 16th International Conference, LPNMR 2022, Proceedings (pp. 415-428). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 13416 LNAI). https://doi.org/10.1007/978-3-031-15707-3_32

Liu, Liu ; Truszczynski, Mirek ; Lierler, Yuliya. / A Machine Learning System to Improve the Performance of ASP Solving Based on Encoding Selection. Logic Programming and Nonmonotonic Reasoning - 16th International Conference, LPNMR 2022, Proceedings. editor / Georg Gottlob ; Daniela Inclezan ; Marco Maratea. 2022. pp. 415-428 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{56541971d3064282af690b3d675ba413,

title = "A Machine Learning System to Improve the Performance of ASP Solving Based on Encoding Selection",

abstract = "Answer set programming (ASP) has long been used for modeling and solving hard search problems. Experience shows that the performance of ASP tools on different ASP encodings of the same problem may vary greatly from instance to instance and it is rarely the case that one encoding outperforms all others. We describe a system and its implementation that given a set of encodings and a training set of instances, builds performance models for the encodings, predicts the execution time of these encodings on new instances, and uses these predictions to select an encoding for solving.",

keywords = "answer set programming, encoding selection, machine learning",

author = "Liu Liu and Mirek Truszczynski and Yuliya Lierler",

note = "Publisher Copyright: {\textcopyright} 2022, The Author(s), under exclusive license to Springer Nature Switzerland AG.; 16th International Conference on Logic Programming and Nonmonotonic Reasoning, LPNMR 2022 ; Conference date: 05-09-2022 Through 09-09-2022",

year = "2022",

doi = "10.1007/978-3-031-15707-3\_32",

language = "English",

isbn = "9783031157066",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

pages = "415--428",

editor = "Georg Gottlob and Daniela Inclezan and Marco Maratea",

booktitle = "Logic Programming and Nonmonotonic Reasoning - 16th International Conference, LPNMR 2022, Proceedings",

}

Liu, L, Truszczynski, M & Lierler, Y 2022, A Machine Learning System to Improve the Performance of ASP Solving Based on Encoding Selection. in G Gottlob, D Inclezan & M Maratea (eds), Logic Programming and Nonmonotonic Reasoning - 16th International Conference, LPNMR 2022, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 13416 LNAI, pp. 415-428, 16th International Conference on Logic Programming and Nonmonotonic Reasoning, LPNMR 2022, Genoa, Italy, 9/5/22. https://doi.org/10.1007/978-3-031-15707-3_32

A Machine Learning System to Improve the Performance of ASP Solving Based on Encoding Selection. / Liu, Liu; Truszczynski, Mirek; Lierler, Yuliya.
Logic Programming and Nonmonotonic Reasoning - 16th International Conference, LPNMR 2022, Proceedings. ed. / Georg Gottlob; Daniela Inclezan; Marco Maratea. 2022. p. 415-428 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 13416 LNAI).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - A Machine Learning System to Improve the Performance of ASP Solving Based on Encoding Selection

AU - Liu, Liu

AU - Truszczynski, Mirek

AU - Lierler, Yuliya

PY - 2022

Y1 - 2022

N2 - Answer set programming (ASP) has long been used for modeling and solving hard search problems. Experience shows that the performance of ASP tools on different ASP encodings of the same problem may vary greatly from instance to instance and it is rarely the case that one encoding outperforms all others. We describe a system and its implementation that given a set of encodings and a training set of instances, builds performance models for the encodings, predicts the execution time of these encodings on new instances, and uses these predictions to select an encoding for solving.

AB - Answer set programming (ASP) has long been used for modeling and solving hard search problems. Experience shows that the performance of ASP tools on different ASP encodings of the same problem may vary greatly from instance to instance and it is rarely the case that one encoding outperforms all others. We describe a system and its implementation that given a set of encodings and a training set of instances, builds performance models for the encodings, predicts the execution time of these encodings on new instances, and uses these predictions to select an encoding for solving.

KW - answer set programming

KW - encoding selection

KW - machine learning

UR - https://www.scopus.com/pages/publications/85137987960

UR - https://www.scopus.com/pages/publications/85137987960#tab=citedBy

U2 - 10.1007/978-3-031-15707-3_32

DO - 10.1007/978-3-031-15707-3_32

M3 - Conference contribution

AN - SCOPUS:85137987960

SN - 9783031157066

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 415

EP - 428

BT - Logic Programming and Nonmonotonic Reasoning - 16th International Conference, LPNMR 2022, Proceedings

A2 - Gottlob, Georg

A2 - Inclezan, Daniela

A2 - Maratea, Marco

T2 - 16th International Conference on Logic Programming and Nonmonotonic Reasoning, LPNMR 2022

Y2 - 5 September 2022 through 9 September 2022

ER -

Liu L, Truszczynski M, Lierler Y. A Machine Learning System to Improve the Performance of ASP Solving Based on Encoding Selection. In Gottlob G, Inclezan D, Maratea M, editors, Logic Programming and Nonmonotonic Reasoning - 16th International Conference, LPNMR 2022, Proceedings. 2022. p. 415-428. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-031-15707-3_32