[2M4-OS-11b] OS-11

[2M4-OS-11b-02] Study on Cost-optimal Combinatorial Reconfiguration with Answer Set Programming

〇Kazuki Takada¹, Yuya Yamada¹, Mutsunori Banbara¹ (1. Graduate School of Informatics, Nagoya University)

Keywords:Combinatorial Reconfiguration, Cost-optimization, Answer Set Programming, Independent Set Reconfiguration Problem

Cost-optimization in combinatorial reconfiguration is the task of finding, for a given combinatorial problem and two among its feasible solutions, a minimum-cost sequence of adjacent feasible solutions from one to another. Each transition must satisfy the exact one of multiple transition constraints.
Each transition constraint has a weight, and
the objective is to minimize the total sum of weights of the sequence.
In this paper, we propose an algorithm for solving
cost-optimization problems in combinatorial reconfiguration
based on Answer Set Programming (ASP).
The resulting recongo_opt solver reads a problem instance and
converts it into ASP facts.
In turn, these facts are combined with an ASP encoding
for problem solving,
which are afterward solved by
efficient ASP solvers, in our case clingo.
We show some experimental results for cost-optimal independent set
reconfiguration on the benchmark set of CoRe Challenge 2022,
which demonstrate the effectiveness of our proposed algorithm.