Pat

J-GLOBAL ID：202303002291616915

組合せ最適化装置、組合せ最適化方法、およびプログラム

Inventor： 巴 徳瑪 ,  新井 淳也 ,  八木 哲志 ,  寺本 純司 ,  川上 蒼馬 ,  武笠 陽介 ,  鮑 思雅 ,  戸川 望
Applicant, Patent owner： 日本電信電話株式会社 ,  学校法人早稲田大学
Agent (3)： 中尾 直樹 ,  中村 幸雄 ,  義村 宗洋
Gazette classification：公開公報
Application number (International application number)：2022038002
Publication number (International publication number)：2023132590
Application date： Mar. 11, 2022
Publication date： Sep. 22, 2023
Summary：

【課題】従来よりも制約条件の多い産業上の割当問題を解くことが可能な組合せ最適化装置、組合せ最適化方法およびプログラムを提供する。 【解決手段】組合せ最適化装置は、集合V,E,Sを用い、複数の変数q i,c についてのエネルギー関数H=αH 1 +βH 2 +γH 3 +δH 4 +εH obj を得、エネルギー関数Hが最小となる変数q i,c の値を得、これにより複数の対象v i に複数の要素s c を割り当てる。H 1 は対象v i のそれぞれに要素s c のそれぞれが1個ずつ割り当てられたときに最小となり、H 2 は、組(v i ,v j )のv i およびv j に互いに異なる要素s c が割り当てられたときに最小となり、H 3 は特定の対象v k ∈Vに特定の要素s d が割り当てられたときに最小となり、H 4 は特定の要素s f が予め定められた回数L f 以下しか割り当てられないときに最小となり、H obj は割り当てられない要素s g ∈Sの個数が最大のときに最小となる。 【選択図】図1

Claim (excerpt)：

複数の対象v i に複数の要素s c を割り当てる組合せ最適化装置であって、 Vが前記対象v i の集合であり、Eが前記集合Vに含まれた特定の対象の組(v i ,v j )の集合であり、Sが前記要素s c の集合であり、q i,c が前記対象v i への前記要素s c の割り当てを表す変数であり、 前記集合V,E,Sを用い、複数の変数q i,c についてのエネルギー関数H=αH 1 +βH 2 +γH 3 +δH 4 +εH obj を得るエネルギー関数生成部と、 前記エネルギー関数Hが最小となる前記変数q i,c の値を得る組合せ最適化部と、を有し、 H 1 が、前記対象v i ∈Vのそれぞれに前記要素s c ∈Sのそれぞれが1個ずつ割り当てられたときに最小となる関数であり、 H 2 が、前記組(v i ,v j )∈Eのv i およびv j に互いに異なる前記要素s c ∈Sが割り当てられたときに最小となる関数であり、 H 3 が、予め定められた特定の対象v k ∈Vに予め定められた特定の要素s d ∈Sが割り当てられたときに最小となる関数であり、 H 4 が、予め定められた特定の要素s f ∈Sが予め定められた回数L f 以下しか割り当てられないときに最小となる関数であり、 H obj が、割り当てられない要素s g ∈Sの個数が最大のときに最小となる関数であり、 αおよびβが正の実数係数であり、γ,δ,εが0以上の実数係数であり、γ,δ,εの少なくとも何れかが正である、 組合せ最適化装置。

IPC (1)：

G06N 99/00

FI (1)：

G06N99/00 180