二次ボトルネック割り当て問題

数学において、二次ボトルネック割り当て問題（QBAP ）は、最適化またはオペレーションズリサーチの分野における基本的な組み合わせ最適化問題の一つであり、施設配置問題の範疇に属する。^{[ 1 ]}

これは、線形ボトルネック割り当て問題が線形割り当て問題と関連しているのと同様に、二次割り当て問題と関連しており、目的関数の「合計」が「最大」に置き換えられています。

この問題は、現実世界における以下の問題をモデル化したものです。

n個の施設とn個の場所があります。場所の各ペアに対して距離が指定され、施設の各ペアに対して重量または流量（例えば、2つの施設間で輸送される物資の量）が指定されます。問題は、距離と対応する流量の積の最大値を最小限に抑えることを目的として、すべての施設を異なる場所に割り当てることです。

この問題はNP困難であり、サイクルのパターンにおける流れと、グラフのエッジには短い距離、非エッジには長い距離を用いることで、ハミルトン閉路問題を定式化するために使用できる。 ^{[ 2 ]}

• ボトルネックとなる巡回セールスマン問題
• グラフ帯域幅の問題