Bounded Combinatorial Reconfiguration with Answer Set Programming

• URL: http://arxiv.org/abs/2307.10688v1
• Date: Thu, 20 Jul 2023 08:30:56 GMT
• Title: Bounded Combinatorial Reconfiguration with Answer Set Programming
• Authors: Yuya Yamada, Mutsunori Banbara, Katsumi Inoue, Torsten Schaub
• Abstract summary: 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.
• Score: 6.40603461305679
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: 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.

Related papers

• A Random-Key Optimizer for Combinatorial Optimization [0.0]
  The Random-Key hubs (RKO) is a versatile and efficient local search method tailored for optimization problems. Using the random-key concept, RKO encodes solutions as vectors of random keys that are subsequently decoded into feasible solutions via problem-specific decoders. The RKO framework is able to combine a plethora of classic metaheuristics, each capable of operating independently or in parallel, with solution sharing facilitated through an elite solution pool.
  arXiv  Detail & Related papers  (2024-11-06T22:23:29Z)
• Dominating Set Reconfiguration with Answer Set Programming [0.5242869847419832]
  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.
  arXiv  Detail & Related papers  (2024-08-14T12:38:12Z)
• Multi-Phase Relaxation Labeling for Square Jigsaw Puzzle Solving [73.58829980121767]
  We present a novel method for solving square jigsaw puzzles based on global optimization. The method is fully automatic, assumes no prior information, and can handle puzzles with known or unknown piece orientation.
  arXiv  Detail & Related papers  (2023-03-26T18:53:51Z)
• Generalizing Math Word Problem Solvers via Solution Diversification [56.2690023011738]
  We design a new training framework for an MWP solver by introducing a solution buffer and a solution discriminator. Our framework is flexibly applicable to a wide setting of fully, semi-weakly and weakly supervised training for all Seq2Seq MWP solvers.
  arXiv  Detail & Related papers  (2022-12-01T19:34:58Z)
• A Model-Oriented Approach for Lifting Symmetries in Answer Set Programming [0.0]
  We introduce a new model-oriented Answer Set Programming that lifts the SBCs of small problem instances into a set of interpretable first-order constraints. After targeting simple problems, we aim to extend our method to be applied also for advanced decision problems.
  arXiv  Detail & Related papers  (2022-08-05T10:50:03Z)
• The Machine Learning for Combinatorial Optimization Competition (ML4CO): Results and Insights [59.93939636422896]
  The ML4CO aims at improving state-of-the-art optimization solvers by replacing key components. The competition featured three challenging tasks: finding the best feasible solution, producing the tightest optimality certificate, and giving an appropriate routing configuration.
  arXiv  Detail & Related papers  (2022-03-04T17:06:00Z)
• 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)
• Combining Deep Learning and Optimization for Security-Constrained Optimal Power Flow [94.24763814458686]
  Security-constrained optimal power flow (SCOPF) is fundamental in power systems. Modeling of APR within the SCOPF problem results in complex large-scale mixed-integer programs. This paper proposes a novel approach that combines deep learning and robust optimization techniques.
  arXiv  Detail & Related papers  (2020-07-14T12:38:21Z)
• 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)
• Competitive Mirror Descent [67.31015611281225]
  Constrained competitive optimization involves multiple agents trying to minimize conflicting objectives, subject to constraints. We propose competitive mirror descent (CMD): a general method for solving such problems based on first order information. As a special case we obtain a novel competitive multiplicative weights algorithm for problems on the positive cone.
  arXiv  Detail & Related papers  (2020-06-17T22:11:35Z)
• A Permutation-Equivariant Neural Network Architecture For Auction Design [49.41561446069114]
  Design of an incentive compatible auction that maximizes expected revenue is a central problem in Auction Design. In this work, we consider auction design problems that have permutationequivariant symmetry and construct a neural architecture that is capable of perfectly recovering the permutationequi optimal mechanism.
  arXiv  Detail & Related papers  (2020-03-02T00:37:36Z)

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.