課題
コレクションでコンテンツを整理
必要に応じて、コンテンツの保存と分類を行います。
よく知られている組み合わせ最適化問題の一つは、割り当て問題です。たとえば、ワーカーのグループが一連のタスクを実行する必要があり、ワーカーとタスクごとにワーカーをタスクに割り当てるためのコストが発生するとします。問題は、総コストを最小限に抑えながら、各ワーカーを最大 1 つのタスクに割り当て、同じタスクを実行する 2 つのワーカーがないことです。
下のグラフでこの問題を視覚化できます。ここには、4 つのワーカーと 4 つのタスクがあります。エッジは、ワーカーをタスクに割り当てる際に使用できるすべての方法を表します。端のラベルは、ワーカーをタスクに割り当てるコストを表します。
割り当てはエッジのサブセットとなり、各ワーカーには少なくとも 1 つのエッジがあり、2 つのワーカーが同じタスクにつながるエッジはありません。考えられる割り当ての 1 つを以下に示します。
課題の総費用は 70 + 55 + 95 + 45 = 265 です。
次のセクションでは、MIP ソルバーと CP-SAT ソルバーの両方を使用して、割り当て問題を解く方法について説明します。
OR-Tools には、割り当ての問題を解決するツールが他に 2 つあります。これらのツールは、MIP や CP のソルバーよりも高速です。
ただし、これらのツールで解決できる課題は、単純なものに限られます。そのため、さまざまな問題を処理できる（そしてほとんどのアプリケーションで十分な速度）一般的なソルバーには、MIP ソルバーと CP-SAT ソルバーをおすすめします。
特に記載のない限り、このページのコンテンツはクリエイティブ・コモンズの表示 4.0 ライセンスにより使用許諾されます。コードサンプルは Apache 2.0 ライセンスにより使用許諾されます。詳しくは、Google Developers サイトのポリシーをご覧ください。Java は Oracle および関連会社の登録商標です。
最終更新日 2024-08-09 UTC。
[null,null,["最終更新日 2024-08-09 UTC。"],[[["\u003cp\u003eThe assignment problem focuses on optimally assigning workers to tasks to minimize the total cost, where each worker is assigned at most one task and no task is assigned to multiple workers.\u003c/p\u003e\n"],["\u003cp\u003eThis problem can be visualized using a graph where edges represent worker-task assignments and edge labels represent the cost of each assignment.\u003c/p\u003e\n"],["\u003cp\u003eOR-Tools offers various solvers like MIP, CP-SAT, Linear Sum Assignment, and Minimum Cost Flow, but MIP and CP-SAT are recommended for their versatility and efficiency in handling a broader range of assignment problems.\u003c/p\u003e\n"]]],["The content describes the assignment problem, a combinatorial optimization challenge where workers are assigned to tasks to minimize total cost. Each worker is assigned to at most one task, and each task is done by at most one worker. The example shows how the problem can be represented graphically, with edges representing possible assignments and their costs. The total cost is calculated by adding up the costs of the assigned edges. OR-Tools offer multiple tools to solve such problems, among which the MIP and CP-SAT are the most general.\n"],null,["# Assignment\n\nOne of the most well-known combinatorial optimization problems is the\n[*assignment problem*](https://en.wikipedia.org/wiki/Assignment_problem). Here's an example: suppose a group of workers needs to perform a set of tasks, and for\neach worker and task, there is a cost for assigning the worker to the task.\nThe problem is to assign each worker to at most one task, with no two workers\nperforming the same task, while minimizing the total cost.\n\nYou can visualize this problem by the graph below, in which there are four\nworkers and four tasks. The edges represent all possible ways to assign workers\nto tasks. The labels on the edges are the costs of assigning workers to tasks.\n\nAn assignment corresponds to a subset of the edges, in which each worker has at\nmost one edge leading out, and no two workers have edges leading to the same\ntask. One possible assignment is shown below.\n\nThe total cost of the assignment is `70 + 55 + 95 + 45 = 265`.\n\nThe [next section](/optimization/assignment/assignment_example) shows how solve\nan assignment problem, using both the MIP solver and the CP-SAT solver.\n\n### Other tools for solving assignment problems\n\nOR-Tools also provides a couple of other tools for solving assignment problems,\nwhich can be faster than the MIP or CP solvers:\n\n- [Linear sum assignment solver](/optimization/assignment/linear_assignment)\n- [Minimum cost flow solver](/optimization/flow/assignment_min_cost_flow)\n\nHowever, these tools can only solve simple types of assignment problems.\nSo for general solvers that can handle a wide variety of problems (and are fast\nenough for most applications), we recommend the MIP and CP-SAT solvers."]]
