Empacotamento Orientado ao Vazio

Resumo:

Neste seminário eu apresentarei uma nova estratégia para empacotar caixas iguais em containers retangulares. (Esse é o Pallet Loading Problem, ou PLP, para o qual não há nem algoritmo polinomial nem prova de NP-hardness.)

As abordagens usuais para o PLP tentam posicionar as caixas eficientemente. Entretanto, eu creio que a estrutura das soluções ótimas do PLP é melhor descrita pelas áreas que ficam vazias. Essa crença é motivada pelo que eu observo na interface de um software que desenvolvi para explorar o PLP e é confirmada por teoremas que relacionam a estrutura das soluções ótimas à localização dos vazios.

Eu iniciarei o seminário apresentando o software citado acima. Mostrarei como a observação das soluções ótimas leva naturalmente ao estudo dos vazios. Em seguida ilustrarei como o teorema de Bezout fornece informações sobre as soluções ótimas do PLP, ressaltando a relação entre o PLP e a teoria de números. Demonstrarei então como o software incorpora essas informações.

Finalmente, especularei que o PLP é basicamente um problema de satisfabilidade. Argumentarei que o empacotamento orientado ao vazio relaciona o PLP ao Mine Sweeper, aquele jogo do windows para o qual há uma prova de NP-Completude baseada em uma redução do problema de satisfabilidade.