Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
13430498 | Electronic Notes in Theoretical Computer Science | 2019 | 12 Pages |
Abstract
Motivated by the significant advances in integer optimization in the past decade, Bertsimas and Shioda developed an 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 problem is defined on graphs using the geodesic convexity as an analogy of the Euclidean convexity in the multidimensional space. We denote such a problem by Geodesic Classification (GC) problem. We propose an integer programming formulation for the GC problem along with a branch-and-cut algorithm to solve it. Finally, we show computational experiments in order to evaluate the combinatorial optimization efficiency and classification accuracy of the proposed approach.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Paulo Henrique Macêdo de Araújo, Manoel Campêlo, Ricardo C. Corrêa, Martine Labbé,