Otimização Não-Linear

Projeto Prático

O objetivo do presente projeto é aplicar o conhecimento adquirido durante a discplina em uma aplicação prática para visualização de resultados de busca na web.

A execução será divida nas seguintes etapas:

1. Simulação dos dados
2. Modelagem matemática do problema
3. Solução numérica
4. Visualização dos resultados
5. Elaboração de relatório

Abaixo é descrito o esperado em cada uma dessas etapas.

Simulação dos dados

Os dados do modelo devem ser posições espaciais dos resultados de busca, as dimensões dos retângulos associados a cada um desses pontos e associações de agrupamento de conjuntos desses pontos. A sugestão de execução da simulação é a seguinte:

1. Escolher aleatoriamente um número de grupos entre 3 e 7
2. Para cada grupo escolher um número de pontos entre 5 e 15
3. Para cada grupo escolher uma posição para seu centro
4. Distribuir os pontos aleatoriamente em torno do centro do grupo (certifique-se de fazer com que haja pouca sobreposição entre os pontos de distintos grupos)
5. Para cada ponto $j$ gerar tamanhos horizontais $h_j$ e verticais $v_j$ ambos entre 2 e 4

Após os dados serem gerados, uma coleção de retângulos no plano será obtida, juntamente com informação sobre agrupamento desses retângulos.

Modelagem matemática do problema

Nesta etapa deverá ser seguido o modelo sugerido em https://ieeexplore.ieee.org/abstract/document/6629989 em que é minimizada uma soma da forma $$ (1 - \alpha) E_O + \alpha E_N, $$ onde $\alpha \in [ 0, 1 ]$, $E_O$ refere-se à taxa de sobreposição de retângulos e $E_N$ mede o quanto a solução atual distorce a estrutura de vizinhanças dos dados originais.

As variáveis de decisão para a minimização são as posições finais de cada um dos retângulos onde seriam exibidos resultados de busca textual na web.

Solução numérica

O modelo obtido acima deverá ser resolvido utilizando-se de método numérico apropriado. A implementação pode ser qualquer uma desejada pelo aluno, desde que o relatório forneça as referências apropriadas. O método numérico utilizado deve ser descrito em termos gerais.

Diversas instâncias devem ser geradas, e o resultado numérico deve ser sumarizado com detalhes relevantes do procedimento numérico (tempo de execução, valor final da função objetivo, etc.)

Visualização dos resultados

Uma vez que o resultado final da otimização fornecerá as posições ideais de diversos retângulos, a visualização desses resultados deve ser simples. Ao menos uma das soluções finais deve ser ilustrada no relatório.

Elaboração de relatório

O relatório deverá conter detalhes da modelagem, implementação e resultados em um documento PDF. Este relatório deverá ser entregue em conjunto com todos os documentos e códigos fontes utilizados para a realização do projeto. A entrega se dará em um arquivo compactado (.zip, .rar ou .tar.gz) através do escaninho de um dos alunos do sistema TidiaAe até as 23:59 dia 09 de novembro de 2020.