Experimentos Numéricos

O programa foi codificado primeiramente em C e depois foi traduzido para Fortran77. Usamos a opção do compilador ``-O4''.

Olhando para o minimizador global do problema de decisão (veja Figura ) usamos $N$ = 100000, que significa que rodamos o método de 100000 pontos iniciais aleatórios ou até encontrarmos um minimizador global (detectado pelo seu custo ótimo igual a zero).

Para cada tentativa $t$ (veja Figura ) os pontos iniciais foram gerados como se segue. Pontos aleatórios $r^i \in I\!\!R^2$ foram gerados dentro da região convexa do problema. Os números aleatórios foram gerados na seguinte ordem: $r_x^1, r_y^1, r_x^2, r_y^2, \ldots$. O gerador de números aleatórios de Schrage [39] (versão double precision) com semente $t$ foi usado para gerar números aleatórios independemente de máquina.

Resolvemos alguns problemas usando diferentes métodos:

• usando o método do vetor;
• usando o método das restrições;
• usando o método da distância entre os centros;
• usando o método do vetor com uma configuração inicial gerada pelo método das circunferências;
• usando o método das restrições com uma configuração inicial gerada pelo método das circunferências;
• usando o método da distância entre os centros com uma configuração inicial gerada pelo método das circunferências;

Para o método das circunferências, cobrimos os retângulos de diveras maneiras:

• usando o que foi descrito, tentando cobrir totalmente o retângulo;
• colocamos 6 circunferências: 4 circunferências de raio $0$, um em cada vértice e 2 circunferências de raio $w/2$, um em cada lado do retângulo, onde $w$ é o menor lado do retângulo;
• colocamos 2 circunferências de raio $w/2$, um em cada lado do retângulo, onde $w$ é o menor lado do retângulo;
• colocamos apenas 1 circunferência de raio $w/2$, no centro do retângulo, onde $w$ é o menor lado do retângulo

Com os resultados gerados, concluímos que desses métodos, o que resultou em melhores resultados foi o método da distância entre os centros dos retângulo com uma configuração inicial gerada pelo método das circunferências usando apenas uma circunferência.

A partir dessa conclusão, resolvemos todos os problemas de empacotar retângulos em regiões convexas que foram resolvidas em [6] e mais alguns exemplos usando esse método. Os problemas estão definidos nas Tabelas - . Nas tabelas são dados o número do problema, a região convexa, a dimensão do retângulo, o número de retângulos que foi possível empacotar em [6] e usando modelos contínuos. As soluções são dadas nas Figuras 1-34.