[2M4-OS-11b] AIと制約プログラミング

[2M4-OS-11b-02] 解集合プログラミングに基づく組合せ遷移のコスト最適化に関する一考察

〇髙田 和紀¹、山田 悠也¹、番原 睦則¹ (1. 名古屋大学大学院情報学研究科)

キーワード：組合せ遷移、コスト最適化、解集合プログラミング、独立集合遷移問題

組合せ遷移のコスト最適化とは，基となる組合せ問題とその2つの実行可能解が与えられたとき，一方から他方への実行可能解の遷移系列のうち，コスト最適な遷移系列を求める問題である．各遷移は，複数ある遷移制約のうちただ1つを満たす．各遷移制約にはコストが付加されており，遷移系列全体の総コストを最小化(あるいは最大化)することが目的である．

本稿では，解集合プログラミング(ASP)を用いた組合せ遷移のコスト最適化について述べる．まず最初に，組合せ遷移のコスト最適化問題を解くアルゴリズムを提案する．提案アルゴリズムの特長は，遷移回数の上限を適切に更新することで解の最適性を保証できる点である．次に，TJ型とTS型の2つの遷移制約をもつ独立集合遷移のコスト最適化問題を解くASP符号化を提案する．最後に，提案アルゴリズムの評価として，国際組合せ遷移競技会 CoRe Challenge 2022問題集を用いた実験結果を示す．