特許ウォッチ

公開番号2025045980
公報種別公開特許公報(A)
公開日2025-04-02
出願番号2023154091
出願日2023-09-21
発明の名称組合せ最適化問題求解装置および組合せ最適化問題求解方法
出願人日本電気株式会社
代理人個人,個人
主分類G06N 99/00 20190101AFI20250326BHJP(計算;計数)
要約【課題】組合せ最適化問題の解の候補をより高速に求めることができる組合せ最適化問題求解装置を提供する。
【解決手段】組合せ最適化問題求解装置20は、組合せ最適化問題に課せられた1つ以上の制約のうち所定の条件を満たす制約である無変換制約以外の制約が変換されたCNFの形式で表されたSATを、無変換制約が満たされるように求解することによって、組合せ最適化問題の解の候補であって1つ以上の制約を満たす組合せ最適化問題の複数の変数の値の組を求める求解部21を備える。
【選択図】図14
特許請求の範囲【請求項１】
組合せ最適化問題に課せられた１つ以上の制約のうち所定の条件を満たす制約である無変換制約以外の制約が変換されたCNF(Conjunctive Normal Form)の形式で表されたSAT(Boolean Satisfiability Testing)を、前記無変換制約が満たされるように求解することによって、前記組合せ最適化問題の解の候補であって前記１つ以上の制約を満たす前記組合せ最適化問題の複数の変数の値の組を求める求解部を備える
ことを特徴とする組合せ最適化問題求解装置。
続きを表示（約 1,200 文字）【請求項２】
求解部は、
SATを求解することによって解の暫定候補を求めるソルバと、
求められた解の暫定候補が無変換制約を満たすか否かを判定する判定部とを含む
請求項１記載の組合せ最適化問題求解装置。
【請求項３】
CNFは、
１つ以上の変数が結合した１つ以上の節で構成され、
判定部は、
求められた解の暫定候補が無変換制約を満たさない場合、前記解の暫定候補の前記無変換制約を満たさない変数を用いて節を生成し、
ソルバは、
生成された節を用いて再度SATを求解する
請求項２記載の組合せ最適化問題求解装置。
【請求項４】
判定部は、
求められた解の暫定候補が無変換制約を満たす場合、前記解の暫定候補の値が未確定な変数の中で、前記無変換制約を基に値が確定可能な変数を特定し、
特定された変数を用いて節を生成し、
ソルバは、
生成された節を用いて再度SATを求解する
請求項３記載の組合せ最適化問題求解装置。
【請求項５】
ソルバは、シミュレーテッドアニーリング方式でSATを求解する
請求項２から請求項４のうちのいずれか１項に記載の組合せ最適化問題求解装置。
【請求項６】
無変換制約が変換されたCNFの形式で表されたSATの求解に要する時間は、前記無変換制約以外の制約が変換されたCNFの形式で表されたSATの求解に要する時間よりも長い
請求項１記載の組合せ最適化問題求解装置。
【請求項７】
無変換制約は、One Hot制約またはWeighted Sum制約である
請求項６記載の組合せ最適化問題求解装置。
【請求項８】
組合せ最適化問題に課せられた１つ以上の制約のうち所定の条件を満たす制約である無変換制約以外の制約が変換されたCNF(Conjunctive Normal Form)の形式で表されたSAT(Boolean Satisfiability Testing)を、前記無変換制約が満たされるように求解することによって、前記組合せ最適化問題の解の候補であって前記１つ以上の制約を満たす前記組合せ最適化問題の複数の変数の値の組を求める
ことを特徴とする組合せ最適化問題求解方法。
【請求項９】
コンピュータに、
組合せ最適化問題に課せられた１つ以上の制約のうち所定の条件を満たす制約である無変換制約以外の制約が変換されたCNF(Conjunctive Normal Form)の形式で表されたSAT(Boolean Satisfiability Testing)を、前記無変換制約が満たされるように求解することによって、前記組合せ最適化問題の解の候補であって前記１つ以上の制約を満たす前記組合せ最適化問題の複数の変数の値の組を求める求解処理
を実行させるための組合せ最適化問題求解プログラム。

発明の詳細な説明【技術分野】
【０００１】
本開示は、組合せ最適化問題求解装置、組合せ最適化問題求解方法および組合せ最適化問題求解プログラムに関する。特に、本開示は、疑似量子アニーリングと呼ばれる組合せ最適化ソルバの高速化を実現する組合せ最適化問題求解装置、組合せ最適化問題求解方法および組合せ最適化問題求解プログラムに関する。
続きを表示（約 970 文字）【背景技術】
【０００２】
組合せ最適化問題を量子アニーリング方式で高速に求解可能な量子コンピュータの研究が進められている。量子コンピュータは、組合せ最適化問題をイジングモデルで表し、量子重ね合わせを利用して、組合せ最適化問題の目的関数に相当するエネルギー関数を最小にする状態を探索する。
【０００３】
量子コンピュータは、イジングモデルにおけるエネルギー関数を入力として、組合せ最適化問題を解く。なお、組合せ最適化問題の例として、巡回セールスマン問題、ナップサック問題、グラフ分割問題、ナースシフトスケジューリング問題が挙げられる。また、組合せ最適化問題は、他の問題でもよい。
【０００４】
イジングモデルは、磁性体のスピンの振る舞いを表す統計力学上のモデルである。イジングモデルでは、個々のスピンの状態は、“１”または“－１”で表される。
【０００５】
組合せ最適化問題が求解される際、イジングモデルにおけるエネルギー関数が小さくなるようにスピンの向きが変化する。イジングモデルにおけるエネルギー関数は、以下の式（１）のように表される。
【０００６】
TIFF
2025045980000002.tif
15
144
【０００７】
式（１）におけるs
i
，s
j
は、スピンの状態を表す変数である。また、J
ij
は、i，jに応じた定数である。また、h
i
は、iに応じた定数である。
【０００８】
また、個々のスピンの状態を“１”または“０”で表すモデルとして、QUBO(Quadratic Unconstrained Binary Optimization)も知られている。イジングモデルにおけるエネルギー関数と、QUBOにおけるエネルギー関数とは、相互に変換可能である。
【０００９】
QUBOにおけるエネルギー関数は、以下の式（２）のように表される。
【００１０】
TIFF
2025045980000003.tif
17
141
（【００１１】以降は省略されています）

関連特許