할당
컬렉션을 사용해 정리하기
내 환경설정을 기준으로 콘텐츠를 저장하고 분류하세요.
가장 잘 알려진 조합 최적화 문제 중 하나는 할당 문제입니다. 예를 들어 작업자 그룹이 일련의 태스크를 수행해야 하고 각 작업자와 태스크에 작업자를 태스크에 할당하는 비용이 있다고 가정해 보겠습니다.
문제는 총 비용을 최소화하면서 두 명의 작업자가 동일한 태스크를 수행하지 않고 각 작업자를 최대 한 개의 태스크에 할당하는 것입니다.
이 문제는 작업자 4개와 태스크 4개가 있는 아래 그래프로 시각화할 수 있습니다. 에지는 작업에 작업자를 할당할 수 있는 모든 방법을 나타냅니다. 에지의 라벨은 작업자를 태스크에 할당하는 비용입니다.
할당은 에지의 하위 집합에 해당하며, 각 작업자에는 최대 한 개의 가장자리가 바깥쪽으로 선행되어 있고, 동일한 태스크로 이어지는 가장자리가 두 작업자가 없는 에지의 하위 집합에 해당합니다. 가능한 할당 하나가 아래에 표시됩니다.
할당 총비용은 70 + 55 + 95 + 45 = 265입니다.
다음 섹션에서는 MIP 솔버와 CP-SAT 솔버를 모두 사용하여 할당 문제를 푸는 방법을 보여줍니다.
OR-Tools는 할당 문제를 해결하기 위한 몇 가지 다른 도구도 제공하며 이는 MIP 또는 CP 솔버보다 빠를 수 있습니다.
그러나 이러한 도구는 간단한 유형의 할당 문제만 해결할 수 있습니다.
따라서 다양한 문제를 처리할 수 있고 대부분의 애플리케이션에서 충분히 빠른 일반 문제 해결자의 경우 MIP 및 CP-SAT 솔버를 사용하는 것이 좋습니다.
달리 명시되지 않는 한 이 페이지의 콘텐츠에는 Creative Commons Attribution 4.0 라이선스에 따라 라이선스가 부여되며, 코드 샘플에는 Apache 2.0 라이선스에 따라 라이선스가 부여됩니다. 자세한 내용은 Google Developers 사이트 정책을 참조하세요. 자바는 Oracle 및/또는 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."]]
