変数が数十万、制約条件を表す式が数万程度の大規模な最適化問題への対応が可能に

日立は、複雑な制約条件を守りながら大規模な組合せ最適化問題を高速に解くCMOSアニーリング技術を開発しました。本技術では、変数が数十万、制約条件を表す式が数万程度の大規模な最適化問題に対して、大規模な問題の最適化計算に優れたCMOSアニーリングと、制約条件を満たす解の探索に優れた最適化ソルバ*1を統合して現実的な時間で解を導きます。その際に問題を複数の部分に分割し、それぞれを効率的に解く「交互方向乗数法(ADMM)*2」というアルゴリズムを活用することで、計算負荷を分散しながら高精度な最適化を実現しました。これにより、鉄道車両の運用計画や金融ポートフォリオの最適化など、社会インフラや金融分野で求められる複雑な業務計画の効率化・高度化に貢献します。今後、日立は、本技術をCMOSアニーリングクラウドサービス*3に搭載し、また、お客さまとの協創を通じて技術の高度化を進め、さまざまな社会課題の解決や持続可能な社会の実現に貢献していきます。

社会インフラや金融分野では、複雑な制約条件を守りながら、大規模な業務システムを効率よく運用することが求められます。例えば、鉄道車両の運用計画では、ダイヤ改正のたびに、どの車両を使ってどの列車を走らせるか*4を決定する必要があり、車庫の収容数や定期検査のタイミングといった制約条件を満たしつつ、最小限の車両数で効率的な運用計画を作成するには相応の知見と時間を要します。こうした大規模な組合せ最適化問題に対して、日立ではこれまで、膨大な変数の組合せを最適化する技術として、０と１の二値変数だけでなく連続変数*5を用いるCMOSアニーリング技術「relaxed MA」*6を開発し、より柔軟な最適化を実現してきました。しかし、今後さらに複雑化・多様化する制約条件を満たす解を実用的な時間内に求めるためには、新たな技術の開発が必要とされていました。

そこで、日立は、複雑な制約条件を守りながら、大規模な組合せ最適化問題を高速に解くCMOSアニーリング技術を開発しました。具体的には、CMOSアニーリングが大規模な最適化問題のより良い解を探す役割を担い、最適化ソルバがその解の周辺で制約条件を満たす解を探索する計算を繰り返すことにより、実行可能な解を高速に導き出します(図1)。CMOSアニーリングと最適化ソルバの統合には、組合せ最適化問題を分割し、解きやすい部分ごとに条件を満たす解を効率よく求めることが可能な交互方向乗数法(ADMM)を適用しました。これにより、変数が数十万、制約条件を表す式が数万程度の大規模な組合せ最適化問題を高速に解くことが可能となりました。

画像: 図1：制約条件を守りながら大規模な組合せ最適化問題を高速に解くCMOSアニーリング技術 — 図1：制約条件を守りながら大規模な組合せ最適化問題を高速に解くCMOSアニーリング技術

今後、日立は、本技術をCMOSアニーリングクラウドサービスに搭載し、金融や鉄道分野などへの適用をめざすとともに、お客さまとの協創を通じて価値を検証しながら、技術のさらなる高度化を進めていきます。
また、本成果の一部は2025年5月に米国エバンストンで開催されたInternational Workshop on Ising Machines(IISM) 2025において発表しました。

*1: 最適化ソルバ: 数理最適化問題を解決するためのアルゴリズムを実装したソフトウェア。指定したさまざまな制約条件を満たす値の組合せを探索する機能を有する。
*2: 交互方向乗数法(ADMM): 大規模最適化問題に対する解法として複数の求解手法を用いて部分問題を繰り返し交互に解くことで全体問題の実行可能な解を求めるアルゴリズム。エネルギー分野の分散管理システムなど多くの研究報告がある。
*3: CMOSアニーリング　クラウドサービス：金融ソリューション：日立
*4: 「車両」は実際に走る物理的な車体、「列車」はダイヤ上に設定された仮想的な運行単位。実際に運行するには、ダイヤ上に設定されたすべての列車に対して、漏れなく車両を割り当てる必要がある。
*5: 連続変数: 0と1のみをとりうる2値変数とは異なり、0と1の間で32ビットまたは64ビット浮動小数点で表現される値をとりうる変数
*6: 2024年6月6日ニュースリリース小数など連続変数に対応したCMOSアニーリング技術「relaxed MA」を開発