Modelos Matemáticos para o Problema da Poligonização de Área Máxima

Autores

  • Raí Caetano de Jesus
  • Fábio L. Usberti

DOI:

https://doi.org/10.5540/03.2018.006.02.0303

Palavras-chave:

Poligonização, Área Máxima, Programação Linear Inteira, Matheuristic

Resumo

O problema do caixeiro viajante, do ponto de vista geométrico, tem por objetivo encontrar um polı́gono simples sobre um dado conjunto de vértices cujo perı́metro é mı́nimo. É possı́vel derivar o problema de modo que o objetivo seja encontrar um polı́gono simples cuja área interna seja máxima: trata-se do problema de poligonização de área máxima. Este é um problema de otimização combinatória NP-difı́cil com aplicações práticas em segmentos como reconhecimento de padrões, reconstrução de imagens, clusterização e robótica. Este trabalho apresenta dois modelos matemáticos de programação linear inteira. Experimentos computacionais foram executados para comparar as metodologias propostas com um algoritmo 12 -aproximado da literatura. Os modelos matemáticos propostos mostram a dificuldade de resolver de maneira exata o problema de poligonização de área máxima, encontrando soluções ótimas em uma hora somente para as instâncias de 10 pontos, em um conjunto de instâncias de até 50 pontos.

Downloads

Não há dados estatísticos.

Downloads

Publicado

2018-12-19

Edição

Seção

Trabalhos Completos