Problema de atribuição - Assignment problem

O problema de atribuição é um problema fundamental de otimização combinatória . Em sua forma mais geral, o problema é o seguinte:

A instância do problema possui vários agentes e várias tarefas . Qualquer agente pode ser atribuído para executar qualquer tarefa, incorrendo em alguns custos que podem variar dependendo da atribuição da tarefa do agente. É necessário realizar o maior número de tarefas possível atribuindo no máximo um agente a cada tarefa e no máximo uma tarefa a cada agente, de forma que o custo total da atribuição seja minimizado.

Alternativamente, descrevendo o problema usando a teoria dos grafos:

O problema de atribuição consiste em encontrar, em um grafo bipartido ponderado , um casamento de um determinado tamanho, no qual a soma dos pesos das arestas é mínima.

Se o número de agentes e tarefas forem iguais, o problema é chamado de atribuição balanceada . Caso contrário, é chamado de atribuição não balanceada . Se o custo total da atribuição para todas as tarefas for igual à soma dos custos de cada agente (ou à soma dos custos de cada tarefa, que é a mesma coisa neste caso), então o problema é denominado atribuição linear . Normalmente, quando se fala do problema de atribuição sem qualquer qualificação adicional, então se entende o problema de atribuição linear equilibrada .

Exemplos

Suponha que uma empresa de táxi tenha três táxis (os agentes) disponíveis e três clientes (as tarefas) que desejam ser buscados o mais rápido possível. A empresa se orgulha de suas coletas rápidas; portanto, para cada táxi, o "custo" de pegar um cliente específico dependerá do tempo que o táxi leva para chegar ao ponto de coleta. Este é um problema de atribuição equilibrado . Sua solução é qualquer combinação de táxis e clientes que resulte no menor custo total.

Agora, suponha que haja quatro táxis disponíveis, mas ainda assim apenas três clientes. Este é um problema de atribuição desequilibrado . Uma maneira de resolver isso é inventar uma quarta tarefa fictícia, talvez chamada de "ficar sentado sem fazer nada", com um custo de 0 para o táxi atribuído a ela. Isso reduz o problema a um problema de atribuição equilibrada, que pode então ser resolvido da maneira usual e ainda fornecer a melhor solução para o problema.

Ajustes semelhantes podem ser feitos para permitir mais tarefas do que agentes, tarefas às quais vários agentes devem ser atribuídos (por exemplo, um grupo de mais clientes do que caberia em um táxi), ou maximizar o lucro em vez de minimizar o custo.

Definição formal

A definição formal do problema de atribuição (ou problema de atribuição linear ) é

Dados dois conjuntos, A e T , de igual tamanho, em conjunto com uma função de ponderação C : Uma × T → R . Encontre uma bijeção f : A → T de modo que a função de custo :

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

é minimizado.

Normalmente, a função de peso é vista como uma matriz quadrada de valor real C , de modo que a função de custo é escrita como:

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

O problema é "linear" porque a função de custo a ser otimizada, bem como todas as restrições, contêm apenas termos lineares.

Algoritmos

Uma solução ingênua para o problema de atribuição é verificar todas as atribuições e calcular o custo de cada uma. Isso pode ser muito ineficiente, pois, com n agentes en tarefas, há n ! ( fatorial de n ) atribuições diferentes. Felizmente, existem muitos algoritmos para resolver o problema no tempo polinomial em n .

O problema de atribuição é um caso especial do problema de transporte , que é um caso especial do problema de fluxo de custo mínimo , que por sua vez é um caso especial de um programa linear . Embora seja possível resolver qualquer um desses problemas usando o algoritmo simplex , cada especialização tem um pequeno espaço de solução e, portanto, algoritmos mais eficientes projetados para tirar proveito de sua estrutura especial.

Trabalho equilibrado

No problema de atribuição balanceada, ambas as partes do grafo bipartido têm o mesmo número de vértices, denotados por n .

Um dos primeiros algoritmos de tempo polinomial para atribuição balanceada foi o algoritmo húngaro . É um algoritmo global - é baseado na melhoria da correspondência ao longo de caminhos aumentantes (caminhos alternados entre vértices não correspondidos). Sua complexidade de tempo de execução, ao usar pilhas de Fibonacci , é , onde m é um número de arestas. Este é atualmente o tempo de execução mais rápido de um algoritmo fortemente polinomial para este problema. Se todos os pesos forem inteiros, então o tempo de execução pode ser melhorado para , mas o algoritmo resultante é apenas fracamente polinomial. Se os pesos forem inteiros, e todos os pesos forem no máximo C (onde C > 1 é algum inteiro), então o problema pode ser resolvido em tempo fracamente polinomial em um método chamado escala de peso . ${\ displaystyle O (mn + n ^ {2} \ log n)}$ ${\ displaystyle O (mn + n ^ {2} \ log \ log n)}$ ${\ displaystyle O (m {\ sqrt {n}} \ log (n \ cdot C))}$

Além dos métodos globais, existem métodos locais que se baseiam na localização de atualizações locais (em vez de caminhos completos de aumento). Esses métodos têm garantias de tempo de execução assintóticas piores, mas geralmente funcionam melhor na prática. Esses algoritmos são chamados de algoritmos de leilão , algoritmos push-relabel ou algoritmos pré-fluxo-push. Alguns desses algoritmos mostraram-se equivalentes.

Alguns dos métodos locais assumem que o gráfico admite uma combinação perfeita ; se não for esse o caso, alguns desses métodos podem ser executados para sempre. Uma maneira técnica simples de resolver esse problema é estender o grafo de entrada para um grafo bipartido completo, adicionando arestas artificiais com pesos muito grandes. Esses pesos devem exceder os pesos de todas as combinações existentes, para evitar o aparecimento de arestas artificiais na solução possível.

Conforme mostrado por Mulmuley, Vazirani e Vazirani, o problema de correspondência perfeita de peso mínimo é convertido para encontrar menores na matriz de adjacência de um grafo. Usando o lema de isolamento , uma correspondência perfeita de peso mínimo em um gráfico pode ser encontrada com probabilidade de pelo menos ½. Para um gráfico com n vértices, isso requer tempo. ${\ displaystyle O (\ log ^ {2} (n))}$

Atribuição desequilibrada

No problema de atribuição não balanceada, a maior parte do grafo bipartido possui n vértices e a parte menor possui r < n vértices. Há também uma constante s que é no máximo a cardinalidade de uma correspondência máxima no gráfico. O objetivo é encontrar uma correspondência de custo mínimo de tamanho exatamente s . O caso mais comum é o caso em que o gráfico admite um casamento perfeito unilateral (ou seja, um casamento de tamanho r ) e s = r .

A atribuição não balanceada pode ser reduzida a uma atribuição balanceada. A redução ingênua é adicionar novos vértices à parte menor e conectá-los à parte maior usando arestas de custo 0. No entanto, isso requer novas arestas. Uma redução mais eficiente é chamada de técnica de duplicação . Aqui, um novo gráfico G ' é construído a partir de duas cópias do gráfico original G : uma cópia para a frente Gf e uma cópia para trás Gb. A cópia reversa é "invertida", de forma que, em cada lado de G ' , agora existem n + r vértices. Entre as cópias, precisamos adicionar dois tipos de bordas de ligação: ${\ displaystyle nr}$ ${\ displaystyle n (nr)}$

Grande para grande: de cada vértice na parte maior de Gf , adicione uma aresta de custo zero ao vértice correspondente em Gb .
Pequeno para pequeno: se o gráfico original não tiver uma correspondência unilateral perfeita, a partir de cada vértice na parte menor de Gf , adicione uma aresta de custo muito alto ao vértice correspondente em Gb .

Em suma, no máximo novas arestas são necessárias. O gráfico resultante sempre tem uma combinação perfeita de tamanho . Uma correspondência perfeita de custo mínimo neste gráfico deve consistir em correspondências de cardinalidade máxima de custo mínimo em Gf e Gb. O principal problema com essa técnica de duplicação é que não há ganho de velocidade quando . ${\ displaystyle n + r}$ ${\ displaystyle n + r}$ ${\ displaystyle r \ ll n}$

Em vez de usar a redução, o problema de atribuição não balanceada pode ser resolvido generalizando diretamente os algoritmos existentes para atribuição balanceada. O algoritmo húngaro pode ser generalizado para resolver o problema em tempo fortemente polinomial. Em particular, se s = r, então o tempo de execução é . Se os pesos forem inteiros, o método de Thorup pode ser usado para obter um tempo de execução de . ${\ displaystyle O (ms + s ^ {2} \ log r)}$ ${\ displaystyle O (mr + r ^ {2} \ log r)}$ ${\ displaystyle O (ms + s ^ {2} \ log \ log r)}$

Solução por programação linear

O problema de atribuição pode ser resolvido apresentando-o como um programa linear . Por conveniência, apresentaremos o problema de maximização. Cada aresta $(i, j)$ , onde i está em A e j está em T, tem um peso . Para cada aresta , temos uma variável _.A variável é 1 se a borda está contida na correspondência e 0 caso contrário, então definimos as restrições de domínio: ${\ textstyle w_ {ij}}$ ${\ displaystyle (i, j)}$ ${\ textstyle x_ {ij}}$

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

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

O peso total da correspondência é a seguinte: . O objetivo é encontrar uma combinação perfeita de peso máximo. ${\ displaystyle \ sum _ {(i, j) \ in A \ times T} w_ {ij} x_ {ij}}$

Para garantir que as variáveis realmente representem uma correspondência perfeita, adicionamos restrições dizendo que cada vértice é adjacente a exatamente uma aresta na correspondência, ou seja,

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

.

Ao todo, temos o seguinte LP:

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

{\ displaystyle {\ text {subject to}} ~~ \ sum _ {j \ in T} x_ {ij} = 1 {\ text {for}} i \ in A, \, ~~~ \ sum _ {i \ in A} x_ {ij} = 1 {\ text {for}} j \ in T}

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

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

Este é um programa linear inteiro. No entanto, podemos resolvê-lo sem as restrições de integralidade (ou seja, eliminar a última restrição), usando métodos padrão para resolver programas lineares contínuos. Embora esta formulação também permita valores de variáveis fracionários, neste caso especial, o LP sempre tem uma solução ótima onde as variáveis assumem valores inteiros. Isso ocorre porque a matriz de restrição do LP fracionário é totalmente unimodular - ela satisfaz as quatro condições de Hoffman e Gale.

Isso também pode ser provado diretamente. Seja x uma solução ótima do LP fracionário, seu peso total e o número de variáveis não integrais. Se terminarmos. Caso contrário, existe uma variável fracionária, digamos . Como a soma das variáveis adjacentes a é 1, que em um inteiro, deve haver outra variável adjacente a j ₂ com um valor fracionário, digamos . Por considerações semelhantes em i ₃ , deve haver outra variável adjacente a i ₃ com um valor fracionário, digamos . Por considerações semelhantes, passamos de um vértice a outro, coletando arestas com valores fracionários. Como o gráfico é finito, em algum ponto devemos ter um ciclo. Sem perda de generalidade, podemos assumir que o ciclo termina no vértice i ₁ , então a última variável fracionária do ciclo é . Portanto, o número de arestas no ciclo é de 2 m - deve ser par, já que o gráfico é bipartido. ${\ displaystyle w (x)}$ ${\ displaystyle k (x)}$ ${\ displaystyle k (x) = 0}$ ${\ textstyle x_ {i_ {1}, j_ {2}}}$ ${\ displaystyle j_ {2}}$ ${\ textstyle x_ {i_ {3}, j_ {2}}}$ ${\ textstyle x_ {i_ {3}, j_ {4}}}$ ${\ textstyle x_ {i_ {1}, j_ {2m}}}$

Suponha que adicionemos uma certa constante e a todas as variáveis pares do ciclo e removamos a mesma constante e de todas as variáveis ímpares do ciclo. Para qualquer e , a soma das variáveis perto de cada vértice permanece a mesma (1), então as restrições do vértice ainda são satisfeitas. Além disso, se e for suficientemente pequeno, todas as variáveis permanecerão entre 0 e 1, de modo que as restrições de domínio também serão satisfeitas. É fácil encontrar um maior e que mantém as restrições de domínio: ou é a menor diferença entre uma variável ímpar e 0, ou a menor diferença entre uma variável par e 1. Agora, temos uma variável fracionária a menos, então k ( x ) diminui em 1. O valor objetivo permanece o mesmo, caso contrário, poderíamos aumentá-lo selecionando e como positivo ou negativo, em contradição com a suposição de que seja máximo.

Repetindo o processo de remoção do ciclo, chegamos, após no máximo n passos, a uma solução em que todas as variáveis são integrais.

Outros métodos e algoritmos de aproximação

Outras abordagens para o problema de atribuição existem e são revisadas por Duan e Pettie (ver Tabela II). Seu trabalho propõe um algoritmo de aproximação para o problema de atribuição (e o problema mais geral de correspondência de peso máximo ), que funciona em tempo linear para qualquer limite de erro fixo.

Generalização

Quando formulado como um problema de teoria dos grafos, o problema de atribuição pode ser estendido de grafos bipartidos para grafos arbitrários. O problema correspondente, de encontrar uma correspondência em um gráfico ponderado onde a soma dos pesos é maximizada, é chamado de problema de correspondência de peso máximo .

Veja também

Referências e leituras adicionais

Brualdi, Richard A. (2006). Classes de matrizes combinatórias . Enciclopédia de matemática e suas aplicações. 108 . Cambridge: Cambridge University Press . ISBN 978-0-521-86565-4. Zbl 1106.05001 .
Burkard, Rainer ; M. Dell'Amico; S. Martello (2012). Problemas de atribuição (reimpressão revisada) . SIAM. ISBN 978-1-61197-222-1.
Bertsekas, Dimitri (1998). Otimização de redes: modelos contínuos e discretos . Athena Scientific. ISBN 978-1-886529-02-1.

Languages

In other projects