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.


Integer and Combinatorial Optimization
November 7, 2023  3:30 PM
HC1: Canónigos Room 1

Other papers in the same session

Solving the container premarshalling problem considering crane availability constraints

C. Jiménez Piqueras, D. Pacino, C. Parreño Torres, R. Álvarez Valdés

A multiobjective SHARP holistic model

F. Martos-Barrachina, L. Delgado-Antequera, M. Hernández, R. Caballero

Cookie policy

We use cookies in order to be able to identify and authenticate you on the website. They are necessary for the correct functioning of it, and therefore they can not be disabled. If you continue browsing the website, you are agreeing with their acceptance, as well as our Privacy Policy.

Additionally, we use Google Analytics in order to analyze the website traffic. They also use cookies and you can accept or refuse them with the buttons below.

You can read more details about our Cookie Policy and our Privacy Policy.