特許ウォッチ

公開番号2025112962
公報種別公開特許公報(A)
公開日2025-08-01
出願番号2024007549
出願日2024-01-22
発明の名称最適化システム、最適化方法及び最適化プログラム
出願人日立ヴァンタラ株式会社
代理人青稜弁理士法人
主分類G06N 99/00 20190101AFI20250725BHJP(計算;計数)
要約【課題】最適化システムにおいて、複雑な論理制約を含む二値二次最適化問題を制約の破れなしに解く。
【解決手段】アニーリング部は第1のソルバを用いて制約充足解の近傍で目的関数値を下げようにアニーリング解の第1の探索を行い、制約論理部は第2のソルバを用いてアニーリング部で得られたアニーリング解の近傍で制約充足解の第2の探索を行い、第1の探索と第2の探索の繰り返し処理を実行して最適解を得る。
【選択図】図2
特許請求の範囲【請求項１】
制約条件を伴う混合２値２次計画問題の最適解を探索する最適化システムであって、
前記混合２値２次計画問題の目的関数の値を下げるアニーリング解の第１の探索を行うアニーリング部と、
前記制約条件を充足する制約充足解の第２の探索を行う制約論理部と、を有し、
前記アニーリング部は、
第１のソルバを用いて、前記制約充足解の近傍で前記目的関数値を下げるように前記アニーリング解の前記第１の探索を行い、
前記制約論理部は、
第２のソルバを用いて、前記アニーリング部で得られた前記アニーリング解の近傍で前記制約充足解の前記第２の探索を行い、
前記第１の探索と前記第２の探索の繰り返し処理を実行して前記最適解を得ることを特徴とする最適化システム。
続きを表示（約 1,900 文字）【請求項２】
前記制約論理部は、
前記第２のソルバとして、前記目的関数の値を最小化する機能を有するアルゴリズムに則って動作するＳＡＴ型制約充足ソルバを用いて、前記第２の探索を行うことを特徴とする請求項１に記載の最適化システム。
【請求項３】
前記制約論理部は、
予め指定した個数の前記制約充足解を発見した場合に、前記第２の探索を終了することを特徴とする請求項１に記載の最適化システム。
【請求項４】
前記制約論理部は、
予め指定した解探索時間が経過した場合に、前記第２の探索を終了することを特徴とする請求項１に記載の最適化システム。
【請求項５】
問題入力部、問題分割部、パラメータ更新部、終了条件判定部、出力部を更に有し、
前記問題入力部は、
前記混合２値２次計画問題を入力し、
前記問題分割部は、
前記問題入力部で入力された前記混合２値２次計画問題を前記アニーリング部で解くべきＱＵＢＯ式と、前記制約論理部で解くべき制約式に分割して出力し、
前記アニーリング部は、
前記ＱＵＢＯ式を用いて、前記アニーリング解の前記第１の探索を行い、
前記制約論理部は、
前記制約式を用いて、前記制約充足解の前記第２の探索を行い、
前記パラメータ更新部は、
所定のパラメータを更新して前記アニーリング部および前記制約論理部へフィードバックし、
前記終了条件判定部は、
前記パラメータ更新部の結果に基づいて、前記第１の探索と前記第２の探索の前記繰り返し処理を終了するかを所定の終了条件に基づいて判定し、
前記所定の終了条件に基づいて、前記繰り返し処理を終了しないと判定した場合、前記アニーリング部での前記第１の探索及び前記制約論理部での前記第２の探索の前記繰り返し処理を実行し、
前記所定の終了条件に基づいて、前記繰り返し処理を終了すると判定した場合、前記最適解を前記出力部に出力することを特徴とする請求項１に記載の最適化システム。
【請求項６】
前記問題入力部は、
前記混合２値２次計画問題を、前記目的関数と、前記制約式と、前記制約式に基づくペナルティ項とを含んだ第１の変数ベクトル及び第２の変数ベクトルを変数とする拡張ラグランジュ関数に変換する変換処理を実行し、
前記問題分割部は、
前記目的関数と前記ペナルティ項を前記ＱＵＢＯ式に変換して前記アニーリング部に送信し、前記制約式を前記制約論理部に送信し、
前記アニーリング部は、
交互方向乗数法における前記拡張ラグランジュ関数を最適化する前記第１の変数ベクトルの最適解の探索を前記混合２値２次計画問題の所定の最適化アルゴリズムを用いて行い、
前記制約論理部は、
前記交互方向乗数法における前記拡張ラグランジュ関数を最適化する前記第２の変数ベクトルの最適解の探索を、前記制約式を満たすように前記ＳＡＴ型制約充足ソルバを用いて行い、
前記パラメータ更新部は、
前記拡張ラグランジュ関数の前記パラメータを更新して前記アニーリング部と前記制約論理部にフィードバックすることを特徴とする請求項５に記載の最適化システム。
【請求項７】
前記問題分割部は、
前記制約式を不等式制約と論理制約に分割して前記制約論理部に送信することを特徴とする請求項６に記載の最適化システム。
【請求項８】
前記論理制約はチャネル制約を含み、
前記チャネル制約は前記論理制約が満たすべき条件を記述することを特徴とする請求項７に記載の最適化システム。
【請求項９】
前記論理制約は１行で１つの制約を表現するフォーマットを有しており、前記論理制約の関数のＩＤ情報、前記チャネル制約のＩＤ情報、前記チャネル制約に入力する変数の数の情報、前記論理制約及び前記チャネル制約に含まれる変数情報を含んで構成されることを特徴とする請求項７に記載の最適化システム。
【請求項１０】
前記変数情報は、
前記変数の属性、変数に乗ずる係数及び変数を含み、
前記変数の属性は、
前記変数が変数であるか、ＮＯＴ属性を付与した変数であるか、定数であるかを規定し、
前記変数は、
前記変数の属性に対応した変数か、前記ＮＯＴ属性が付与された変数か、前記定数のいずれかを表すことを特徴とする請求項９に記載の最適化システム。
（【請求項１１】以降は省略されています）
発明の詳細な説明【技術分野】
【０００１】
本発明は、最適化システム、最適化方法及び最適化プログラムに関する。
続きを表示（約 1,300 文字）【背景技術】
【０００２】
近年、組合せ最適化問題を解くための疑似量子計算技術であるＣＭＯＳ（ＣｏｍｐｌｅｍｅｎｔａｒｙＭｅｔａｌＯｘｉｄｅＳｅｍｉｃｏｎｄｕｃｔｏｒ）アニーリングが注目されている。
【０００３】
ＣＭＯＳアニーリングは最適化問題をイジングモデルで表現し、この基底状態をアニーリングという手法で探索する。実社会の問題をアニーリングにより解こうとするとき、様々な制約条件を充足しなければならないことがある。このような場合、制約条件は２次以下のペナルティ項としてイジングモデルの目的関数として組み込むことで目的関数値を下げる過程で充足を目指すという方法を取るのが一般的に知られている。
【０００４】
しかし、上記の方法では制約条件の充足は保証されておらず、制約条件が破れた解が導出されることがある。これは制約条件が破れた場合にペナルティを課すという方法ではできる限り制約を守ろうとするものの、必ず制約条件を満たす解空間のみを探索する、ということではないためである。
【０００５】
ペナルティ項の目的関数における寄与を大きくすることで出来るだけ充足する方法が知られている。これは上記ペナルティ項の係数を大きくすることで実現できるが、制約充足を優先するために上記ペナルティ項の係数を大きくしすぎると目的関数の値が良くならず最適解か、もしくはこれに近い解を得ることが難しくなる。一方で、上記ペナルティ項の重みを小さくすると制約が破れるため、係数の調整が難しいという課題があった。
【０００６】
これに対して、アニーリングにおいて線形不等式制約を充足する技術としてＡＤＭＭ（交互方向乗数法）を用いた解法が特許文献１に提案されている。
【０００７】
特許文献１には、ラグランジュ関数法を用いてアニーリングとＨｉｌｄｒｅｔｈアルゴリズムを組み込んだＡＤＭＭにより、線形不等式制約をＨｉｌｄｒｅｔｈアルゴリズムで処理することで制約を充足する混合２値２次計画問題を解く手法が記載されている。
【先行技術文献】
【特許文献】
【０００８】
特開１３３－１２１０４６号公報
【発明の概要】
【発明が解決しようとする課題】
【０００９】
しかし、特許文献１はＨｉｌｄｒｅｔｈアルゴリズムで線形不等式制約を満たしながら解を探索する手法であったが、論理制約やある条件が満たされる場合にのみ適用される制約など、線形不等式制約では表現が難しい制約条件を満たすことが困難であった。また混合２値２次計画問題において複雑な制約を充足しつつ求解するには、特許文献１に示される連続最適化では時間が掛かりすぎて求解が遅くなる問題があった。
【００１０】
本発明の目的は、最適化システムにおいて、複雑な論理制約を含む二値二次最適化問題を制約の破れなしに解くことを目的とする。
【課題を解決するための手段】
（【００１１】以降は省略されています）

関連特許