Bounded Combinatorial Reconfiguration with Answer Set Programming
We develop an approach called bounded combinatorial reconfiguration for solving combinatorial reconfiguration problems based on Answer Set Programming (ASP). The general task is to study the solution spaces of source combinatorial problems and to decide whether or not there are sequences of feasible solutions that have special properties. The resulting recongo solver covers all metrics of the solver track in the most recent international competition on combinatorial reconfiguration (CoRe Challenge 2022). recongo ranked first in the shortest metric of the single-engine solvers track. In this paper, we present the design and implementation of bounded combinatorial reconfiguration, and present an ASP encoding of the independent set reconfiguration problem that is one of the most studied combinatorial reconfiguration problems. Finally, we present empirical analysis considering all instances of CoRe Challenge 2022.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Dominating Set Reconfiguration with Answer Set Programming
The dominating set reconfiguration problem is defined as determining, for a given dominating set problem and two among its feasible solutions, whether one is reachable from the other via a sequence of feasible solutions …
Evaluate Quantum Combinatorial Optimization for Distribution Network Reconfiguration
This paper aims to implement and evaluate the performance of quantum computing on solving combinatorial optimization problems arising from the operations of the power grid. To this end, we construct a novel mixed integer…
Combinatorial OptimizationSketched Answer Set Programming
Answer Set Programming (ASP) is a powerful modeling formalism for combinatorial problems. However, writing ASP models is not trivial. We propose a novel method, called Sketched Answer Set Programming (SkASP), aiming at s…
Automatic Reconfiguration of Untimed Discrete-Event Systems
This work introduces a general formulation of the reconfiguration problem for untimed discrete-event systems (DES), which can be treated directly by supervisory control theory (SCT). To model the reconfiguration requirem…
Large Neighborhood Prioritized Search for Combinatorial Optimization with Answer Set Programming
We propose Large Neighborhood Prioritized Search (LNPS) for solving combinatorial optimization problems in Answer Set Programming (ASP). LNPS is a metaheuristic that starts with an initial solution and then iteratively t…
Combinatorial Optimization