Defesa de Proposta de Tese: Paulo Henrique Macêdo de Araújo

Título: The Combinatorial Classification Problem - A Geodetic Convexity Classification Problem on Graphs

Data: 09/11/2018

Horário: 14:00h

Local: Sala de Seminários - Bloco 952

Resumo:

Motivated by the significant advances in integer optimization in the past decade, Bertsimas and Shioda developed a integer optimization method to the classical statistical problem of classification in a multidimensional space, delivering a software package called CRIO (Classification and Regression via Integer Optimization). Following those ideas, we define a new classification problem, exploring its combinatorial aspects, that is defined on graphs using geodetic convexity as a analogy of the euclidean convexity in the multidimensional space. We call such a problem by Combinatorial Classification Problem (CCP). We propose integer programming based approaches for CCP along with resolution methods based on branch-and-bound algorithms. We also show a polyhedral study of the polyhedrons associated to each integer formulation proposed and some valid inequalities with separation algorithms for them. Computational experiments results and comparison between the approaches to evaluate their combinatorial optimization efficiency are also presented.

Banca:

  • Prof. Dr. Manoel Bezerra Campêlo Neto (MDCC/UFC - Orientador)
  • Prof. Dr. Ricardo Cordeiro Corrêa (UFRRJ - Coorientador)
  • Prof. Dr. Rafael Castro de Andrade (MDCC/UFC)
  • Prof. Dr. Carlos Diego Rodrigues (UFC)