Encoding Selection for Solving Hamiltonian Cycle Problems with ASP
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.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Simultaneously Solving Computational Problems Using an Artificial Chemical Reactor
This paper is centered on using chemical reaction as a computational metaphor for simultaneously solving problems. An artificial chemical reactor that can simultaneously solve instances of three unrelated problems was cr…
Finding Hamiltonian cycles with graph neural networks
We train a small message-passing graph neural network to predict Hamiltonian cycles on Erd\H{o}s-R\'enyi random graphs in a critical regime. It outperforms existing hand-crafted heuristics after about 2.5 hours of traini…
GPUGraph Neural NetworkRiemannian Hamiltonian methods for min-max optimization on manifolds
In this paper, we study min-max optimization problems on Riemannian manifolds. We introduce a Riemannian Hamiltonian function, minimization of which serves as a proxy for solving the original min-max problems. Under the …
Riemannian optimizationA Memetic Algorithm To Find a Hamiltonian Cycle in a Hamiltonian Graph
We present a memetic algorithm (\maa) approach for finding a Hamiltonian cycle in a Hamiltonian graph. The \ma is based on a proven approach to the Asymmetric Travelling Salesman Problem (\atspp) that, in this contributi…
High-dimensional Clustering onto Hamiltonian Cycle
Clustering aims to group unlabelled samples based on their similarities. It has become a significant tool for the analysis of high-dimensional data. However, most of the clustering methods merely generate pseudo labels a…
ClusteringDeep ClusteringVocal Bursts Intensity Prediction