Solving the Coarseness Problem by ILP Using Column Generation

Autor(es):Mostrar menos -

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

• Tipo de documento: Artigo Científico
• Fonte: COMPUTATIONAL SCIENCE AND ITS APPLICATIONS, ICCSA 2021, PT V; v. 12953, p. 16-pg., 2021-01-01.

Resumo

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)

• Processo FAPESP: 14/12236-1 - AnImaLS: Anotação de Imagem em Larga Escala: o que máquinas e especialistas podem aprender interagindo?
• Beneficiário: Alexandre Xavier Falcão
• Modalidade de apoio: Auxílio à Pesquisa - Temático
• Processo FAPESP: 18/26434-0 - Algoritmos exatos e heurísticos para solução de problemas difíceis relacionados a geometria computacional
• Beneficiário: Pedro Jussieu de Rezende
• Modalidade de apoio: Auxílio à Pesquisa - Regular
• Processo FAPESP: 18/14883-5 - Problemas geométricos de decomposição
• Beneficiário: Allan Sapucaia Barboza
• Modalidade de apoio: Bolsas no Brasil - Doutorado Direto