Esta série de oficinas tem como intuito promover o estudo e desenvolvimento de técnicas avançadas nas áreas de otimização, combinatória e teoria da computação. Acreditamos que com estas oficinas, possamos nos inteirar sobre os novos desenvolvimentos em nossa área de conhecimento e expandir os horizontes da pesquisa em algoritmos, combinatória e otimização na Unicamp.

Cada edição da OALOCo aborda um tema específico dentro das áreas de interesse do laboratório. Este tema será trabalhado pelos participantes da oficina através da apresentação informal de artigos e resultados existentes na literatura relacionada ao tema da oficina, além de mesas redondas de discussão sobre os trabalhos apresentados e colaboração nos moldes clássicos de workshops acadêmicos.

O tema desta segunda edição da OALOCo será o método de Decomposição de Benders para problemas de otimização.

Em 1962, J. F. Benders propôs uma nova técnica para resolver problemas de Programação Inteira Mista de maneira exata mais eficientemente. Sua abordagem baseava-se na reformulação do modelo original através da fixação temporária de variáveis complicadoras. Mais de 50 anos depois, esta técnica, que passou a ser conhecida como Decomposição de Benders, fora estendida e generalizada para casos além da Programação Inteira Mista, e seu interesse tem crescido progressivamente nos últimos anos. Em seu Invited Review para o European Journal of Operational Research, Rahmaniani, Crainic, Gendreau e Rei descrevem Decomposição de Benders da seguinte forma:

"Primeiramente o modelo original é projetado em um subespaço definido por um conjunto de variáveis complicadoras. A formulação resultante é então dualizada e os raios e pontos extremos definem condições de viabilidade (cortes de viabilidade) e os custos projetados (cortes de otimalidade) das variáveis complicadoras respectivamente. Assim, uma formulação equivalente pode ser construída baseando-se na enumeração destes raios e pontos extremos. Este novo modelo é então resolvido através de uma estratégia de relaxação dos cortes de viabilidade e otimalidade, resultando em um Problema Mestre e um subproblema (separação)."

Convidamos todos os pesquisadores e estudantes interessados em Decomposição de Benders e suas aplicações a participar de nossas discussões.

2o. Semestre de 2018 - Variable Neighbourhood Search (VNS)