The Optimal Area Polygonization Problem: A Benders Decomposition Approach
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.
Palabras clave: Optimal Area Polygonization Benders' Decomposition Mixed-Integer Linear Programming MILP Branch-and-Cut Computational Geometry Combinatorial Optimization Hamiltonian Cycle Feasibility Cuts