課題

よく知られている組み合わせ最適化問題の一つは、割り当て問題です。たとえば、ワーカーのグループが一連のタスクを実行する必要があり、ワーカーとタスクごとにワーカーをタスクに割り当てるためのコストが発生するとします。問題は、総コストを最小限に抑えながら、各ワーカーを最大 1 つのタスクに割り当て、同じタスクを実行する 2 つのワーカーがないことです。

下のグラフでこの問題を視覚化できます。ここには、4 つのワーカーと 4 つのタスクがあります。エッジは、ワーカーをタスクに割り当てる際に使用できるすべての方法を表します。端のラベルは、ワーカーをタスクに割り当てるコストを表します。

割り当てはエッジのサブセットとなり、各ワーカーには少なくとも 1 つのエッジがあり、2 つのワーカーが同じタスクにつながるエッジはありません。考えられる割り当ての 1 つを以下に示します。

課題の総費用は 70 + 55 + 95 + 45 = 265 です。

次のセクションでは、MIP ソルバーと CP-SAT ソルバーの両方を使用して、割り当て問題を解く方法について説明します。

課題の問題を解決するその他のツール

OR-Tools には、割り当ての問題を解決するツールが他に 2 つあります。これらのツールは、MIP や CP のソルバーよりも高速です。

• 線形和の割り当て解法
• 最小コストのフロー ソルバー

ただし、これらのツールで解決できる課題は、単純なものに限られます。そのため、さまざまな問題を処理できる（そしてほとんどのアプリケーションで十分な速度）一般的なソルバーには、MIP ソルバーと CP-SAT ソルバーをおすすめします。