Research and Development on SAT-based Integration of Systematic and Stochastic Search

本研究では，SAT技術を用いて系統的探索と確率的局所探索を統合的かつ効率的に扱うアルゴリズム技法およびソルバーの実現を目指し，研究開発をおこなっている．3年計画の2年目となる2022年度は，国際ソルバー競技会での入賞2件，査読付き国際会議論文2件，国際ワークショップ発表2件，国内学会発表4件の成果を得た．特に，研究テーマ「(C) 特長的なアプリケーションの開発」への取り組みとして，車両装備仕様問題の応用研究を進めた．車両装備仕様とは自動車のカタログに記載されている車種と装備の組合せであり，販売される国や地域の法規や規制，市場の特性，顧客の選好，競合他社，コストなど，様々な要因を考慮した上で決定される．現状では，車両装備仕様の決定には専門知識を持つ技術者の多大な労力が費やされている．そのため，クオリティの高い車両装備仕様決定の自動化・効率化は，自動車メーカーにとって重要な課題の一つである．この車両装備仕様問題を解く ASP 符号化を考案し，日本の自動車メーカーから提供された実データに基づくベンチマークセットを使用して実験を行った．その結果，現実規模の問題に対して，クオリティの高い車両装備仕様を得ることに成功した．

本研究では，SAT技術を用いて系統的探索と確率的局所探索を統合的かつ効率的に扱うアルゴリズム技法およびソルバーの実現を目指し，研究開発をおこなっている．3年計画の2年目となる2022年度は，国際ソルバー競技会での入賞2件，査読付き国際会議論文2件，国際ワークショップ発表2件，国内学会発表4件の成果を得た．特に，研究テーマ「(C) 特長的なアプリケーションの開発」への取り組みとして，車両装備仕様問題の応用研究を進めた．車両装備仕様とは自動車のカタログに記載されている車種と装備の組合せであり，販売される国や地域の法規や規制，市場の特性，顧客の選好，競合他社，コストなど，様々な要因を考慮した上で決定される．現状では，車両装備仕様の決定には専門知識を持つ技術者の多大な労力が費やされている．そのため，クオリティの高い車両装備仕様決定の自動化・効率化は，自動車メーカーにとって重要な課題の一つである．この車両装備仕様問題を解く ASP 符号化を考案し，日本の自動車メーカーから提供された実データに基づくベンチマークセットを使用して実験を行った．その結果，現実規模の問題に対して，クオリティの高い車両装備仕様を得ることに成功した．