Problema di assegnazione - Assignment problem

Il problema di assegnazione è un problema fondamentale di ottimizzazione combinatoria . Nella sua forma più generale, il problema è il seguente:

L'istanza del problema ha un numero di agenti e un numero di attività . Qualsiasi agente può essere assegnato per eseguire qualsiasi attività, sostenendo dei costi che possono variare a seconda dell'assegnazione agente-attività. È necessario eseguire quante più attività possibili assegnando al massimo un agente a ciascuna attività e al massimo un'attività a ciascun agente, in modo tale da ridurre al minimo il costo totale dell'assegnazione.

In alternativa, descrivendo il problema usando la teoria dei grafi:

Il problema assegnazione consiste nel trovare, in una ponderata grafo bipartito , una corrispondenza di una data dimensione, in cui la somma dei pesi dei bordi è minimo.

Se il numero di agenti e attività è uguale, il problema viene chiamato assegnazione bilanciata . In caso contrario si parla di assegnazione sbilanciata . Se il costo totale dell'assegnazione per tutte le attività è uguale alla somma dei costi per ogni agente (o la somma dei costi per ogni attività, che è la stessa cosa in questo caso), allora il problema è chiamato assegnazione lineare . Comunemente, quando si parla del problema di assegnazione senza alcuna qualificazione aggiuntiva, si intende il problema di assegnazione bilanciato lineare .

Esempi

Supponiamo che una società di taxi abbia a disposizione tre taxi (gli agenti) e tre clienti (le attività) che desiderano essere prelevati il prima possibile. L'azienda è orgogliosa di ritiri veloci, quindi per ogni taxi il "costo" del prelievo di un particolare cliente dipenderà dal tempo impiegato dal taxi per raggiungere il punto di prelievo. Questo è un problema di assegnazione equilibrata . La sua soluzione è qualsiasi combinazione di taxi e clienti risulti nel minor costo totale.

Supponiamo ora che ci siano quattro taxi disponibili, ma ancora solo tre clienti. Questo è un problema di assegnazione sbilanciato . Un modo per risolverlo è inventare un quarto compito fittizio, forse chiamato "stare fermo senza fare nulla", con un costo pari a 0 per il taxi ad esso assegnato. Ciò riduce il problema a un problema di assegnazione bilanciata, che può quindi essere risolto nel modo consueto e fornire comunque la migliore soluzione al problema.

È possibile eseguire regolazioni simili per consentire più attività rispetto agli agenti, attività a cui devono essere assegnati più agenti (ad esempio, un gruppo di più clienti di quanti possano entrare in un taxi) o massimizzare il profitto anziché ridurre al minimo i costi.

Definizione formale

La definizione formale del problema di assegnazione (o problema di assegnazione lineare ) è

Dati due insiemi, A e T , di uguale dimensione, insieme a una funzione peso C : A × T → R . Trova una biiezione f : A → T tale che la funzione di costo :

\sum _{a\in A}C(a,f(a))

è ridotto al minimo.

Di solito la funzione peso è vista come una matrice quadrata a valori reali C , in modo che la funzione di costo sia scritta come:

\sum _{a\in A}C_{a,f(a)}

Il problema è "lineare" perché la funzione di costo da ottimizzare così come tutti i vincoli contengono solo termini lineari.

Algoritmi

Una soluzione ingenua per il problema dell'assegnazione è controllare tutti gli incarichi e calcolare il costo di ciascuno. Questo può essere molto inefficiente poiché, con n agenti e n attività, ci sono n ! ( fattoriale di n ) assegnazioni diverse. Fortunatamente, ci sono molti algoritmi per risolvere il problema in tempo polinomiale in n .

Il problema di assegnazione è un caso speciale del problema di trasporto , che è un caso speciale del problema di flusso di costo minimo , che a sua volta è un caso speciale di un programma lineare . Sebbene sia possibile risolvere uno qualsiasi di questi problemi utilizzando l' algoritmo del simplesso , ogni specializzazione ha un piccolo spazio di soluzione e quindi algoritmi più efficienti progettati per sfruttare la sua struttura speciale.

Assegnazione equilibrata

Nel problema dell'assegnamento bilanciato, entrambe le parti del grafo bipartito hanno lo stesso numero di vertici, indicato con n .

Uno dei primi algoritmi polinomiali per l'assegnazione bilanciata è stato l' algoritmo ungherese . È un algoritmo globale : si basa sul miglioramento di una corrispondenza lungo percorsi aumentanti (percorsi alternati tra vertici non corrispondenti). La sua complessità di runtime, quando si usano gli heap di Fibonacci , è , dove m è un numero di archi. Questo è attualmente il tempo di esecuzione più veloce di un algoritmo fortemente polinomiale per questo problema. Se tutti i pesi sono interi, il tempo di esecuzione può essere migliorato a , ma l'algoritmo risultante è solo debolmente polinomiale. Se i pesi sono interi e tutti i pesi sono al massimo C (dove C >1 è un numero intero), allora il problema può essere risolto in tempo debolmente polinomiale in un metodo chiamato scalatura dei pesi . $O(mn+n^{2}\log n)$ $O(mn+n^{2}\log \log n)$ $O(m{\sqrt {n}}\log(n\cdot C))$

Oltre ai metodi globali, esistono metodi locali che si basano sulla ricerca di aggiornamenti locali (piuttosto che sui percorsi aumentanti completi). Questi metodi hanno garanzie di runtime asintotiche peggiori, ma spesso funzionano meglio nella pratica. Questi algoritmi sono chiamati algoritmi di asta , algoritmi push-relabel o algoritmi preflow-push. Alcuni di questi algoritmi si sono dimostrati equivalenti.

Alcuni dei metodi locali presuppongono che il grafo ammetta un matching perfetto ; in caso contrario, alcuni di questi metodi potrebbero essere eseguiti per sempre. Un modo tecnico semplice per risolvere questo problema consiste nell'estendere il grafo di input a un grafo bipartito completo, aggiungendo archi artificiali con pesi molto grandi. Questi pesi dovrebbero superare i pesi di tutti gli accoppiamenti esistenti, per evitare la comparsa di bordi artificiali nella possibile soluzione.

Come mostrato da Mulmuley, Vazirani e Vazirani, il problema del perfetto matching di peso minimo viene convertito nel trovare minori nella matrice di adiacenza di un grafo. Usando il lemma dell'isolamento , si può trovare un matching perfetto di peso minimo in un grafo con probabilità almeno ½. Per un grafo con n vertici, richiede tempo. $O(\log ^{2}(n))$

Assegnazione sbilanciata

Nel problema dell'assegnamento sbilanciato, la parte più grande del grafo bipartito ha n vertici e la parte più piccola ha r < n vertici. C'è anche una costante s che è al massimo la cardinalità di una corrispondenza massima nel grafico. L'obiettivo è trovare una corrispondenza a costo minimo di dimensione esattamente s . Il caso più comune è il caso in cui il grafo ammette un matching perfetto unilaterale (cioè un matching di dimensione r ), e s = r .

L'assegnazione sbilanciata può essere ridotta a un'assegnazione equilibrata. La riduzione ingenua consiste nell'aggiungere nuovi vertici alla parte più piccola e collegarli alla parte più grande utilizzando bordi di costo 0. Tuttavia, ciò richiede nuovi bordi. Una riduzione più efficiente è chiamata tecnica del raddoppio . Qui, un nuovo grafo G' è costruito da due copie del grafo originale G : una copia in avanti Gf e una copia all'indietro Gb. La copia all'indietro è "capovolta", in modo che, in ogni lato di G' , ci siano ora n + r vertici. Tra le copie, dobbiamo aggiungere due tipi di bordi di collegamento: $nr$ $n(nr)$

Large-to-large: da ogni vertice nella parte più grande di Gf , aggiungi un arco a costo zero al corrispondente vertice in Gb .
Da piccolo a piccolo: se il grafo originale non ha un matching perfetto unilaterale, allora da ciascun vertice nella parte più piccola di Gf , aggiungi un arco di costo molto elevato al corrispondente vertice in Gb .

Tutto sommato, sono necessari al massimo nuovi bordi. Il grafico risultante ha sempre una perfetta corrispondenza di dimensioni . Un abbinamento perfetto di costo minimo in questo grafico deve consistere di abbinamenti di cardinalità massima a costo minimo in Gf e Gb. Il problema principale con questa tecnica di raddoppio è che non c'è guadagno di velocità quando . $n+r$ $n+r$ $r\ll n$

Invece di usare la riduzione, il problema dell'assegnazione sbilanciata può essere risolto generalizzando direttamente gli algoritmi esistenti per l'assegnazione bilanciata. L' algoritmo ungherese può essere generalizzato per risolvere il problema in tempo fortemente polinomiale. In particolare, se s = r allora il runtime è . Se i pesi sono interi, il metodo di Thorup può essere utilizzato per ottenere un runtime di . $O(ms+s^{2}\log r)$ $O(mr+r^{2}\log r)$ $O(ms+s^{2}\log \log r)$

Soluzione mediante programmazione lineare

Il problema dell'assegnazione può essere risolto presentandolo come un programma lineare . Per comodità presenteremo il problema della massimizzazione. Ogni arco $(i, j)$ , dove i è in A e j è in T, ha un peso . Per ogni arco abbiamo una variabile _.La variabile è 1 se il bordo è contenuto nel matching e 0 altrimenti, quindi impostiamo i vincoli di dominio: ${\textstyle w_{ij}}$ $(i,j)$ ${\textstyle x_{ij}}$

0\leq x_{ij}\leq 1{\text{ per }}i,j\in A,T,\,

x_{ij}\in \mathbb {Z} {\text{ per }}i,j\in A,T.

Il peso totale dell'abbinamento è: . L'obiettivo è trovare un abbinamento perfetto di peso massimo. $\sum _{(i,j)\in A\times T}w_{ij}x_{ij}$

Per garantire che le variabili rappresentino effettivamente una corrispondenza perfetta, aggiungiamo vincoli che dicono che ogni vertice è adiacente esattamente a un arco nella corrispondenza, cioè,

\sum _{j\in T}x_{ij}=1{\text{ per }}i\in A,\,~~~\sum _{i\in A}x_{ij}=1 {\text{ per }}j\in T,\,

.

Tutto sommato abbiamo il seguente LP:

{\text{massimizza}}~~\sum _{(i,j)\in A\times T}w_{ij}x_{ij}

{\text{soggetto a}}~~\sum _{j\in T}x_{ij}=1{\text{ per }}i\in A,\,~~~\sum _{i \in A}x_{ij}=1{\text{ per }}j\in T

0\leq x_{ij}\leq 1{\text{ per }}i,j\in A,T,\,

x_{ij}\in \mathbb {Z} {\text{ per }}i,j\in A,T.

Questo è un programma lineare intero. Tuttavia, possiamo risolverlo senza i vincoli di integralità (cioè, eliminare l'ultimo vincolo), utilizzando metodi standard per risolvere programmi lineari continui. Sebbene questa formulazione consenta anche valori di variabili frazionarie, in questo caso speciale, il PL ha sempre una soluzione ottima in cui le variabili assumono valori interi. Questo perché la matrice dei vincoli del LP frazionario è totalmente unimodulare : soddisfa le quattro condizioni di Hoffman e Gale.

Questo può essere dimostrato anche direttamente. Sia x una soluzione ottima del PL frazionario, sia il suo peso totale, sia il numero di variabili non integrali. Se abbiamo finito. Altrimenti, c'è una variabile frazionaria, diciamo . Poiché la somma delle variabili adiacenti a è 1, che in un numero intero, deve esserci un'altra variabile adiacente a j ₂ con un valore frazionario, diciamo . Per considerazioni simili su i ₃ , deve esserci un'altra variabile adiacente a i ₃ con un valore frazionario, diciamo . Con considerazioni simili ci spostiamo da un vertice all'altro, raccogliendo archi con valori frazionari. Poiché il grafico è finito, a un certo punto dobbiamo avere un ciclo. Senza perdita di generalità possiamo assumere che il ciclo termini al vertice i ₁ , quindi l'ultima variabile frazionaria nel ciclo è . Quindi il numero di archi nel ciclo è 2 m – deve essere pari poiché il grafo è bipartito. $w(x)$ $k(x)$ $k(x)=0$ ${\textstyle x_{i_{1},j_{2}}}$ $j_{2}$ ${\textstyle x_{i_{3},j_{2}}}$ ${\textstyle x_{i_{3},j_{4}}}$ ${\textstyle x_{i_{1},j_{2m}}}$

Supponiamo di aggiungere una certa costante e a tutte le variabili pari del ciclo e rimuovere la stessa costante e da tutte le variabili dispari del ciclo. Per ogni tale e , la somma delle variabili vicino a ciascun vertice rimane la stessa (1), quindi i vincoli sui vertici sono ancora soddisfatti. Inoltre, se e è sufficientemente piccolo, tutte le variabili rimangono tra 0 e 1, quindi anche i vincoli di dominio sono ancora soddisfatti. È facile trovare una e più grande che mantenga i vincoli di dominio: è o la differenza più piccola tra una variabile dispari e 0, o la differenza più piccola tra una variabile pari e 1. Ora, abbiamo una variabile frazionaria in meno, quindi k ( x ) diminuisce di 1. Il valore obiettivo rimane lo stesso, poiché altrimenti potremmo aumentarlo selezionando e come positivo o negativo, in contraddizione con l'assunzione che sia massimale.

Ripetendo il processo di rimozione del ciclo si arriva, dopo al massimo n passaggi, a una soluzione in cui tutte le variabili sono integrali.

Altri metodi e algoritmi di approssimazione

Esistono altri approcci per il problema dell'assegnazione e sono stati esaminati da Duan e Pettie (vedi Tabella II). Il loro lavoro propone un algoritmo di approssimazione per il problema di assegnazione (e il più generale problema di corrispondenza del peso massimo ), che funziona in tempo lineare per qualsiasi limite di errore fisso.

Generalizzazione

Quando formulato come un problema di teoria dei grafi, il problema di assegnazione può essere esteso da grafi bipartiti a grafi arbitrari. Il problema corrispondente, di trovare una corrispondenza in un grafo ponderato in cui la somma dei pesi è massimizzata, è chiamato problema di corrispondenza del peso massimo .

Guarda anche

Riferimenti e approfondimenti

Brualdi, Richard A. (2006). Classi di matrici combinatorie . Enciclopedia della matematica e delle sue applicazioni. 108 . Cambridge: Pressa dell'università di Cambridge . ISBN 978-0-521-86565-4. Zbl 1106.05001 .
Burkard, Rainer ; M. Dell'Amico; San Martello (2012). Problemi di assegnazione (ristampa rivista) . SIAM. ISBN 978-1-61197-222-1.
Bertsekas, Dimitri (1998). Ottimizzazione della rete: modelli continui e discreti . Atena Scientifica. ISBN 978-1-886529-02-1.

Languages

In other projects