Palestras – O Programa de Pós-Graduação em Modelagem Computacional convida para as seguintes palestras:

Marcio Costa Santos

(Professor, Universidade Federal de Minas Gerais)

Data: 28/02/2024

Horário: 14:00

Local: Auditório do DCC/Engenharia Computacional/Estatística

Dado um grafo G=(V,E), o problema da coloração de Grundy consiste em encontrar uma atribuição de cores a cada um de seus vértices de forma que vértices adjacentes recebam cores diferentes, e as regras da heurística gulosa first-fit sejam respeitadas. Tais regras implicam que uma dada cor, exceto a de menor índice, só pode ser utilizada para um vértice se todas as outras cores de índice inferior estiverem presentes na sua vizinhança. Uma solução que maximiza o número de cores define o número de Grundy de um grafo, o qual fornece um limite de pior caso para o desempenho da abordagem gulosa first-fit para o conhecido problema da coloração de vértices. Nesta apresentação vamos falar de formulações de programação inteira para o problema, assim como heurísticas evolutivas para esse problema. Ademais, avaliamos como critérios gulosos bem conhecidos para o problema da coloração se comportam quando comparados com as soluções obtidas para o problema da coloração de Grundy.

Bio: Possui graduação e mestrado em ciência da computação pela Universidade Federal do Ceará (2010) e doutorado pela Universidade de Tecnologia de Compiègne(2016). Atuou como pós-doc na Universidade Federal da Bahia e na Universidade Livre de Bruxelas. Foi professor na campus avançado de Russas da Universidade Federal do Ceará e hoje é professor no departamento de ciência da computação da Universidade Federal de Minas Gerais. Tem experiência na área de ciência da computação, com ênfase em combinatória e complexidade computacional. Áreas de interesse englobam: teoria dos grafos, teoria poliédrica, otimização combinatória e robusta. Atualmente trabalha com problemas focados em coloração de grafos.

Michaël Poss

(Pesquisador Sênior, CNRS, LIRMM laboratory)

Data: 28/02/2024

Horário: 15:00

Local: Auditório do DCC/Engenharia Computacional/Estatística

Given a nominal combinatorial optimization problem, we consider a robust two-stages variant with polyhedral cost uncertainty, called DDID. In the first stage, DDID selects a subset of uncertain cost coefficients to be observed, and in the second-stage, DDID selects a solution to the nominal problem, where the remaining cost coefficients are still uncertain. Given a compact linear programming formulation for the nominal problem, we provide a mixed-integer linear programming (MILP) formulation for DDID. The MILP is compact if the number of constraints describing the uncertainty polytope other than lower and upper bounds is constant. In that case, the formulation leads to polynomial-time algorithms for DDID when the number of possible observations is polynomially bounded. We extend this formulation to more general nominal problems through column generation and constraint generation algorithms. We illustrate our reformulations and algorithms numerically on the selection problem, the orienteering problem, and the spanning tree problem.

Bio: Michaël Poss is a senior research fellow at the CNRS, in the LIRMM laboratory. He obtained his PhD degree in 2011 at the Université Libre de Bruxelles. After his thesis, he spent a couple of months at the Universidade de Aveiro, followed by a postdoctoral stay at the CMUC from the Universidade de Coimbra. He was recruited at the CNRS in 2012, in the Heudiasyc lab. His current research focuses mainly on robust combinatorial optimization. He is the founding managing editor of the Open Journal of Mathematical Optimization (https://ojmo.centre-mersenne.org/).