Encoding Selection for Solving Hamiltonian Cycle Problems with ASP

Liu Liu, Miroslaw TruszczynskiarXiv 2019 · DOI

TL;DR

This paper tackles the challenge of selecting the most effective "encoding" (program representation) for Answer Set Programming (ASP) problems, specifically the Hamiltonian Cycle problem. By using machine learning to predict which encoding will perform best for a given instance, they achieve significant performance gains over using any single encoding.

What Problem Does This Paper Address?

Answer Set Programming (ASP) is a powerful paradigm for solving complex search and optimization problems. However, a major hurdle is that problems can often be represented by multiple, equivalent ASP programs (encodings). These different encodings can exhibit vastly different performance characteristics on various problem instances. While solver selection and parameter tuning have been extensively studied to improve ASP performance, the problem of selecting the right encoding for a given instance has been largely unexplored. This paper aims to bridge this gap by demonstrating how machine learning can be used to intelligently select encodings, thereby improving the overall solving capabilities of ASP.

Methods

The authors' core contribution is a machine learning-based approach to encoding selection. They first construct several equivalent ASP encodings for the computationally hard Hamiltonian Cycle (HC) problem. To train their models, they generate a dataset of "reasonably hard" HC instances. For each instance, they extract two types of features:

  • Graph Features: These are general characteristics of the graph, such as the number of nodes and edges, and properties related to graph traversal (e.g., depth-first search trees).
  • Encoding-Based Features: These are extracted using a tool called claspre, which analyzes the ASP program itself (both statically and dynamically during a short solving attempt) to capture program-specific characteristics.

With these features, they train three types of regression models: k-nearest neighbors (KNN), decision trees (DT), and random forests (RF). These models learn to predict the performance of each encoding for a given instance. During experimentation, they use these trained models to select the best encoding for each test instance.

Datasets

The paper introduces a dataset of 784 "reasonably hard" Hamiltonian Cycle problem instances. These instances were generated by starting with structured graphs (like grid graphs) that are guaranteed to have a Hamiltonian cycle, and then removing edges randomly until the graph becomes difficult to solve. This process aims to identify instances that fall within the "phase transition" region, known for being computationally challenging. The performance data (solved percentage, average runtime) for each of the six selected encodings on these instances was collected.

Key Insights and Ideas

  • Encodings have complementary strengths: No single encoding consistently outperforms others across all instances. This highlights the need for a selection mechanism.
  • Machine learning can predict encoding performance: By extracting relevant instance features, it's possible to build models that accurately predict which encoding will perform best.
  • Encoding selection offers significant gains: The proposed method, by intelligently selecting encodings, achieves performance close to an "oracle" that always picks the fastest encoding, far surpassing the performance of any individual encoding.
  • Feature engineering is crucial: Both graph-specific and program-specific features are important for building effective prediction models.

Key Results

The paper reports on experiments using six high-performing encodings for the HC problem on 784 hard instances.

  • Individual Encoding Performance: The best individual encoding solved about 84% of instances.
  • Oracle Performance: An "oracle" that always selects the fastest encoding solved 98.7% of instances.
  • Encoding Selection Performance:
    • The Decision Tree (DT) model achieved 96.2% solved instances.
  • The Random Forest (RF) model achieved 93.6% solved instances.
  • The KNN model achieved 92.9% solved instances.

These results show that the machine learning-based encoding selection methods significantly outperform individual encodings and come very close to the performance of the ideal oracle.

Limitations and Future Work

The authors acknowledge that their encoding selection approach, while effective, is still about twice as slow as the optimal oracle. They suggest that improving runtime prediction accuracy by identifying more informative (especially domain-specific) features could help close this gap. Additionally, they propose combining encoding selection with parameter configuration for ASP solvers, as solver parameters can also greatly influence performance. Finally, they suggest automating the generation of high-performing encodings, rather than relying on manual creation.

Summary updated

BibTeX
@misc{liu2019encoding,
  author = {Liu Liu and Miroslaw Truszczynski},
  title = {{Encoding Selection for Solving Hamiltonian Cycle Problems with ASP}},
  year = {2019},
  doi = {10.4204/eptcs.306.35},
}
Figure