George Dantzig e o Algoritmo Simplex

Julho 30, 2010

George Dantzig (1914-2005) pode ser considerado o pai da programação linear, pois ele é o inventor do Simplex, o primeiro algoritmo para resolução de programas lineares. No pior caso, o simplex tem complexidade exponencial em função do tamanho da entrada e já foram desenvolvidos algoritmos polinomiais que resolvem programas lineares como o método dos pontos interiores. Na prática porém, o algoritmo simplex se comporta muito bem. Além disso possui características que os fazem ideais para os algoritmos de Branch and Bound, que resolvem programas lineares inteiros.

Diz a lenda que uma vez Dantizig chegou atrasado para o primeiro dia de aula de estatística na Universidade de Berkeley. Quando entrou, viu dois problemas escritos na lousa e, pensando serem tarefas para casa, anotou-os em seu caderno. Após alguns dias, entregou os exercícios ao professor e se desculpou por demorar tanto para resolvê-los, por estarem mais difíceis do que o normal. O professor pareceu não dar muita importância na hora, mas depois um tempo foi revelar a Dantizig que ele tinha resolvido dois problemas abertos em estatística.

O filme Gênio Indomável inspirou-se nessa história. Para quem não viu ou não lembra, Will Hunting era um faxineiro de uma Universidade, encrenqueiro, com passagens pela polícia e um gênio da matemática. Certa vez professores discutiam sobre um teorema em uma lousa e após irem embora, deixam o enunciado do teorema escrito. No dia seguinte o teorema está resolvido por um autor anônimo. Mais tarde descobrem se tratar do faxineiro e o filme se desenrola com os professores tentando convencer Hunting a estudar matemática e procurar um psicólogo para refrear seus ímpetos. É um filme que eu gostei muito e recomendo.

Uma paródia do filme, Perry Bible Fellowship

Em 1975, os economistas Tjalling Koopmans e Leonid Kantorovich foram laureados com o prêmio Nobel por sua teoria de alocação ótima de recursos, que era essencialmente programação linear. Injustamente Dantizig não foi premiado. Para quem tem interesse em saber mais sobre ele, eis uma biografia mais completa.

Enfim, o principal objetivo do meu post foi falar sobre um outro post que eu li no blog de teoria Gödel’s Lost Letter and P=NP, que começa falando sobre Dantzig para então apresentar uma excelente introdução a PLI. No post ele também apresenta uma modelagem para o problema de decidir se um grafo cúbico tem uma 3-coloração, que é NP-Completo.

Ele utiliza uma técnica interessante para modelar uma variável que pode assumir valores discretos não-contíguos, no caso 1, 2 e 4. Sejam variáveis binárias e que representa a cor de um vértice . Temos o modelo para cada :

(1)
(2)

Para cada três vértices adjacentes :

(3)

A desigualdade (2) diz que exatamente um, entre deve valer 1. Combinada com (1), temos que vale 1, 2 ou 4. A única forma para (3) ser satisfeita é com 1 + 2 + 4, ou seja devem ter cores diferentes, justamente a restrição do problema da 3-coloração. Assim, se existir uma solução satisfazendo tais desigualdades, o grafo possui uma 3-coloração.

Exemplo de uma 6-coloração de um Grafo

Há um problema mais genérico do que a 3-coloração em grafos cúbicos, que é determinar se um grafo G qualquer possui uma k-coloração. Definimos variáveis binárias se o vértice v possui cor c e 0 caso contrário. Temos o seguinte modelo:

(4) Para todo vértice v = 1,…,n,

(5) Para todo par de vértices adjacentes i e j, e toda cor c,

A igualdade (4) força que todo vértice tenha uma única cor. A igualdade (5) impede que dois vértices adjacentes tenham a mesma cor. Se existir algum y que satisfaz todas as igualdades, o grafo possui uma k-coloração.

Anúncios

Triangulação de Custo Mínimo

Julho 23, 2010

Considere n pontos em posição geral no plano. Considere todos os segmentos de reta que unem dois desses pontos quaisquer e com um custo associado. Uma triangulação desses pontos é um subconjunto maximal desses segmentos tal que dois segmentos nesse subconjunto não se interceptem (exceto nas pontas). O problema da triangulação de custo mínimo consiste em encontrar uma triangulação que minimize a soma dos custos dos segmentos. Existe uma variante muito famosa  em geometria computacional, onde a função objetivo é maximizar o menor ângulo entre dois lados de algum triângulo da triangulação, conhecida também como triangulação de Delaunay .

Exemplo de triangulação

Recentemente (2008) foi provado que esse problema é NP-difícil [1]. Entretanto, encontrei um artigo de 1997 que apresenta um modelo de PLI para esse problema [2]. Estou tentando uma abordagem parecida na minha tese, ou seja, atacando um problema cuja pertinência a classe NPC é um problema em aberto. Enfim, vamos ao modelo.

Modelo

Começamos com um teorema:
O número de segmentos em uma triangulação com n pontos é:

Além do mais, considere o grafo Gs, onde cada vértice corresponde a um segmento e existe uma aresta ligando dois vértices se seus segmentos correspondentes se interceptam. É possível mostrar que conjuntos independentes maximais nesse tipo de grafo têm uma correspondência um pra um com triangulações, ou seja queremos um conjunto independente de tamanho .

Como os segmentos têm custo associado (geralmente dado pela distância euclidiana), associamos esses mesmos custos aos vértices. Desta forma, seja o custo de cada vértice v. Definimos a variável se o vértice está no conjunto independente e 0 caso contrário.

O modelo fica:

(1)

(2)

(3)

A desigualdade (2) impede que dois vértices adjacentes estejam em no conjunto independente. A desigualdade (3) garante que o conjunto independente é maximal.

Trabalhei com o Pedro Hokama em cima desse problema no trabalho 2 da disciplina de Programação linear inteira. Consideramos algumas desigualdades adicionais para fortalecer o modelo e que estão presentes em [2,3], além de usar alguma delas como cortes para o algoritmo de Branch and Cut. Um relatório deste trabalho pode ser encontrado aqui.

Referências:

[1] Mulzer, W. and Rote, G. – Minimum-weight triangulation is NP-hard (http://arxiv.org/abs/cs.CG/0601002)
[2] Yoda, Y. and Imai, K. and Takeuchi, F. and Tajima, A. – A branch-and-cut approach for minimum weight triangulation
[3] Nemhauser, G.L. and Sigismondi, G.A – Strong cutting plane/branch-and-bound algorithm for node packing


Fim do semestre

Julho 17, 2010

Mais um semestre chegou ao final. Conclui minha última matéria da pós, cumprindo os 22 créditos necessários para o mestrado. Além do mais, fui PED C da disciplina de estruturas de dados, cumprindo com a obrigação de um bolsista do CNPq. Gostaria de ser PED novamente, quer em MC102, MC202 ou MC448. Porém, o tempo que este me consumiu durante o semestre mostrou-me que posso não conseguir terminar a tempo o mestrado caso pegue novamente.





Outra atividade com a qual me envolvi neste semestre foi a de técnico da maratona. Antes de ocorrer a prova da OBI, fiquei meio ausente e um outro pessoal da maratona deu aulas para os bixos. Porém, depois dessa prova, comecei a preparar aulas e selecionar exercícios de tópicos específicos. Fui colocando todos esses problemas em um placar, para monitorar quem estava resolvendo os problemas. Para minha decepção, pouca gente mostrou-se disposta a treinar firme e a maioria dos alunos resolveu menos da metade dos problemas que vinham sendo propostos (45). Continuei preparando aulas, mas a presença dos alunos foi diminuindo até restarem dois ou três alunos, que assistiam às aulas mas não faziam trabalho extra-classe. Acabei perdendo a motivação de preparar as aulas e somando-se a falta de tempo para dedicar ao mestrado, o período de copa do mundo e o fato de eu ter adoecido no final do semestre, fez eu interromper o treinamento antes do planejado. No começo do próximo semestre, haverá a seletiva da Unicamp. Espero que com os times formados, haja maior interesse por parte dos alunos em treinar e quem sabe assim eu me motivo a estudar e voltar a preparar aulas.





Toda essa série de atividades paralelas me tomou um tempo considerável e por ter ficado cerca de um mês treinando na USP e duas semanas na final mundial da maratona na China, já está certo que não conseguirei terminar meu mestrado em 1 ano e meio que era minha meta no começo. Conformado, espero que semestre que vem eu me dedique mais ao mestrado, possivelmente gastando um tempinho para ajudar os times a treinarem (a minha disponibilidade depende mais deles do que de mim). Ano que vem escrevo a tese e defendo no meio do ano. Vamos ver se consigo cumprir essas metas agora ;)


Tarefa 8: Escola

Julho 9, 2010

O último laboratório da disciplina era sobre ordenação externa. Esse é um tópico que é dado na disciplina de estruturas de dados (embora não estivesse na ementa na vez que cursei). O problema é basicamente o seguinte: dado um arquivo muito grande em disco, queremos ordená-lo, sem ter que carregá-lo completamente na memória. A ideia para resolver é subdividir o arquivo em blocos de tamanho fixo e pequenos o suficiente para caberem em memória. Lemos cada bloco de uma vez na memória, ordenamos com um algoritmo de ordenação qualquer e escrevemos de volta no arquivo. Imagine agora que temos vários vetores ordenados e queremos fazer uma intercalação entre eles e gerar um único vetor ordenado. Observe que esta é uma generalização do passo do algoritmo Merge-sort.

No caso básico temos dois vetores ordenados e mantemos apontadores para o começo de cada um deles, Pa e Pb, por exemplo. Sejam a[1] e b[1] os valores dos elementos apontados por tais apontadores. Se a[1] for menor do que b[1], então A deverá vir primeiro no vetor final ordenado. Caso contrário será b[1] (no caso de empate tanto faz). Ou seja, colocamos o menor entre a[1] e b[1] no vetor final. Supondo que a[1] foi colocado, a pergunta que devemos fazer é: qual elemento poderia aparecer depois de a[1] num vetor ordenado? É claro que é b[1] ou a[1], pois estes são os menores elementos maiores do que a[1]. Então andamos com o apontador Pa em 1 posição e repetimos o procedimento.

Como generalizar essa ideia? Suponha agora que temos m vetores, dados em uma matriz a[m][n] e apontadores (P1, …, Pm) para o começo de cada um deles. O primeiro elemento no vetor de saída será o menor entre todos os elementos. Só que como os vetores estão ordenados, sabemos que o menor elemento está na primeira posição de algum dos vetores ou seja, queremos min(a[1][1], a[2][1], ….. a[m][1]). Seja i* o vetor com menor elemento. Colocamos então a[i*][1] na saída. Com argumentação semelhante ao caso base, sabemos que o próximo elemento a aparecer depois de a[i*][1] é min(a[1][1], a[2][1], …, a[i-1][1],a[i][2], a[i+1][1], …, a[m][1]). Que é equivalente a ardamos uma posição com o ponteiro de i*. Achar o menor entre dois elementos é fácil, mas e para n elementos? Bom, para isso podemos utilizar a estrutura de fila de prioridades. Dela conseguimos extrair o menor elemento em O(1) e inserir em O(log n). Assim, extraímos a[i*][Pi*] e inserimos a[i*][Pi*+1].

Qual a complexidade do algoritmo? Seja m o número de blocos e n o tamanho de cada bloco. Para cada bloco devemos realizar uma operação de ordenação sobre O(n) elementos, implicando em uma complexidade de O(m*n*log n). Após isso, temos a etapa de intercalação. Observe que a fila de prioridades nunca tem mais de um elemento por vetor, logo tem tamanho no máximo O(m). Isso é importante porque as complexidades das operações sobre a fila são sobre o número de elementos nela. Logo, a remoção é O(1) e a inserção O(log m). Como todo elemento de cada vetor entra e sai da fila, vamos fazer uma operação de inserção e remoção para cada um dos O(n*m) elementos, resultando na complexidade O(n*m*log m). No total temos O(n*m*(log n + log m)) = O(n*m*log(n*m)). Seja N=n*m o tamanho do arquivo. Então a complexidade desse algoritmo O(N*log N).

Um tira no jardim de infância (velho!)

Para quem leu o enunciado, verá que o problema não está descrito desta forma. Decidi colocar um contexo de treinamento contra incêncios de uma escola. Dá para fazer as seguintes correspondências: a escola representa o arquivo, os alunos representam os elementos do arquivo, as salas correspondem aos blocos em memória e o pátio junto com o diretor representam a fila de prioridades. Minha intenção com isso era tornar o problema mais interessante e quem sabe deixar a ideia por trás do algoritmo mais intuitiva. Não sei se foi devido às provas de fim de semestre ou à dificuldade do problema (ou porque muita gente já tinha passado na parte prática), mas essa foi a tarefa com menor número de submissões.


Restrições disjuntas

Julho 5, 2010

Como se sabe, as restrições de um PL devem ser satisfeitas simultaneamente pelas variáveis. Do ponto de vista lógico, isso representa um AND. Porém, existe um modo de modelar um OR, ou seja, permitir que as variáveis satisfaçam uma ou outra restrição? A resposta é sim, e essa modelagem é obtida através das restrições disjuntas.

Vamos começar por um exemplo de uma dimensão. Suponha que queiramos que x satisfaça x <= 1 ou x >= 3. Para isso, introduzimos uma novo variável y binária (ou seja y=0 ou y=1). Se x satisfizer x <= 1, então y=0, se x satisfizer x >= 3, então y=1. Seja M um número positivo muito grande. Modificamos as desigualdades na seguinte forma:


Para entender o funcionamento desse modelo, suponha que y=0. Então o modelo fica:


Como M é suficientemente grande, x >= 3 – M será satisfeito para qualquer x. Ou seja, a desigualdade torna-se redundante e podemos desconsiderá-la. Agora supomos que y=1. Temos então:


A interpretação é análoga. A ideia básica dessa técnica consiste em tornar uma das desigualdades redundantes.

Podemos generalizar essa ideia para que, dado um conjunto de desigualdades, apenas uma delas seja satisfeita. Se tivermos três restrições para duas variáveis, por exemplo:



Introduzimos as variáveis . Se a primeira desigualdade for satisfeita, queremos que (análogo para as outras desigualdades). Consideramos o seguinte modelo:

Observe que exatamente um dos ‘s tem 1 e o resto tem 0. Ele age como um Multiplexador. Quando , dá pra ver que a segunda e terceira desigualdades ficam redundantes, já que os outros termos são sempre positivos e só tendem a aumentar o lado direito da desigualdade. Entretanto, todos os termos envolvendo da primeira equação zeram, fazendo com que ela fique na forma original. Os outros casos são análogos.

Referências

[1] http://www.dcc.unicamp.br/~cid/cursos/MO420/Material-didatico/


Tarefa 7: RPG

Julho 2, 2010

A tarefa 07 de MC202 consistia em simular uma batalha de RPG em turnos. São dados 2 equipes inimigas, cada qual com vários personagens com atributos diferentes, tais como força, velocidade, resistência e pontos de vida. Cada personagem tem um “período” inversamente proporcional a sua velocidade. Dados os períodos, podemos determinar os instantes de ataque de cada personagem. Quando dois personagens têm mesmo instante de ataque, existem alguns critérios de desempate que não cabe detalhar aqui.

Humano vs. Orc

Para determinar a ordem dos ataques, poderíamos fazer uma simulação discreta, por exemplo iterando sobre o tempo segundo a segundo e a cada instante verificar quem tinha um instante de tempo que caía bem naquele momento. A primeira desvantagem de tal método é que esse algoritmo é proporcional ao valor dos períodos, e a gente acaba iterando sobre instantes de tempo em que ninguém ataca. Além do mais, se os períodos forem números reais, esse tipo de abordagem pode ser impossível! Uma alternativa consiste em usar uma estrutura de dados chamada de fila de prioridades. A prioridade utilizada no caso é o próximo instante de ataque de cada personagem. Com uma fila de prioridades temos acesso ao elemento de maior prioridade em O(1). Assim, sabemos quem será o próximo atacante. Após efetuar o ataque, o próximo instante de ataque de uma personagem é a soma do instante atual e o período. Desta forma, basta reinseri-lo na fila com essa nova prioridade que em O(log n) conseguimos atualizar o heap mantendo suas propriedades.

Fila de Prioridades visualizada como árvore

Outro aspecto importante é a escolha do atacado. A estratégia de ambos os times consiste em atacar sempre o membro do time adversário com menos vida (mais alguns critérios de desempate). Uma observação importante é que todos do mesmo time “miram” no mesmo personagem inimigo até que este morra (porque se este já tinha menos pontos de vida, depois de sofrer os ataques continuará sendo o mais frágil). Isso nos possibilita ordenar inicialmente os membros dos times por ordem de não-decrescente de pontos de vida e, usando lista ligada, descobrir o membro a ser atacado em O(1), removendo-o da lista em caso de morte (também em O(1)). Aqui porém, eu permiti fazer do jeito força-bruta O(n) para escolher o mais fraco.

Esse método de simulação é mais eficiente do que a primeira proposta, sendo O(m log m), onde m é o número de turnos realizados antes de o jogo terminar. Porém, m pode ser proporcional aos valores de entrada, tornando nosso algoritmo pseudo-polinomial. Um exemplo seria dois times com um jogadores cada, um deles o personagem tem ataque 1 e no outro o personagem tem velocidade 0 e vida V. É fácil ver que o número de turnos é O(V), que pode ser tão grande quanto quisermos. Neste caso poderíamos ter feito algo mais eficiente, tal como calcular quantas vezes o personagem do time 1 ia atacar antes do personagem do time 2, mas acho que precisamos de uma ideia mais elaborada para funcionar em casos mais gerais. Porém, não cheguei a nenhuma conclusão se é possível resolver a simulação “analiticamente”.