一般化割り当て問題

応用数学において、最大一般化割り当て問題は組み合わせ最適化の問題である。この問題は、タスクとエージェントの両方にサイズがある割り当て問題の一般化である。さらに、各タスクのサイズはエージェントごとに異なる可能性がある。

この問題を最も一般的な形で表すと次のようになります。エージェントとタスクが複数存在します。どのエージェントにも任意のタスクを割り当てることができ、そのタスクによって発生するコストと利益は、エージェントとタスクの割り当てに応じて変動します。さらに、各エージェントには予算があり、割り当てられたタスクのコストの合計はこの予算を超えることはできません。すべてのエージェントが予算を超えず、かつ割り当て全体の利益が最大化されるような割り当てを見つけることが求められます。

すべてのエージェントの予算とすべてのタスクのコストが1に等しいという特殊なケースでは、この問題は割り当て問題に帰着します。すべてのタスクのコストと利益が異なるエージェント間で変化しない場合、この問題は多重ナップサック問題に帰着します。エージェントが1人だけの場合、この問題はナップサック問題に帰着します。

以下では、n種類のアイテムがあります。${\displaystyle a_{1}}$を通して${\displaystyle a_{n}}$そしてm種類のビン${\displaystyle b_{1}}$を通して${\displaystyle b_{m}}$各ビン${\displaystyle b_{i}}$予算に関連している$t_i$ゴミ箱用${\displaystyle b_{i}}$各アイテム${\displaystyle a_{j}}$利益がある${\displaystyle p_{ij}}$そして重さ${\displaystyle w_{ij}}$解決策とは、アイテムからビンへの割り当てのことです。実行可能な解決策とは、各ビンに対して${\displaystyle b_{i}}$割り当てられたアイテムの総重量は最大$t_i$解決策の利益は、各品目と保管場所の割り当てにおける利益の合計です。目標は、実現可能な最大利益となる解決策を見つけることです。

数学的には、一般化割り当て問題は整数計画問題として定式化できる。

${\displaystyle {\begin{aligned}{\text{maximize }}&\sum _{i=1}^{m}\sum _{j=1}^{n}p_{ij}x_{ij}.\\{\text{subject to }}&\sum _{j=1}^{n}w_{ij}x_{ij}\leq t_{i}&&i=1,\ldots ,m;\\&\sum _{i=1}^{m}x_{ij}\leq 1&&j=1,\ldots ,n;\\&x_{ij}\in \{0,1\}&&i=1,\ldots ,m,\quad j=1,\ldots ,n;\end{aligned}}}$

一般化割り当て問題はNP困難である。^{[ 1 ]}しかし、線形計画緩和法によって、${\displaystyle (1-1/e)}$-近似。^{[ 2 ]}

すべてのアイテムをビンに割り当てる必要がない問題の変種については、ナップサック問題の任意のアルゴリズムをGAPの近似アルゴリズムに組み合わせ変換することによってGAPを解くアルゴリズムのファミリーが存在する。^{[ 3 ]}

使用${\displaystyle \alpha }$-ナップサック問題に対する近似アルゴリズムALGでは、(${\displaystyle \alpha +1}$)-残余利益の概念を用いた貪欲法による一般化割り当て問題の近似。このアルゴリズムは反復でスケジュールを構築し、反復中に${\displaystyle j}$廃棄予定品の暫定的な選定${\displaystyle b_{j}}$選択されています。ビンの選択${\displaystyle b_{j}}$アイテムが後の反復処理で他のビン用に再選択される可能性があるため、変更される可能性があります。アイテムの残余利益${\displaystyle x_{i}}$ビン用${\displaystyle b_{j}}$は${\displaystyle p_{ij}}$もし${\displaystyle x_{i}}$他のビンには選択されません、または${\displaystyle p_{ij}}$–${\displaystyle p_{ik}}$もし${\displaystyle x_{i}}$ビンに選択されています${\displaystyle b_{k}}$。

正式には：ベクトルを使用します${\displaystyle T}$アルゴリズム実行中の暫定スケジュールを示す。具体的には、${\displaystyle T[i]=j}$アイテムを意味する${\displaystyle x_{i}}$ビンに予定されています${\displaystyle b_{j}}$そして${\displaystyle T[i]=-1}$アイテム${\displaystyle x_{i}}$スケジュールされていません。反復における残余利益${\displaystyle j}$は、${\displaystyle P_{j}}$、 どこ${\displaystyle P_{j}[i]=p_{ij}}$アイテムの場合${\displaystyle x_{i}}$予定されていません（つまり${\displaystyle T[i]=-1}$） そして${\displaystyle P_{j}[i]=p_{ij}-p_{ik}}$アイテムの場合${\displaystyle x_{i}}$ビンに予定されています${\displaystyle b_{k}}$（つまり）${\displaystyle T[i]=k}$)

正式には：

セット${\displaystyle T[i]=-1{\text{ for }}i=1\ldots n}$

のために${\displaystyle j=1,\ldots ,m}$する：

ビンの解決策を見つけるにはALGに連絡してください${\displaystyle b_{j}}$残余利益関数を使用する${\displaystyle P_{j}}$選択された項目をで表す${\displaystyle S_{j}}$。

アップデート${\displaystyle T}$使用${\displaystyle S_{j}}$つまり、${\displaystyle T[i]=j}$すべての人々のために${\displaystyle i\in S_{j}}$。

• 割り当て問題

• ケラー、ハンス。フェルシー、ウルリッヒ。デイビッド・パイシンガー (2013-03-19)。ナップザックの問題。スプリンガー。ISBN 978-3-540-24777-7。