Arena MTE

Agosto 27, 2010

Domingo passado (22 de agosto), participei do arena MTE. O arena MTE é uma competição de resolução de cases, problemas reais da indústria, em equipe de 4 pessoas.  O evento durou todo o Domingo, com várias palestras e 4 cases: da editora Abril, da AISEC, da Henkel e do próprio MTE. Os 5 melhores colocados nesses 4 cases iriam para a final, participar da resolução de mais um case da Fiat, sendo o time vencedor dessa última etapa premiado com um netbook para cada integrante.  Participaram desse evento 192 pessoas, ou 48 equipes. Nossa equipe era a “on Rails”, com o Vítor, a Bia e o Felipe Guaycuru (o criador do GDE!).

Os Cases

Vou aqui detalhar um pouquinho mais sobre os cases propostos.

Abril — Inicialmente nos foi passado um vídeo de um executivo de uma revista se comunicando via nextel com um acessor de uma marca, para supostamente negociar propagandas. Depois entregaram uma folha descrevendo o seguinte problema: A abril recentemente fundou uma empresa distribuidora, chamada Treelog. Um dos desafios dessa empresa é entregar as revistas veja aos Sábados, uma vez que atualmente há regiões para as quais as revistas são entregues somente às Segundas ou Terças-feiras. O objetivo era propor uma solução para esse problema, utilizando ideias do vídeo apresentado.

AIESEC — Nesse case a AIESEC estava estudando criar uma sede na Coreia do Norte, que planeja criar zonas de livre comércio. O objetivo era convencer o governo comunista de que a entrada da AIESEC no país traria benefícios, sem com isso ameaçar o sistema de governo.

Henkel — Dois representantes da Henkel participaram desse case. O cenário é o seguinte: a cola Tenaz, líder de vendas nesse segmento, depende do petróleo para sua composição. Estamos no ano de 2030 e há uma projeção de que em 25 as reservas de petróleo irão se esgotar e o preço deste irá subir exponencialmente nos próximos anos. Foi descoberto porém, um novo tipo de cola, batizada de Power Glue, biodegradável e 5 vezes mais aderente e seu principal componente é produzido por bactéria, uma fonte renovável. O problema é que não foram feitos testes conclusivos sobre os efeitos carcinogênicos do produto. O objetivo era decidir se íamos produzir tal cola e quando começar a produção, justificando as decisões.

MTE — Nesse case, o MTE enfrenta vários problemas: empresas perderam interesse em patrocinar eventos, consequentemente o número de participantes em tais eventos diminuiu e para piorar há uma falta de interesse por parte dos alunos em integrar o MTE. O objetivo era propor ideias para reverter essa situação.

Depois dos cases cansativos, tivemos um coffee-break e então o anúncio dos finalistas. Não fomos classificados para a final, que consistia em resolver um case da Fiat. O restante dos times deveria participar de um laboratório que consistia em montar um cubo de papel representando um carro e colocar inovações nele, na vertente do Fiat Mio http://www.fiatmio.cc/ A maioria das equipes (incluindo a nossa) decidiu não participar desse último evento e voltamos para a Unicamp de ônibus.

Conclusão

O MTE espalhou bastante propaganda pelo campus e todos eles apresentavam desafios de lógica. Como eu nunca tinha participado, achei que os cases eram de problem solving, mas sem cunho matemático/computacional como olimpíadas e maratona de programação. Minha impressão no final do dia foi de que os cases não davam muito espaço para ideias, uma vez que a solução esperada já era delineada no enunciado do problema. Obviamente, todas as equipes apresentaram soluções parecidas, o que torna difícil a comparação das equipes por soluções.

Segundo o regulamento da competição, outras formas de avaliação são comunicação, trabalho em equipe, pró-atividade, ética e conduta. Não creio que nossa equipe tenha se destacado em nenhum desses quesitos (exceto pelo Vítor que pode ter arrecadado uns pontos extras com a comunicação). Pelo contrário, creio que perdemos pontos com ética e conduta, já que diversas vezes durante a resolução fizemos piadas e brincadeiras :P.

Enfim, senti que acordei Domingo às 6 da manhã não para participar de uma competição, mas para ficar o dia inteiro participando de dinâmicas de grupo exaustivas (com a diferença que eu conhecia a minha equipe). Bom, pelo menos ganhamos uns brindes: boné, camiseta e caneta.

Anúncios

Seletiva Interna da Maratona

Agosto 20, 2010

Da seletiva

No Domingo passado, 15/08 foi realizada a seletiva dos times da Unicamp. Estava marcado para os competidores chegarem às 13h. A maior parte do pessoal se atrasou e por isso o warmup começou às 13h40. Tudo correu bem no aquecimento. Eu queria registrar a conta do SPOJ dos competidores e testar o placar, que por sinal funcionou corretamente. Comecei a prova às 14h10. Para meu desespero, logo que o pessoal começou a submeter, percebemos que o placar estava bugado! Conseguimos arrumar depois de um tempo, mas a essa altura algumas submissões não tinham sido registradas e outras estavam com o tempo incorreto.

Decidimos verificar o bug, mas como o placar está em python, e eu não sei quase nada dessa linguagem, acabamos desistindo. Outra ideia era reescrever um placar simples em C++, mas fazer o parse de uma página de HTML ia dar muito trabalho. Felizmente o SPOJ armazena, para cada usuário, um log de suas submissões em modo texto. Isso tornou viável implementar o placar em C++ com a adicional vantagem de podermos  contabilizar todas as submissões dos competidores, sem perder nenhuma e como o tempo correto.

Demoramos umas 3 horas para finalizar o placar e enquanto isso o pessoal foi usando o placar bugado. Depois de 4 horas de prova ainda congelamos o placar, de modo que o pessoal só teve acesso ao placar correto por uma hora :(

Gostaria de deixar meus agradecimentos para o Marcelo, que me indicou a maioria dos problemas da seletiva, e ao staff (também chamados de “melancias” na maratona): a Annelise, o Carlos e o Pedro.

Dos competidores

O placar final foi o seguinte:

  1. Paulo Costa
  2. Igor Ribeiro de Assis
  3. Davi Barbosa (nao elegivel)
  4. Douglas Santos
  5. Bruno Espinosa Crepaldi
  6. Ruan Silva
  7. Mauro Lopes
  8. Thiago Cavalcante
  9. Igor Wolff
  10. Alex Fernando Brandt
  11. Rodrigo Bustamante Magalhaes
  12. Rafael Carneiro
  13. Douglas Fonseca
  14. Jose Americo de Freitas
  15. Marcos Torres
  16. Alex Lucchesi de Oliveira

O coach e os três primeiros colocados

O Paulo e o Igor dominaram a prova de ponta a ponta, alternando suas posições ocasionalmente. Para se ter uma ideia, com cerca de uma hora de prova, o Igor já tinha resolvido 5 problemas. O Davi  também foi bem, mas estava participando apenas por diversão pois não é mais elegível. A disputa pelo quarto lugar foi interessante, principalmente depois que o placar congelou. O Douglas Santos estava em 4º, com 4 problemas, até congelar o placar. Logo que isso aconteceu, o Bruno passou mais um problema, empatando em número de problemas, mas ultrapassou o Douglas pois tinha menor penalidade. Faltando menos de 10 minutos para o término da prova o Douglas conseguiu passar mais um problema. Lembre que como o Davi não era elegível, ficar com o quarto lugar representava estar no primeiro time.

A revelação foi o Ruan, bixo da Engenharia de Computação, que vinha treinando desde o primeiro semestre e fazendo os problemas do placar. Por um bom tempo ele ficou em quarto, mas acabou ficando preso em um dos problemas, o que pode tê-lo prejudicado. O Mauro, era o único competidor dos que tinham ido para a final brasileira do ano passado. Ele não foi tão bem quanto esperava e preferiu desistir da vaga. Além deles, o Thiago e o Igor Wolff, outro bixo, também fizeram 3 problemas. O Alex ficou com 2, Rodrigo, Rafael e Douglas Fonseca fizeram 1 e infelizmente o José Américo, Marcos e Alex Oliveira não conseguiram fazer nenhum problema.

Dos problemas

Escolhemos os seguintes problemas do SPOJ, que estão na ordem em que apareceram no placar:

Escolhi Common Permutation, Find the Clones para serem os problemas mais fáceis da prova, seguidos por The Last Digit e Bug’s Life. O problema Prime Path era um pouco mais complicado, mas achei que mais pessoas fariam. O problema Transmitters, NERED e o Flipping Burned Pancakes foram escolhidos com intuito de separar o primeiros colocados do resto. O Can you answer these queries III era de longe o problema mais difícil e só decidimos colocar para ninguém fechar a prova muito cedo :P De fato, ninguém resolveu esse problema.


Dijkstra e o caminho máximo

Agosto 13, 2010

O problema do caminho mínimo é um dos problemas mais conhecidos da computação. Nesse post, vou comentar um pouco sobre o problema do caminho mínimo e também do caminho máximo, apresentando modelos de PLI para ambos. Para simplificar, vou considerar apenas as instâncias onde o grafo é direcionado e os pesos nas arestas são positivos.

O problema dos caminhos mínimos pode ser modelado como fluxo em redes. Mais especificamente, pode ser reduzido para o problema do fluxo de custo mínimo. Assim, existe naturalmente um algoritmo polinomial para resolvê-lo. Porém, da mesma forma que existem algoritmos combinatórios para o fluxo máximo e o fluxo de custo mínimo, o algoritmo de Dijkstra resolve o problema dos caminhos mínimos de maneira muito eficiente. O algoritmo foi desenvolvido por Edsger Dijkstra em 1956 tomando café em um bar. Disse o autor em uma entrevista que levou 20 minutos para desenvolver um dos algoritmos mais famosos do mundo da computação.

Claramente um algoritmo que resolva o problema dos caminhos mínimos através de programação linear não será capaz de bater a eficiência do algoritmo de Dijkstra. Mas, para fins de modelagem, vou apresentar o modelo PLI desse problema. A redução para o problema do fluxo máximo de custo mínimo é simples: basta fazer com que o fluxo máximo seja igual a 1. O modelo completo fica:

(1) Para cada nó v do grafo que não a fonte ou o sorvedouro,

(2) Para cada aresta (ij),

(3) Para cada aresta (ij),

(4)

Desta forma, temos que todo vale 0 ou 1. Devido à conservação do fluxo, as arestas com formam um caminho de s a t. Além do mais, o valor da função objetivo consiste em minimizar o custo das arestas desse caminho, justamente a definição do menor caminho.

Caminho de custo máximo

Um problema semelhante ao do caminho de menor custo é o problema do caminho de maior custo. Uma possível aplicação para esse problema é a técnica de planejamento CPM (Critical Path Method). O CPM consiste em construir um grafo direcionado com vértices correspondendo às atividades e arestas representando as dependências entre elas (ou seja, se existe uma aresta a->b, então b só pode ser executada depois que a terminar). A cada atividade está associado um custo, que é seu tempo de execução. Observe que aqui, o custo está associado a um vértice, e não a uma aresta. Isso pode ser resolvido através de uma modificação no grafo: para cada vértice v, substitua-o por vértice v’ e v’, com uma aresta v’-> v”com o custo igual ao do vértice. Para toda aresta (v,u), criamos a aresta (v”,u) e para toda aresta (u,v), criamos a aresta (u,v’) (veja a figura abaixo).

Split de um vértice para transformar custo do vértice em custo da aresta

Outra característica desse grafo é que ele é acíclico. Assim, é possível resolvê-lo em tempo polinimial através de programação dinâmica. Porém, para um grafo geral, o problema do caminho máximo é NP-completo.

Há uma característica que garante a integralidade (ou seja, que a solução do PL coincide com a do PLI) de modelos de programação linear, que é chamada de unimodularidade total. Se a matriz de coeficientes das restrições de um programa linear satisfizer certas condições, ela é dita totalmente unimodular. Isso implica que o problema que foi modelado com esse programa linear pode ser resolvido em tempo polinomial. Dois exemplos de matrizes que possuem essa estrutura são as matrizes de coeficientes dos PL’s do problema do fluxo máximo e do fluxo máximo de custo mínimo. Isso quer dizer que a matriz do PL do caminho de custo mínimo é unimodular. À primeira vista, isso parece implicar que o problema do caminho máximo pode ser resolvido em tempo polinomial, já que é só mudar a função objetivo de minimização pra maximização e, já que não modificamos a matriz de restrições, a unimodularidade total é mantida.

O problema é que não basta apenas modificar a função objetivo para que o PL resolva o problema do caminho de custo máximo. Se fizermos apenas isso, vão aparecer ciclos direcionados de custo positivo, disjuntos do caminho de s a t, já que queremos maximizar a função objetivo. Na figura abaixo, as arestas coloridas formam uma solução viável, já que ciclos (em vermelho) respeitam a conservação de fluxo. Supondo que a capacidade das arestas seja 1, o custo total da solução abaixo é 51; O maior caminho nesse grafo tem custo 33, que é maior do que o caminho encontrado em verde (ou seja, não basta jogar fora os ciclos encontrados). No problema do caminho mínimo eles não vão aparecer e por isso o modelo é válido.

Uma solução viável para o modelo com maximização

Assim, é preciso usar restrições que eliminem ciclos, o que faz com que a matriz de restrições deixe de ser totalmente unimodular. Para eliminá-los, definimos variáveis auxiliares, , associadas aos vértices. A seguinte restrição, elimina ciclos direcionados:

(5) Para cada aresta (i,j), seja M um número suficientemente grande

Se passa fluxo por uma aresta, a restrição fica,

O que implica que . Caso contrário, a desigualdade fica,

que é sempre satisfeita, tornando-a redundante.

Para ver que tal desigualdade elimina ciclos, considere um ciclo direcionado no grafo com os vértices na seguinte ordem (repeti o último vértice para explicitar que é um ciclo), corforme a figura seguinte.

Ciclo direcionado

Se houver fluxo passando por esse ciclo direcionado, a desigualdade (5) vai forçar que , ou seja , o que não pode acontecer. É fácil ver que tal desigualdade não impede a formação do caminho s-t. Basta ir atribuindo valores crescentes para u ao longo do caminho.


Modelos de Programação Linear: Fluxo em Redes

Agosto 6, 2010

Muitos problemas de otimização combinatória podem ser modelados como problemas de fluxo em rede. Revisando um pouco, uma rede de fluxo é um grafo direcionado onde cada aresta tem uma capacidade e um fluxo associados. O fluxo na aresta não pode ultrapassar sua capacidade. Além disso, um fluxo deve satisfazer a restrição de conservação de fluxo, ou seja, a quantidade de fluxo que entra em um vértice é a mesma que sai, com exceção de um nó fonte (denotado por s), de onde só sai fluxo e um nó sorvedouro (denotado por t) de aonde só entra fluxo. Vamos apresentar um modelo que representa essas restrições. A cada aresta (ij), associamos uma variável representando o fluxo que passa por ela. Seja sua capacidade.

Rede com capacidades não-inteiras

 

(1) Para cada nó v do grafo que não a fonte ou o sorvedouro,

(2) Para cada aresta (ij),

(3) Para cada aresta (ij),

O lado esquerdo da igualdade (1) representa o somatório do fluxo de todas as arestas que entram em v e o lado direito o somatório do fluxo de todas as arestas que saem de v. Em outras palavras, é a restrição de conservação de fluxo. A desigualdade (2) é a restrição da capacidade do fluxo e (3) é para mostrar que o fluxo não pode ser negativo.

Analogia com dutos: capacidade e conservação de fluxo

Existe uma versão mais eficiente do algoritmo Simplex para resolver fluxos em rede (network simplex). Além disso, alguns dos problemas que podem ser modelados como fluxo em rede possuem algoritmos combinatórios (ou seja, algoritmos específicos para resolvê-los de maneira mais eficiente do que através de programação linear). A seguir vou apresentar dois exemplos para os quais foram desenvolvidos algoritmos combinatórios: o problema do fluxo máximo e o problema do fluxo máximo de custo mínimo.

Fluxo Máximo

Se adicionarmos uma função objetivo para maximizar a quantidade total de fluxo que sai da fonte (que por sinal é o mesmo que chega no sorvedouro), ou seja,

(4)

Temos o modelo linear do problema do fluxo máximo. O algoritmo mais simples para resolvê-lo é o ford-fulkerson, com complexidade , onde |f| é o valor do fluxo máximo (ou seja, esse algoritmo é pseudo-polinomial) e um dos mais eficientes é um baseado numa técnica chamada Push-relabel, com complexidade .

Fluxo Máximo de Custo Mínimo

Se além da capacidade, as arestas tiverem custo associado , podemos considerar a seguinte função objetivo:

(5)

Porém, se os custos forem positivos, obviamente a melhor solução seria não passar nenhum fluxo. Por isso, temos que fixar que o fluxo que passa pela rede tenha um valor fixo d,

(6)

Tal problema é chamado de fluxo de custo mínimo. No caso em que d é o maior valor de fluxo possível, temos o problema do fluxo máximo de custo mínimo. Para este problema existe o algoritmo por cancelamento de ciclos, com complexidade , onde U e C são respectivamente a capacidade máxima e o custo máximo de alguma aresta, sendo este portanto um algoritmo pseudo-polinomial. O mais eficiente algoritmo até hoje é de o duplo-escalanamento (escalonamento de custo e capacidade) que é , sendo assim fortemente polinomial [2].

Conclusão

Esses modelos em particular possuem a propriedade de que se as capacidades da rede forem inteiras, o fluxo máximo também será. Ou seja, mesmo que x possa assumir valores reais, na solução ótima ela será inteira. Desta forma, a solução ótima do PLI (x inteira) e do PL (x real) coincidem. Assim, esse é um típico caso em que um PLI pode ser resolvido em tempo polinomial.

Para uma referência mais abrangente, consulte o livro do Ahuja, Magnanti e Orlin [1].

Referências:

[1] Ravindra K. Ahuja, Thomas L. Magnanti, and James B. Orlin (1993). Network Flows: Theory, Algorithms, and Applications.
[2] Advanced Algorithms MIT – Minimum cost maximum flow, Minimum cost circulation, Cost/Capacity scaling