H. Hernández Pérez, J. Riera Ledesma, I. Rodríguez Martín, J. J. Salazar Gonzalez
Optimal area polygonization problems consist of finding the polygon with the optimal area (maximum or minimum) generated from a set of points that correspond to the vertices of that polygon. This paper focuses with simple (without holes) polygons in the plane.
We present three models based in triangulations of the polygon (or the triangulations the convex hull of set of points minus the polygon). We design branch-and-cut algorithms based in these mathematical models.
Extensive computational results on benchmark instances shown that second and third model have better computational results than the previous models from the literature. However, while the third model is better for the problem of maximizing area, the second model is better for the problem of minimizing area.
Keywords: Polygonization, Computational Geometry, Integer Programming, Branch-and-cut, Traveling Salesman Problem.
Scheduled
Integer and Combinatorial Optimization
November 7, 2023 3:30 PM
HC1: Canónigos Room 1