.png){kind=icon}
.png){kind=icon}
Return
Integer programming models and polyhedral study for the geodesic classification problem on graphs
.png){kind=icon}
OA
AI
DOI：10.1016/j.ejor.2023.08.029.png)
.png){kind=icon}
.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
We study a discrete version of the classical classification problem in Euclidean space, to be called the geodesic classification problem. It is defined on a graph, where some vertices are initially assigned a class and the remaining ones must be classified. This vertex partition into classes is grounded on the concept of geodesic convexity on graphs, as a replacement for Euclidean convexity in the multidimensional space. We propose two new integer programming models along with branch-and-bound algorithms to solve them. We also carry out a polyhedral study of the associated polyhedra, which produced families of facetdefining inequalities and separation algorithms. Finally, we run computational experiments to evaluate the computational efficiency and the classification accuracy of the proposed approaches by comparing them with classic solution methods for the Euclidean convexity classification problem. (c) 2023 Elsevier B.V. All rights reserved.
Keywords:
Combinatorial optimization
Classification
Geodesic convexity
Polyhedral combinatorics
Integer programming
AI Summary
Key information extracted from the uploaded paper, including a brief overview, abstract, background, key highlights, visual analysis, and future outlook.
Journal
IF:
6
Papers:
2.2W
Citations:
6.4W
View more organizations