The Optimal Area Polygonization Problem: A Benders Decomposition Approach

Á. García Muñoz, H. Hernández Pérez, J. J. Salazar González

The Optimal Area Polygonization (OAP) problem consists of finding a simple polygon that minimizes or maximizes the area enclosed by a given set of points in the Euclidean plane. Currently, several compact Mixed-Integer Linear Programming (MILP) formulations exist for this problem, one of which can solve almost all instances of up to 50 points (vertices). We propose this study with the aim of scaling larger problem sizes. Accordingly, this work proposes a Benders Decomposition approach that exploits the structural interdependence between the Hamiltonian cycle and the inner and outer triangulations. The main contribution is the analysis of the feasibility cuts that arise from the Benders' decomposition. Studying the extreme rays of the dual subproblem allows us to identify cuts that strengthen the linear relaxation. A branch-and-cut algorithm is presented, wherein these cuts are dynamically introduced to reduce the gap of the relaxed problem and solve larger-scale instances.

Keywords: Optimal Area Polygonization, Benders' Decomposition, Mixed-Integer Linear Programming, MILP, Branch-and-Cut, Computational Geometry, Combinatorial Optimization, Hamiltonian Cycle, Feasibility Cuts

Integer and Combinatorial Optimization
September 2, 2026  5:40 PM
Aula 24

C. Hernández Barrueco, A. Meca Martínez, J. L. Sainz-Pardo Auñón

D. Morillo-Torres, J. Prias, L. Salcedo

C. Parreño-Torres, J. Romero-del-Hombrebueno

I. Rodríguez Acevedo, J. González Díaz, B. González Rodríguez, A. Barros González