割当問題とは、複数の「仕事」と複数の「作業者」が存在するとき、全体のコストを最小化（または全体の価値を最大化）するように、1対1の最適なペアを決定する数理最適化の問題です。線形計画法で効率よく解ける特徴を持ち、AIの資源配分、タスク割り当て、最適輸送問題などの基礎として広く応用されています。
割当問題とは
割当問題（アサインメント問題）とは、複数の「供給側（人や機械など）」と「需要側（タスクや位置など）」が存在する場合に、1対1の対応関係を作り、総コストが最小（または総利益が最大）となる最適な組み合わせを求める数理最適化の代表的な問題です。
詳しく解説
割当問題は、グラフ理論における「二部マッチング」の重み付きバージョンとして定式化されます。すべての作業者にちょうど1つのタスクが割り当てられ、すべてのタスクにちょうど1人の作業者が割り当てられる状況を前提とします。数理モデルとしては、決定変数が0または1の値をとる整数計画問題（特に0-1整数計画問題）となりますが、その係数行列が「完全単模性」を持つため、線形計画法の緩和問題を解くだけで自動的に整数解が得られるという優れた性質を持ちます。このため、実用的な時間で解くことが可能であり、代表的な解法アルゴリズムとして「ハンガリー法（クーン・ムンカレス法）」や、より大規模な問題に対応できる「ネットワークフローアルゴリズム」が用いされます。AIやデータサイエンスの分野では、マルチエージェントシステムにおけるタスク分配や、画像処理での特徴点マッチング、機械学習における最適輸送の計算などに深く関わっています。
具体例・使われ方
具体的な利用例としては、配送ロボット（エージェント）群に対して、複数の目的地への移動タスクを最も効率的（総移動距離が最小）に割り当てる「マルチエージェントタスク割当」が挙げられます。また、求職者と求人情報を、スキルの適合度（スコア）が最大になるように1対1でマッチングさせる人材配置システムや、工場の製造ラインにおいて、複数の作業機械にそれぞれ最も適した製品加工工程を割り当てる生産計画の最適化などにも応用されています。
似た用語との違い
混同されやすい概念に「輸送問題」や「マッチング問題」があります。輸送問題は割当問題を一般化したものであり、1つの供給地から複数の消費地へ任意の量を輸送することを許容します。これに対し、割当問題は供給量と需要量がすべて「1」に制限された特殊なケースです。マッチング問題はより広い概念で、必ずしも1対1の二部グラフに限定されない組み合わせ全般を指します。また、複数の荷物を容量制限のあるビンに詰める「ビンパッキング問題」とは、個数や容量の制約条件の扱いが異なります。
注意点
割当問題の基本形は「作業者の数」と「タスクの数」が等しく、かつ1対1の対応が必須であるという前提に基づいています。現実の業務では「1人が複数のタスクを兼任する」ことや「タスクごとに必要な人数が異なる」ことが多く、これらは単純な割当問題の枠組みを超えて「一般化割当問題（GAP）」や整数計画問題として定式化し直す必要があります。一般化割当問題はNP困難に分類されるため、ハンガリー法のような効率的なアルゴリズムで厳密解を高速に得ることが難しくなり、近似アルゴリズムやメタヒューリスティクスを用いる必要があります。