特許ウォッチ

公開番号2025087048
公報種別公開特許公報(A)
公開日2025-06-10
出願番号2023201420
出願日2023-11-29
発明の名称情報処理装置、情報処理システム及び情報処理プログラム
出願人株式会社日立製作所
代理人弁理士法人第一国際特許事務所
主分類G06N 99/00 20190101AFI20250603BHJP(計算;計数)
要約【課題】アニーリング手法の性能を向上させ、制約付きの二次計画問題の解を効率的に求めることが可能な情報処理手段を提供すること。
【解決手段】情報処理装置は、目的関数及び線形制約を有する制約付きの二次計画問題と変換関数とを入力し、制約付きの二次計画問題に基づいて、緩和問題と、線形制約をペナルティ項に置き換えた制約なしの二次計画問題とを生成する問題生成部と、緩和問題を求解することで、双対変数を計算する緩和部と、変換関数及び双対変数に基づいて、制約付きの二次計画問題の線形制約に対応するペナルティ係数を計算するペナルティ管理部と、アニーリング手法を用いて、ペナルティ係数をペナルティ項に適用した制約なしの二次計画問題を求解することで、線形制約を満たす実行可能解を判定するアニーリング計算部とを含む。
【選択図】図2
特許請求の範囲【請求項１】
情報処理装置であって、
プロセッサとメモリとを備え、
前記メモリは、
所定の目的関数及び少なくとも１つの線形制約を有する制約付きの二次計画問題と、所定の変換関数とを入力し、前記制約付きの二次計画問題に基づいて、前記制約付きの二次計画問を緩和した緩和問題と、前記線形制約をペナルティ項に置き換えた制約なしの二次計画問題とを生成する問題生成部と、
前記緩和問題を求解することで、前記緩和問題の実行可能解となる双対変数を計算する緩和部と、
前記変換関数及び前記双対変数に基づいて、前記制約付きの二次計画問題の前記線形制約に対応するペナルティ係数を計算するペナルティ管理部と、
アニーリング手法を用いて、前記ペナルティ係数を前記ペナルティ項に適用した前記制約なしの二次計画問題を求解することで、前記線形制約を満たす解を前記制約付きの二次計画問題の実行可能解として判定するアニーリング計算部、
として前記プロセッサを機能させるための処理命令を含むことを特徴とする情報処理装置。
続きを表示（約 3,000 文字）【請求項２】
前記情報処理装置は、
二次計画問題の実行可能解を含む求解情報を格納する記憶部を更に含み、
前記アニーリング計算部は、
前記制約なしの二次計画問題を求解し、前記線形制約を満たす解を前記制約付きの二次計画問題の第１の実行可能解として判定した場合、
前記第１の実行可能解が所定の中止条件を満たすか否かを判定し、
前記第１の実行可能解が前記中止条件を満たさない場合、
前記第１の実行可能解を前記求解情報として前記記憶部に保存し、
前記問題生成部は、
前記記憶部から、前記求解情報を取得し、
前記求解情報に示される前記第１の実行可能解に基づいた第２の緩和問題を生成し、
前記緩和部は、
前記第２の緩和問題を求解することで、前記第２の緩和問題の実行可能解となる第２の双対変数を計算し、
前記第２の双対変数を前記求解情報として前記記憶部に保存し、
前記ペナルティ管理部は、
前記記憶部から、前記求解情報を取得し、
前記変換関数及び前記求解情報に示される前記第２の双対変数に基づいて、第２のペナルティ係数を計算し、
前記アニーリング計算部は、
前記第２のペナルティ係数を前記ペナルティ項に適用した第２の制約なしの二次計画問題を求解することで、前記線形制約を満たす解を前記制約付きの二次計画問題の第２の実行可能解として判定する、
ことを特徴とする、請求項１に記載の情報処理装置。
【請求項３】
前記緩和部は、
前記第２の緩和問題の実行可能解を前記制約付きの二次計画問題の前記目的関数の値の第１の限界値と判定し、前記求解情報として前記記憶部に保存し、
前記アニーリング計算部は、
前記制約なしの二次計画問題の実行可能解を前記制約付きの二次計画問題の前記目的関数の値の第２の限界値と判定し、前記求解情報として前記記憶部に保存する、
ことを特徴とする、請求項２に記載の情報処理装置。
【請求項４】
前記中止条件は、
前記制約なしの二次計画問題を求解した反復回数に基づく反復閾値、所定の所要処理時間に基づく時間閾値、又は前記第１の限界値及び前記第２の限界値の差分に基づく収束閾値である、
ことを特徴とする、請求項３に記載の情報処理装置。
【請求項５】
前記アニーリング計算部は、
前記制約付きの二次計画問題の前記第２の実行可能解が前記中止条件を満たす場合、
前記制約付きの二次計画問題の前記第２の実行可能解と、前記第１の限界値及び前記第２の限界値とを前記制約付きの二次計画問題の最適解として出力する、
ことを特徴とする、請求項３に記載の情報処理装置。
【請求項６】
前記アニーリング計算部は、
電子回路、光回路、断熱量子計算装置、及び量子ゲートコンピュータのいずれかを用いて構成されている、
ことを特徴とする、請求項１に記載の情報処理装置。
【請求項７】
前記問題生成部は、
前記制約付きの二次計画問題における二次項を線形化し、前記制約付きの二次計画問題における整合性制約を緩和することで、前記緩和問題を生成する、
ことを特徴とする、請求項１に記載の情報処理装置。
【請求項８】
前記問題生成部は、
半正定値計画問題緩和手法を用いて前記緩和問題を生成する、
ことを特徴とする、請求項１に記載の情報処理装置。
【請求項９】
制約付きの二次計画問題を求解する情報処理装置と、
ユーザ端末とが通信ネットワークを介して接続されている情報処理システムであって、
前記情報処理装置は、
プロセッサとメモリとを備え、
前記メモリは、
所定の目的関数及び少なくとも１つの線形制約を有する制約付きの二次計画問題と、所定の変換関数とを入力し、前記制約付きの二次計画問題に基づいて、前記制約付きの二次計画問を緩和した緩和問題と、前記線形制約をペナルティ項に置き換えた制約なしの二次計画問題とを生成する問題生成部と、
前記緩和問題を求解することで、前記緩和問題の実行可能解となる双対変数を計算する緩和部と、
前記変換関数及び前記双対変数に基づいて、前記制約付きの二次計画問題の前記線形制約に対応するペナルティ係数を計算するペナルティ管理部と、
アニーリング手法を用いて、前記ペナルティ係数を前記ペナルティ項に適用した前記制約なしの二次計画問題を求解することで、前記線形制約を満たす解を前記制約付きの二次計画問題の実行可能解として判定するアニーリング計算部、
として前記プロセッサを機能させるための処理命令を含むことを特徴とする情報処理システム。
【請求項１０】
情報処理装置において実行される情報処理プログラムであって、
前記情報処理装置は、
プロセッサとメモリとを備え、
前記メモリは、
所定の目的関数及び少なくとも１つの線形制約を有する制約付きの二次計画問題と、所定の変換関数とを入力する工程と、
前記制約付きの二次計画問題に基づいて、前記制約付きの二次計画問を緩和した緩和問題と、前記線形制約をペナルティ項に置き換えた制約なしの二次計画問題とを生成する工程と、
前記緩和問題を求解することで、前記緩和問題の実行可能解となる双対変数を計算する工程と、
前記変換関数及び前記双対変数に基づいて、前記制約付きの二次計画問題の前記線形制約に対応するペナルティ係数を計算する工程と、
アニーリング手法を用いて、前記ペナルティ係数を前記ペナルティ項に適用した前記制約なしの二次計画問題を求解することで、前記線形制約を満たす解を前記制約付きの二次計画問の第１の実行可能解として判定する工程と、
前記制約付きの二次計画問の前記第１の実行可能解が所定の中止条件を満たすか否かを判定する工程と、
前記制約付きの二次計画問の前記第１の実行可能解が前記中止条件を満たさない場合、
前記第１の実行可能解に基づいた第２の緩和問題を生成する工程と、
前記第２の緩和問題を求解することで、前記第２の緩和問題の実行可能解となる第２の双対変数を計算する工程と、
前記変換関数及び前記第２の双対変数に基づいて、第２のペナルティ係数を計算する工程と、
前記第２のペナルティ係数を前記ペナルティ項に適用した第２の制約なしの二次計画問題を求解することで、前記線形制約を満たす解を前記制約付きの二次計画問の第２の実行可能解として判定する工程と、
前記第２の実行可能解が前記中止条件を満たすか否かを判定する工程と、
前記第２の実行可能解が前記中止条件を満たす場合、
前記第２の実行可能解を前記制約付きの二次計画問題の最適解として出力する工程と、
を前記プロセッサに実行させる処理命令を含むことを特徴とする情報処理プログラム。

発明の詳細な説明【技術分野】
【０００１】
本開示は、情報処理装置、情報処理システム及び情報処理プログラムに関する。
続きを表示（約 1,900 文字）【背景技術】
【０００２】
自然科学、工学、社会科学などの多種多様な分野において、最適化問題は、対象のシステムにおけるエンティティに対する制約やエンティティ間の相互関係を考慮しながら、特定の目的関数が最小又は最大となる状態を解析するために用いられている。
【０００３】
所定のシステムにおいて、制約を満たしながら目的関数を最適化する問題は、「制約付きの最適化問題」と呼ばれている。また、この最適化問題の目的関数を二次関数として記述することができる場合、当該最適化問題は「制約付きの二次計画問題」と呼ばれる。
【０００４】
制約付きの二次計画問題は、目的関数における制約をペナルティ項に置き換えることで、シミュレーティッド・アニーリングや量子アニーリングなどの、いわゆるアニーリング手法によって求解することができる。一般に、このペナルティ項は、事前に決定されるペナルティ係数と、制約に基づいて導出される関数との積から構成される。アニーリング手法を用いて制約を満たしながら目的関数を最適化するためには、適切なペナルティ係数を決定することが、アニーリング手法の性能を影響する重要な課題となっている。
【０００５】
従来から、アニーリング手法を用いて最適化問題を解く手段がいくつか提案されている。
例えば、国際公開２０２２／００３９４３号（特許文献１）には、「解精度保証アニーリング計算装置２０は、組合せ最適化問題をアニーリング方式で求解する第１求解手段２１と、組合せ最適化問題に課されている制約条件が緩和されることによって生成された問題である緩和問題を求解する第２求解手段２２とを備え、第２求解手段２２は、組合せ最適化問題が最小化問題である場合には組合せ最適化問題から生成された緩和問題を求解することによって最小化問題における最小化対象の下界を算出し、組合せ最適化問題が最大化問題である場合には組合せ最適化問題から生成された緩和問題を求解することによって最大化問題における最大化対象の上界を算出する。」技術が記載されている。
【先行技術文献】
【特許文献】
【０００６】
国際公開２０２２／００３９４３号
【発明の概要】
【発明が解決しようとする課題】
【０００７】
特許文献１には、アニーリング手法により組合せ最適化問題を解き、元の問題の一部の制約を緩和した緩和問題を解くことで解の品質を保証する解精度保証アニーリング装置が開示されている。
【０００８】
しかし、特許文献１のような従来の手段では、目的関数における制約に対応するペナルティ項のペナルティ係数は、制約を満たす実行可能解が特定しやすくなるように、事前に任意の大きな値に設定される。
ところが、制約に対応するペナルティ係数を任意の大きな値に設定する場合、実行可能解が特定しやすくなるものの、実行可能解の中に存在する最適解を特定することが困難となり、アニーリング手法の性能が限定されてしまうことがある。
【０００９】
そこで、本開示は、制約付きの二次計画問題の制約を緩和した緩和問題を求解することで得られる双対変数に基づいて、制約なしの二次計画問題のペナルティ項に適用するペナルティ係数を判定することで、アニーリング手法の性能を向上させ、制約付きの二次計画問題の解を効率的に求めることが可能な情報処理手段を提供することを目的とする。
【課題を解決するための手段】
【００１０】
上記の課題を解決するために、代表的な本発明の情報処理装置の１つは、プロセッサとメモリとを備え、前記メモリは、所定の目的関数及び少なくとも１つの線形制約を有する制約付きの二次計画問題と、所定の変換関数とを入力し、前記制約付きの二次計画問題に基づいて、前記制約付きの二次計画問を緩和した緩和問題と、前記線形制約をペナルティ項に置き換えた制約なしの二次計画問題とを生成する問題生成部と、前記緩和問題を求解することで、前記緩和問題の実行可能解となる双対変数を計算する緩和部と、前記変換関数及び前記双対変数に基づいて、前記制約付きの二次計画問題の前記線形制約に対応するペナルティ係数を計算するペナルティ管理部と、アニーリング手法を用いて、前記ペナルティ係数を前記ペナルティ項に適用した前記制約なしの二次計画問題を求解することで、前記線形制約を満たす実行可能解を判定するアニーリング計算部として前記プロセッサを機能させるための処理命令を含む。
【発明の効果】
（【００１１】以降は省略されています）

関連特許