Advanced search
Start date

Solving the Coarseness Problem by ILP Using Column Generation

Full text
Show less -
Sapucaia, Allan ; de Rezende, Pedro J. ; de Souza, Cid C. ; Gervasi, O ; Murgante, B ; Misra, S ; Garau, C ; Blecic, I ; Taniar, D ; Apduhan, BO ; Rocha, AMAC ; Tarantino, E ; Torre, CM
Total Authors: 13
Document type: Journal article
Source: COMPUTATIONAL SCIENCE AND ITS APPLICATIONS, ICCSA 2021, PT V; v. 12953, p. 16-pg., 2021-01-01.

A core problem in machine learning is the classification of points in high dimensions. In an attempt to minimize the resources required and facilitate data visualization, a recent effort has been made to project the points non-linearly onto the plane and apply classification methods. The quality of any such projection can be measured by evaluating how the resulting points of different classes are set apart. In this paper, we study integer linear programming (ILP) models to determine the coarseness of sets of bicolored points in the plane, which measures how well-separated these two classes are. The complexity of computing the coarseness of a point set is unknown, but conjectured to be NP-hard. We present a base ILP model for the problem with an exponential number of variables and constraints, followed by a series of improvements in the quality of its relaxation and close with an efficient column generation implementation. These modifications allow us to solve instances with three times as many points as the base model, within the same time and memory limits. By combining of our preprocessing techniques and a heuristic from the literature, we are even able to solve to proved optimality many instances of our benchmark in polynomial time. A comprehensive experimental study is presented to evaluate the impact of each improvement. (AU)

FAPESP's process: 14/12236-1 - AnImaLS: Annotation of Images in Large Scale: what can machines and specialists learn from interaction?
Grantee:Alexandre Xavier Falcão
Support Opportunities: Research Projects - Thematic Grants
FAPESP's process: 18/26434-0 - Exact and heuristic algorithms for solving difficult problems related to computational geometry
Grantee:Pedro Jussieu de Rezende
Support Opportunities: Regular Research Grants
FAPESP's process: 18/14883-5 - Geometric decomposition problems
Grantee:Allan Sapucaia Barboza
Support Opportunities: Scholarships in Brazil - Doctorate (Direct)