図1:sCOPがCSPを解く仕組み
図1:sCOPがCSPを解く仕組み

今回 XCSP3 競技会の2部門へ出場し両方で1位という良い成績を収めた CSPソルバー sCOP の一番の特徴は、与えられた CSPをSATと呼ばれるより簡単な表現をもつ問題へと”符号化”して、SATを解くプログラムであるSATソルバーを用いてCSPを解くことです (図1)。さらに、効率の良い順序符号化と呼ばれる符号化方法を用いることで、高性能なCSPソルバーを実現しています。

【今後の展望】
CSPを拡張した問題として、与えられた制約を満たす解の中で最適なもの(最適解)を探索する問題である制約最適化問題 (COP) があります。病院での勤務シフトの作成やスポーツの対戦スケジュール作成など、COP は身近な応用がたくさんある重要な問題です。今後の課題としてsCOPをCOPに対応できるように拡張することが挙げられます。

関連サイト

(情報基盤センター、研究推進課)

受賞発表時の様子
受賞発表時の様子