Dominating Set Reconfiguration with Answer Set Programming
- URL: http://arxiv.org/abs/2408.07510v1
- Date: Wed, 14 Aug 2024 12:38:12 GMT
- Title: Dominating Set Reconfiguration with Answer Set Programming
- Authors: Masato Kato, Torsten Schaub, Takehide Soh, Naoyuki Tamura, Mutsunori Banbara,
- Abstract summary: We develop an approach to solve the dominating set reconfiguration problem based on Answer Set Programming (ASP)
Our approach relies on a high-level ASP encoding, and both the grounding and solving tasks are delegated to an ASP-based solver.
- Score: 0.5242869847419832
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: 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 subject to a certain adjacency relation. This problem is PSPACE-complete in general. The concept of the dominating set is known to be quite useful for analyzing wireless networks, social networks, and sensor networks. We develop an approach to solve the dominating set reconfiguration problem based on Answer Set Programming (ASP). Our declarative approach relies on a high-level ASP encoding, and both the grounding and solving tasks are delegated to an ASP-based combinatorial reconfiguration solver. To evaluate the effectiveness of our approach, we conduct experiments on a newly created benchmark set.
Related papers
- Learning Multiple Initial Solutions to Optimization Problems [52.9380464408756]
Sequentially solving similar optimization problems under strict runtime constraints is essential for many applications.
We propose learning to predict emphmultiple diverse initial solutions given parameters that define the problem instance.
We find significant and consistent improvement with our method across all evaluation settings and demonstrate that it efficiently scales with the number of initial solutions required.
arXiv Detail & Related papers (2024-11-04T15:17:19Z) - Design Optimization of NOMA Aided Multi-STAR-RIS for Indoor Environments: A Convex Approximation Imitated Reinforcement Learning Approach [51.63921041249406]
Non-orthogonal multiple access (NOMA) enables multiple users to share the same frequency band, and simultaneously transmitting and reflecting reconfigurable intelligent surface (STAR-RIS)
deploying STAR-RIS indoors presents challenges in interference mitigation, power consumption, and real-time configuration.
A novel network architecture utilizing multiple access points (APs), STAR-RISs, and NOMA is proposed for indoor communication.
arXiv Detail & Related papers (2024-06-19T07:17:04Z) - Large Neighborhood Prioritized Search for Combinatorial Optimization with Answer Set Programming [3.759879849096294]
We propose Large Neighborhood Prioritized Search (LNPS) for solving optimization problems in Answer Set Programming (ASP)
LNPS is a metaheuristic that starts with an initial solution and then iteratively tries to find better solutions by alternately destroying and prioritized searching for a current solution.
We present an implementation of LNPS based on ASP. The resulting heulingo solver demonstrates that LNPS can significantly enhance the solving performance of ASP for optimization.
arXiv Detail & Related papers (2024-05-18T14:37:43Z) - Bounded Combinatorial Reconfiguration with Answer Set Programming [6.40603461305679]
We develop an approach called bounded reconfiguration for solving reconfiguration problems based on Answer Set Programming (ASP)
The resulting recongo solver covers all metrics of the solver track in the most recent international competition on reconfiguration (CoRe Challenge 2022)
In this paper, we present the design and implementation of bounded reconfiguration, and present an ASP encoding of the independent set reconfiguration problem that is one of the most studied reconfiguration problems.
arXiv Detail & Related papers (2023-07-20T08:30:56Z) - Conjunctive Query Based Constraint Solving For Feature Model
Configuration [79.14348940034351]
We show how to apply conjunctive queries to solve constraint satisfaction problems.
This approach allows the application of a wide-spread database technology to solve configuration tasks.
arXiv Detail & Related papers (2023-04-26T10:08:07Z) - Learning Proximal Operators to Discover Multiple Optima [66.98045013486794]
We present an end-to-end method to learn the proximal operator across non-family problems.
We show that for weakly-ized objectives and under mild conditions, the method converges globally.
arXiv Detail & Related papers (2022-01-28T05:53:28Z) - Fidelity-Guarantee Entanglement Routing in Quantum Networks [64.49733801962198]
Entanglement routing establishes remote entanglement connection between two arbitrary nodes.
We propose purification-enabled entanglement routing designs to provide fidelity guarantee for multiple Source-Destination (SD) pairs in quantum networks.
arXiv Detail & Related papers (2021-11-15T14:07:22Z) - Neural Learning of One-of-Many Solutions for Combinatorial Problems in
Structured Output Spaces [20.101005623256626]
We argue that being oblivious to the presence of multiple solutions can severely hamper their training ability.
We present a generic learning framework that adapts an existing prediction network for an RL problem to handle solution multiplicity.
arXiv Detail & Related papers (2020-08-27T08:37:01Z) - SUNRISE: A Simple Unified Framework for Ensemble Learning in Deep
Reinforcement Learning [102.78958681141577]
We present SUNRISE, a simple unified ensemble method, which is compatible with various off-policy deep reinforcement learning algorithms.
SUNRISE integrates two key ingredients: (a) ensemble-based weighted Bellman backups, which re-weight target Q-values based on uncertainty estimates from a Q-ensemble, and (b) an inference method that selects actions using the highest upper-confidence bounds for efficient exploration.
arXiv Detail & Related papers (2020-07-09T17:08:44Z) - Constrained Combinatorial Optimization with Reinforcement Learning [0.30938904602244344]
This paper presents a framework to tackle constrained optimization problems using deep Reinforcement Learning (RL)
We extend the Neural Combinatorial Optimization (NCO) theory in order to deal with constraints in its formulation.
In that context, the solution is iteratively constructed based on interactions with the environment.
arXiv Detail & Related papers (2020-06-22T03:13:07Z)
This list is automatically generated from the titles and abstracts of the papers in this site.
This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.