Encoding selection for solving Hamiltonian cycle problems with ASP

Liu Liu, Miroslaw Truszczynski

Research output: Contribution to journalConference articlepeer-review

4 Scopus citations


It is common for search and optimization problems to have alternative equivalent encodings in ASP. Typically none of them is uniformly better than others when evaluated on broad classes of problem instances. We claim that one can improve the solving ability of ASP by using machine learning techniques to select encodings likely to perform well on a given instance. We substantiate this claim by studying the hamiltonian cycle problem. We propose several equivalent encodings of the problem and several classes of hard instances. We build models to predict the behavior of each encoding, and then show that selecting encodings for a given instance using the learned performance predictors leads to significant performance gains.

Original languageEnglish
Pages (from-to)302-308
Number of pages7
JournalElectronic Proceedings in Theoretical Computer Science, EPTCS
StatePublished - Sep 19 2019
Event35th International Conference on Logic Programming (Technical Communications), ICLP 2019 - Las Cruces, United States
Duration: Sep 20 2019Sep 25 2019

Bibliographical note

Funding Information:
This work was funded by the NSF under the grant IIS-1707371.

Publisher Copyright:
© L. Liu and M. Truszczynski

ASJC Scopus subject areas

  • Software


Dive into the research topics of 'Encoding selection for solving Hamiltonian cycle problems with ASP'. Together they form a unique fingerprint.

Cite this