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: