Compito
Mantieni tutto organizzato con le raccolte
Salva e classifica i contenuti in base alle tue preferenze.
Uno dei problemi di ottimizzazione combinatoria più noti è il problema di assegnazione. Ecco un esempio: supponiamo che un gruppo di lavoratori debba eseguire una serie di attività e che per ogni worker e attività sia previsto un costo per l'assegnazione del worker all'attività.
Il problema è assegnare ogni worker al massimo a un'attività, senza che due worker
eseguano la stessa attività, riducendo al minimo il costo totale.
Puoi visualizzare questo problema dal grafico qui sotto, in cui ci sono quattro worker e quattro attività. I bordi rappresentano tutti i modi possibili
per assegnare worker alle attività. Le etichette ai bordi rappresentano i costi associati all'assegnazione dei lavoratori alle attività.
Un'assegnazione corrisponde a un sottoinsieme di perimetri, in cui ciascun worker ha al massimo un bordo che conduce all'esterno e nessun worker ha un bordo che conduce alla stessa attività. Di seguito è riportata una possibile assegnazione.
Il costo totale dell'assegnazione è 70 + 55 + 95 + 45 = 265.
La sezione successiva mostra come risolvere un problema di assegnazione, utilizzando sia il risolutore MIP sia quello CP-SAT.
OR-Tools fornisce anche un paio di altri strumenti per risolvere problemi di assegnazione,
che possono essere più veloci dei risolutori MIP o CP:
Tuttavia, questi strumenti possono risolvere solo tipi semplici di problemi relativi ai compiti.
Per i risolutori generici in grado di gestire un'ampia varietà di problemi (e abbastanza veloci per la maggior parte delle applicazioni), consigliamo i risolutori MIP e CP-SAT.
Salvo quando diversamente specificato, i contenuti di questa pagina sono concessi in base alla licenza Creative Commons Attribution 4.0, mentre gli esempi di codice sono concessi in base alla licenza Apache 2.0. Per ulteriori dettagli, consulta le norme del sito di Google Developers. Java è un marchio registrato di Oracle e/o delle sue consociate.
Ultimo aggiornamento 2024-08-09 UTC.
[null,null,["Ultimo aggiornamento 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."]]
