Informativo

Alunos de Ciência da Computação estão no pódio no I Desafio Mercado Livre de Otimização

A equipe formada pelos alunos André Luiz Feijó dos Santos e Pedro Fiorio Baldotto, da turma de 2021, estão entre as três finalistas do I Desafio Mercado Livre de Otimização, que faz parte LVII Simpósio Brasileiro de Pesquisa Operacional (SBPO 2025). A classificação final das equipes será divulgada durante o SBPO, em Gramado/RS, no início de outubro.

O desafio foi proposto e coordenado pelo Mercado Livre em colaboração com a Sociedade Brasileira de Pesquisa Operacional (SOBRAPO) e trata um problema de otimização conhecido como Problema da Seleção de Pedidos Ótima (SPO), que se origina de aplicações práticas na logística de e-commerce. Em resumo, o SPO requer a seleção de um subconjunto dos pedidos de clientes que estão aguardando processamento em um armazém, cujos itens devem ser coletados do estoque antes de serem embalados e despachados para entrega. O armazém é organizado em corredores, cada um deles contendo quantidades determinadas dos itens em estoque. O subconjunto escolhido, denominado de wave, deve maximizar a métrica de produtividade medida pela razão entre o total de itens presentes nos pedidos da wave e o número de corredores selecionados para coletar esses itens. Além disso, o total de itens dos pedidos que fazem parte da wave deve respeitar limites mínimos e máximos decorrentes de restrições operacionais.

O desafio ocorreu em 3 etapas e contou com mais de 50 equipes, de até três estudantes, de diversas instituições brasileiras e da América Latina. A equipe formada por André e Pedro foi a campeã da primeira etapa (Sprint), quando as equipes receberam 20 casos de teste, com diferentes tamanhos e características, e também foi campeã da segunda etapa (de qualificação), que contou com 35 casos de testes, mais desafiadores que os da etapa sprint.

Segundo a equipe, na primeira etapa os resultados foram obtidos por um algoritmo exato que combinava modelos de programação linear inteira mista com cálculos de limites inferiores e superiores e técnicas de busca binária. Já na segunda etapa foram adicionadas técnicas heurísticas, dada a maior complexidade dos casos de teste. Um artigo científico com a descrição desses métodos foi aceito para apresentação no SBPO, onde ocorrerá a divulgação final dos resultados da última etapa. O resultado da etapa final foi divulgado na página do evento, mas não revela a ordem das 3 equipes no topo. Os detalhes de pontuação das demais são mostrados para cada caso de teste, mas a classificação final do Top 3 será divulgada durante o evento, em Gramado.

Os alunos participantes deste desafio comentaram que:

“O desafio foi uma grande oportunidade de pôr em prática técnicas de otimização e programação que aprendemos ao longo do curso. Inicialmente, tentamos propor um modelo não-linear que resolvesse todo o problema de uma vez só, mas logo vimos que, para instâncias maiores, isso era inviável. A estratégia fundamental para os resultados que obtivemos foi dividir um problema grande e difícil em vários probleminhas menores e mais fáceis e resolvê-los em paralelo.”
— André Feijó

“O problema proposto é bastante desafiador, pois envolve essencialmente duas camadas de otimização. Ao longo do desafio, nosso entendimento sobre a natureza do problema evoluiu, e fomos capazes de identificar potenciais aplicações de técnicas aprendidas ao longo do curso. Após várias rodadas de tentativa e erro e surgimento de novas ideias, nossa solução foi sendo aprimorada de forma iterativa.”
— Pedro Fiorio

Pedro Fiorio (esquerda) e André Feijó (direita)