特許ウォッチ

公開番号2025054857
公報種別公開特許公報(A)
公開日2025-04-08
出願番号2023164045
出願日2023-09-26
発明の名称情報処理プログラム、情報処理方法、および情報処理装置
出願人富士通株式会社,国立大学法人大阪大学
代理人個人
主分類G06N 99/00 20190101AFI20250331BHJP(計算;計数)
要約【課題】0-1整数計画問題を解き易くすること。
【解決手段】情報処理装置100は、0-1整数計画問題110を形成する複数の制約条件のうち、制約条件の総数未満である所定の数の制約条件にのみ出現する変数と、当該変数が出現する所定の数の制約条件とのペア120を特定する。情報処理装置100は、特定したペア120ごとに、ペア120の変数と、ペア120の所定の数の制約条件の少なくともいずれかに出現する他の変数とを対応付ける第1対応情報を、記憶部150に登録する。情報処理装置100は、複数の変数における変数間の関係度に基づいて、複数の変数の少なくともいずれかの変数と、当該いずれかの変数との関係度が一定以上である他の変数とを対応付ける第2対応情報を、記憶部150に登録する。情報処理装置100は、記憶部150を参照して、0-1整数計画問題110の解を探索することにより、0-1整数計画問題110の解を算出する。
【選択図】図1
特許請求の範囲【請求項１】
それぞれ０または１の値を取る複数の変数を含む０－１整数計画問題を形成する、それぞれ前記複数の変数の少なくともいずれかを含む複数の制約条件を取得し、
前記複数の制約条件のうち、制約条件の総数未満である所定の数の制約条件にのみ出現する変数と、当該変数が出現する前記所定の数の制約条件とのペアを特定し、
特定した前記ペアごとに、前記ペアの変数と、前記ペアの前記所定の数の制約条件の少なくともいずれかに出現する他の変数とを対応付ける第１対応情報を、記憶部に登録し、
前記複数の変数における変数間の関係度に基づいて、前記複数の変数の少なくともいずれかの変数と、前記いずれかの変数との関係度が一定以上である他の変数とを対応付ける第２対応情報を、前記記憶部に登録し、
前記記憶部を参照して、前記第１対応情報と前記第２対応情報とに基づいて、前記複数の変数のうち、対応付けられたいずれかの２以上の変数のグループを、値を反転する対象に決定することにより、前記０－１整数計画問題の解を探索する、
処理をコンピュータに実行させることを特徴とする情報処理プログラム。
続きを表示（約 2,800 文字）【請求項２】
前記所定の数は、１である、ことを特徴とする請求項１に記載の情報処理プログラム。
【請求項３】
前記０－１整数計画問題の解は、前記複数の変数のそれぞれの値の組み合わせであって、
前記探索する処理は、
前記複数の変数のうち、対応付けられたいずれかの２以上の変数をそれぞれ含む１以上のグループを決定し、決定した前記１以上のグループのそれぞれに関して、前記０－１整数計画問題の暫定解から、当該グループの値を反転した、前記０－１整数計画問題の解候補を特定し、前記０－１整数計画問題を形成する目的関数に基づいて、特定した前記解候補のうち、前記暫定解よりも、前記目的関数の値を適切な方向に近付けるいずれかの解候補が存在する場合に、前記暫定解を、前記いずれかの解候補で更新する、という一連の処理を、終了条件を満たすまで繰り返し実施することにより、前記０－１整数計画問題の解を探索する、ことを特徴とする請求項２に記載の情報処理プログラム。
【請求項４】
前記一連の処理は、
前記複数の変数のそれぞれに関して、前記０－１整数計画問題の暫定解から、当該変数の値を反転した、前記０－１整数計画問題の第１解候補を特定し、前記目的関数に基づいて、特定した前記第１解候補のうち、前記暫定解よりも、前記目的関数の値を前記適切な方向に近付けるいずれかの第１解候補が存在する場合に、前記暫定解を、前記いずれかの第１解候補で更新する、第１処理を含む、ことを特徴とする請求項３に記載の情報処理プログラム。
【請求項５】
前記一連の処理は、
前記暫定解よりも、前記目的関数の値を前記適切な方向に近付けるいずれかの第１解候補が存在しない場合に、前記複数の変数のうち、対応付けられたいずれかの２つの変数をそれぞれ含む１以上のグループを決定し、決定した前記１以上のグループのそれぞれに関して、前記暫定解から、当該グループの値を反転した、前記０－１整数計画問題の第２解候補を特定し、前記目的関数に基づいて、特定した前記第２解候補のうち、前記暫定解よりも、前記目的関数の値を前記適切な方向に近付けるいずれかの第２解候補が存在する場合に、前記暫定解を、前記いずれかの第２解候補で更新する、第２処理を含む、ことを特徴とする請求項４に記載の情報処理プログラム。
【請求項６】
前記一連の処理は、
前記暫定解よりも、前記目的関数の値を前記適切な方向に近付けるいずれかの第２解候補が存在しない場合に、前記複数の変数のうち、対応付けられたいずれかの３つまたは４つの変数をそれぞれ含む１以上のグループを決定し、決定した前記１以上のグループのそれぞれに関して、前記暫定解から、当該グループの値を反転した、前記０－１整数計画問題の第３解候補を特定し、前記目的関数に基づいて、特定した前記第３解候補のうち、前記暫定解よりも、前記目的関数の値を前記適切な方向に近付けるいずれかの第３解候補が存在する場合に、前記暫定解を、前記いずれかの第３解候補で更新する、第３処理を含む、ことを特徴とする請求項５に記載の情報処理プログラム。
【請求項７】
前記目的関数は、前記複数の制約条件のそれぞれの違反量の低減化を目的とするよう、前記複数の制約条件のそれぞれの違反量に、係数となるパラメータを乗算した積を含み、
前記探索する処理は、
前記係数となるパラメータを前回更新した後から、前記一連の処理を今回実施する前までの間に、前記暫定解を更新し、前記一連の処理を今回実施した際に、前記暫定解を更新しない場合、前記複数の制約条件の少なくともいずれかに乗算する前記係数となるパラメータを、現在の値よりも大きい値に更新してから、前記一連の処理を再び実施する、ことを特徴とする請求項５または６に記載の情報処理プログラム。
【請求項８】
前記探索する処理は、
前記係数となるパラメータを前回更新した後から、前記一連の処理を今回実施する前までの間に、前記暫定解を更新せず、前記一連の処理を今回実施した際にも、前記暫定解を更新しない場合、前記複数の制約条件の少なくともいずれかに乗算する前記係数となるパラメータを、現在の値よりも小さい値に更新してから、前記一連の処理を再び実施する、ことを特徴とする請求項７に記載の情報処理プログラム。
【請求項９】
それぞれ０または１の値を取る複数の変数を含む０－１整数計画問題を形成する、それぞれ前記複数の変数の少なくともいずれかを含む複数の制約条件を取得し、
前記複数の制約条件のうち、制約条件の総数未満である所定の数の制約条件にのみ出現する変数と、当該変数が出現する前記所定の数の制約条件とのペアを特定し、
特定した前記ペアごとに、前記ペアの変数と、前記ペアの前記所定の数の制約条件の少なくともいずれかに出現する他の変数とを対応付ける第１対応情報を、記憶部に登録し、
前記複数の変数における変数間の関係度に基づいて、前記複数の変数の少なくともいずれかの変数と、前記いずれかの変数との関係度が一定以上である他の変数とを対応付ける第２対応情報を、前記記憶部に登録し、
前記記憶部を参照して、前記第１対応情報と前記第２対応情報とに基づいて、前記複数の変数のうち、対応付けられたいずれかの２以上の変数のグループを、値を反転する対象に決定することにより、前記０－１整数計画問題の解を探索する、
処理をコンピュータが実行することを特徴とする情報処理方法。
【請求項１０】
それぞれ０または１の値を取る複数の変数を含む０－１整数計画問題を形成する、それぞれ前記複数の変数の少なくともいずれかを含む複数の制約条件を取得し、
前記複数の制約条件のうち、制約条件の総数未満である所定の数の制約条件にのみ出現する変数と、当該変数が出現する前記所定の数の制約条件とのペアを特定し、
特定した前記ペアごとに、前記ペアの変数と、前記ペアの前記所定の数の制約条件の少なくともいずれかに出現する他の変数とを対応付ける第１対応情報を、記憶部に登録し、
前記複数の変数における変数間の関係度に基づいて、前記複数の変数の少なくともいずれかの変数と、前記いずれかの変数との関係度が一定以上である他の変数とを対応付ける第２対応情報を、前記記憶部に登録し、
前記記憶部を参照して、前記第１対応情報と前記第２対応情報とに基づいて、前記複数の変数のうち、対応付けられたいずれかの２以上の変数のグループを、値を反転する対象に決定することにより、前記０－１整数計画問題の解を探索する、
制御部を有することを特徴とする情報処理装置。

発明の詳細な説明【技術分野】
【０００１】
本発明は、情報処理プログラム、情報処理方法、および情報処理装置に関する。
続きを表示（約 1,900 文字）【背景技術】
【０００２】
従来、それぞれ０または１の値を取る複数の変数を含む０－１整数計画問題を解くメタヒューリスティクスとして、重み付き局所探索法がある。例えば、重み付き局所探索法では、変数間の関係度に基づいて、０－１整数計画問題の解を探索する空間を絞り込みながら、０－１整数計画問題を解くことがある。
【０００３】
先行技術としては、例えば、変数間の関係度に基づいて、０－１整数計画問題の解を探索する空間を絞り込みながら、０－１整数計画問題を解くものがある。
【先行技術文献】
【非特許文献】
【０００４】
Ｕｍｅｔａｎｉ，Ｓｈｕｎｊｉ． “Ｅｘｐｌｏｉｔｉｎｇｖａｒｉａｂｌｅａｓｓｏｃｉａｔｉｏｎｓｔｏｃｏｎｆｉｇｕｒｅｅｆｆｉｃｉｅｎｔｌｏｃａｌｓｅａｒｃｈａｌｇｏｒｉｔｈｍｓｉｎｌａｒｇｅ－ｓｃａｌｅｂｉｎａｒｙｉｎｔｅｇｅｒｐｒｏｇｒａｍｓ．” ＥｕｒｏｐｅａｎＪｏｕｒｎａｌｏｆＯｐｅｒａｔｉｏｎａｌＲｅｓｅａｒｃｈ２６３．１（２０１７）：７２－８１．
【発明の概要】
【発明が解決しようとする課題】
【０００５】
しかしながら、非特許文献１に記載の従来技術では、０－１整数計画問題を解くことが難しい場合がある。例えば、０－１整数計画問題が、１つの制約条件にのみ出現する変数を含む場合には、変数間の関係度に基づいて、０－１整数計画問題の解を探索する空間を適切に絞り込むことができず、０－１整数計画問題を解くことができないことがある。
【０００６】
１つの側面では、本発明は、０－１整数計画問題を解き易くすることを目的とする。
【課題を解決するための手段】
【０００７】
１つの実施態様によれば、それぞれ０または１の値を取る複数の変数を含む０－１整数計画問題を形成する、それぞれ前記複数の変数の少なくともいずれかを含む複数の制約条件を取得し、前記複数の制約条件のうち、制約条件の総数未満である所定の数の制約条件にのみ出現する変数と、当該変数が出現する前記所定の数の制約条件とのペアを特定し、特定した前記ペアごとに、前記ペアの変数と、前記ペアの前記所定の数の制約条件の少なくともいずれかに出現する他の変数とを対応付ける第１対応情報を、記憶部に登録し、前記複数の変数における変数間の関係度に基づいて、前記複数の変数の少なくともいずれかの変数と、前記いずれかの変数との関係度が一定以上である他の変数とを対応付ける第２対応情報を、前記記憶部に登録し、前記記憶部を参照して、前記第１対応情報と前記第２対応情報とに基づいて、前記複数の変数のうち、対応付けられたいずれかの２以上の変数のグループを、値を反転する対象に決定することにより、前記０－１整数計画問題の解を探索する情報処理プログラム、情報処理方法、および情報処理装置が提案される。
【発明の効果】
【０００８】
一態様によれば、０－１整数計画問題を解き易くすることが可能になる。
【図面の簡単な説明】
【０００９】
図１は、実施の形態にかかる情報処理方法の一実施例を示す説明図である。
図２は、情報処理システム２００の一例を示す説明図である。
図３は、情報処理装置１００のハードウェア構成例を示すブロック図である。
図４は、情報処理装置１００の機能的構成例を示すブロック図である。
図５は、情報処理装置１００の動作の一例を示す説明図である。
図６は、情報処理装置１００の動作の具体例を示す説明図である。
図７は、情報処理装置１００の適用例を示す説明図である。
図８は、全体処理手順の一例を示すフローチャートである。
図９は、初期化処理手順の一例を示すフローチャートである。
図１０は、１－ｆｌｉｐ近傍探索処理手順の一例を示すフローチャートである。
図１１は、２－ｆｌｉｐ近傍探索処理手順の一例を示すフローチャートである。
図１２は、（３，４）－ｆｌｉｐ近傍探索処理手順の一例を示すフローチャートである。
図１３は、更新処理手順の一例を示すフローチャートである。
【発明を実施するための形態】
【００１０】
以下に、図面を参照して、本発明にかかる情報処理プログラム、情報処理方法、および情報処理装置の実施の形態を詳細に説明する。
（【００１１】以降は省略されています）

関連特許