lo
U NIVERSIDADE F EDERAL DE G OIÁS
I NSTITUTO DE I NFORMÁTICA
Mo
de
S ANTIAGO VALDÉS R AVELO
Modelos Matemáticos e Algoritmos
para Problemas Combinatórios
Goiânia
2011
U NIVERSIDADE F EDERAL DE G OIÁS
I NSTITUTO DE I NFORMÁTICA
AUTORIZAÇÃO PARA P UBLICAÇÃO DE D ISSERTAÇÃO
EM
F ORMATO E LETRÔNICO
Na qualidade de titular dos direitos de autor, AUTORIZO o Instituto de
Informática da Universidade Federal de Goiás – UFG a reproduzir, inclusive em outro
formato ou mídia e através de armazenamento permanente ou temporário, bem como a
publicar na rede mundial de computadores (Internet) e na biblioteca virtual da UFG,
entendendo-se os termos “reproduzir” e “publicar” conforme definições dos incisos VI
e I, respectivamente, do artigo 5o da Lei no 9610/98 de 10/02/1998, a obra abaixo
especificada, sem que me seja devido pagamento a título de direitos autorais, desde que
a reprodução e/ou publicação tenham a finalidade exclusiva de uso por quem a consulta,
e a título de divulgação da produção acadêmica gerada pela Universidade, a partir desta
data.
Título: Modelos Matemáticos e Algoritmos para Problemas Combinatórios –
Autor(a): Santiago Valdés Ravelo
Goiânia, 18 de Fevereiro de 2011.
Santiago Valdés Ravelo – Autor
Dr. Cláudio Nogueira de Meneses – Orientador
S ANTIAGO VALDÉS R AVELO
Modelos Matemáticos e Algoritmos
para Problemas Combinatórios
Dissertação apresentada ao Programa de Pós–Graduação do
Instituto de Informática da Universidade Federal de Goiás,
como requisito parcial para obtenção do título de Mestre em
Ciências da Computação.
Área de concentração: Otimização Combinatória.
Orientador: Prof. Dr. Cláudio Nogueira de Meneses
Goiânia
2011
S ANTIAGO VALDÉS R AVELO
Modelos Matemáticos e Algoritmos
para Problemas Combinatórios
Dissertação defendida no Programa de Pós–Graduação do Instituto
de Informática da Universidade Federal de Goiás como requisito parcial para obtenção do título de Mestre em Ciências da Computação,
aprovada em 18 de Fevereiro de 2011, pela Banca Examinadora constituída pelos professores:
Prof. Dr. Cláudio Nogueira de Meneses
Instituto de Informática – UFG
Presidente da Banca
Prof. Dr. Humberto José Longo
Instituto de Informática – Universidade Federal de Goiás
Prof. Dr. Reinaldo Morabito
Departamento de Engenharia de Produção – Universidade Federal de São Carlos
Todos os direitos reservados. É proibida a reprodução total ou parcial do
trabalho sem autorização da universidade, do autor e do orientador(a).
Santiago Valdés Ravelo
Graduou-se Ciências da Computação na Universidade da Havana, Cuba
(2007). Durante sua graduação foi monitor no departamento de Matemática
Aplicada da Faculdade de Matemática e Ciências da Computação da Universidade da Havana e membro do grupo de pesquisa deste departamento.
Fez iniciação científica desenvolvendo modelos matemáticos e implementado algoritmos para localizar o centro de furacões tropicais, que resultou em
um software para o Intituto de Meteorologia de Cuba. Atualmente, cursa o
mestrado na Universidade Federal de Goiás e trabalha na área de otimização
combinatória, estudando diferentes problemas para os que propõe modelos
matemáticos e projeta vários algoritmos.
A Fernan, quem sempre será meu irmãozinho.
Agradecimentos
Gostaria de expressar minha gratidão ao meu orientador, o professor Cláudio
Nogueira de Meneses, por ter confiado em mim e dar-me a oportunidade de crescer como
cientista. Sem sua orientação, paciência e estímulo, este trabalho não teria sido finalizado.
Sou muito grato aos professores Humberto José Longo e Maristela Oliveira dos
Santos, por seus conselhos e auxílios.
Meu sincero agradecimento aos meus pais que me deram uma educação excepcional, não só em conhecimentos senão também em valores humanos.
Quero agradecer as minhas tias e especialmente a minha avó pelo constante apoio
que me deram.
Também sou grato ao pessoal da secretaria e da coordenação da pós-graduação
do INF-UFG, pela ajuda que me ofereceram durante o mestrado.
Agradeço aos meus amigos, colegas de classe, e todas aquelas pessoas que de
uma forma ou outra me ajudaram, apoiaram ou confiaram em mim.
Muito obrigado a todos vocês.
Não existem métodos fáceis para resolver problemas difíceis
René Descartes,
.
Resumo
Ravelo, Santiago Valdés. Modelos Matemáticos e Algoritmos para Problemas Combinatórios. Goiânia, 2011. 94p. Dissertação de Mestrado. Instituto
de Informática, Universidade Federal de Goiás.
Este trabalho considera três problemas, NP-difíceis, relevantes de estudo em otimização
combinatória. O primeiro deles é o problema de corte uni-dimensional de objetos,
onde o material não usado pelos padrões de corte pode ser usado no futuro. Para este
problema analisamos os modelos matemáticos existentes, propomos novos modelos,
projetamos uma heurística construtiva e duas metaheurísticas, sendo seus desempenhos
melhorados com programação paralela, e resolvemos instâncias, práticas e aleatórias,
encontradas na literatura; sendo os experimentos computacionais muito bons para todas as
intâncias testadas. O segundo problema que consideramos é o problema dos companheiros
estáveis (stable roommates problem), uma variante do problema de emparelhamento
estável (stable matching problem). Para este propomos dois modelos matemáticos, uma
implementação sequencial e uma paralela de uma Tabu Search, e um Branch-andBound. Também reportamos experimentos computacionais para instâncias do problema.
O último problema considerado é o da mochila compartimentada (uma generalização do
problema clássico da mochila), para o qual analisamos uma modelagem quadrática inteira
e propomos um modelo linear inteiro; também projetamos uma heurística gulosa, um
algoritmo GRASP, que usa path-relinking, e resolvemos intâncias geradas aleatóriamente.
Todas as implementações em paralelo usam unidades de processamento gráfico (Graphics
Processing Units, GPUs).
Palavras–chave
Otimização Combinatória, Problema de Corte, Stable Matching Problem, Problema da Mochila, Modelos Matemáticos, Heurísticas.
Abstract
Ravelo, Santiago Valdés. Mathematical Models and Algorithms to Combinatorial Problems. Goiânia, 2011. 94p. MSc. Dissertation. Instituto de Informática, Universidade Federal de Goiás.
This work considers three relevant NP-hard problems. The first one is the one-dimensional
cutting stock problem in which the non-used material in the cutting patterns may be used
in the future. For this problem we analyze the existing mathematical models, propose new
models, design a heuristic and two metaheuristic approaches, being their performances
improved by using parallel programming, and solve instances, practical and randomly
generated, from the literature. The computational experiments were quite good for all
tested instances. The second problem we consider is the stable roommates problem (a
variant of the stable matching problem). For this we give two mathematical programming
models, sequential and parallel implementations of a Tabu Search, and a Branch-andBound. Also, we report computational experiments to instances of the problem. The
last problem we consider is the compartmentalized knapsack problem (a generalization
of the knapsack problem) for which we analyze a quadratic integer model and give a
linear integer model. We design a greedy heuristic and a GRASP algorithm, that uses
path-relinking, and solve randomly generated instances. All parallel implementations use
Graphics Processing Units (GPUs).
Keywords
Combinatorial Optimization, Cutting Problem, Stable Matching Problem, Knapsack Problem, Mathematical Models, Heuristics.
Sumário
Lista de Figuras
11
Lista de Tabelas
12
Lista de Algoritmos
14
Lista de Códigos de Programas
15
1
Introdução
16
2
Problema de Corte Uni-dimensional de Objetos com Retalhos
19
20
2.1
2.2
Definição do Problema de Corte Uni-dimensional de Objetos com Retalhos
Modelos Matemáticos para o Problema de Corte Uni-dimensional de Objetos
com Retalhos
2.2.1
Modelos Matemáticos na Literatura para o Problema de Corte Uni-dimensional
com Retalhos
2.2.2
2.3
2.4
Novos Modelos Matemáticos para o CSPUL
Algoritmos
2.3.1
Heurística Construtiva
2.3.2
Algoritmo Baseado no GRASP
2.3.3
Metaheurística Baseada em Algoritmos Evolutivos
2.3.4
Processos Paralelos
Testes Computacionais
2.4.1
Instâncias
Instâncias Numéricas
Instâncias Práticas
Instâncias Aleatórias
2.4.2
Discussões sobre os Modelos Matemáticos
Discussões sobre as Instâncias Numéricas
Discussões sobre as Instâncias Práticas
2.4.3
Discussões sobre os Algoritmos
Discussões sobre as Instâncias Numéricas
Discussões sobre Instâncias Práticas
2.4.4
24
Discussões sobre Instâncias Aleatórias
Comparação com os Resultados de [6]
24
30
32
32
34
38
40
42
42
42
44
45
45
46
48
49
50
50
51
52
3
Problema de Emparelhamento Estável
3.0.5
3.1
3.2
3.3
3.4
3.5
4
Novos Modelos Matemáticos para o Problema dos Companheiros Estáveis
3.1.1
Novo Modelo Quadrático
3.1.2
Novo Modelo Linear Inteiro
Busca Tabu para o Problema dos Companheiros Estáveis
3.2.1
Forma Geral da Busca Tabu
3.2.2
Busca Tabu para o Problema dos Companheiros Estáveis
Branch-and-Bound para o Problema dos Companheiros Estáveis
3.3.1
Forma Geral do Branch-and-Bound
3.3.2
Branch-and-Bound para o Problema dos Companheiros Estáveis
3.3.3
Estratégias para Melhorar o Desempenho do Branch-and-Bound
Melhorando as Implementações com Programação Paralela em GPUs
Experimentos Computacionais
Problema da Mochila Compartimentada
4.1
4.2
4.3
4.4
5
Variantes
Modelo Quadrático do Problema da Mochila Compartimentada
4.1.1
Observações
4.1.2
Exemplo
Modelo Linear Inteiro para o Problema da Mochila Compartimentada
Algoritmos
4.3.1
Heurística Gulosa
4.3.2
GRASP usando Path-Relinking
Experimentos Computacionais
4.4.1
Instâncias
4.4.2
Resultados Computacionais
Conclusões
55
56
57
57
59
60
60
60
61
61
62
64
67
69
72
72
74
75
76
79
79
79
80
80
80
83
Referências Bibliográficas
84
A
Funções para Trabalhar com Vetores Inteiros na Memória das GPUs
87
B
Código dos Kernels Correspondêntes às Implementações Parallelas das
Heurísticas
88
C Código para Executar os Kernels
92
Lista de Figuras
2.1
2.2
2.3
2.4
Solução 1
Solução 2
Solução 3
No gráfico a solução ideal está nas coordenadas (50, 3), a aceitável em
(40, 3) e a indesejável em (66, 1). A solução ideal é dominada, enquanto
as soluções aceitável e indesejável são não-dominadas.
2.5 a), b) e c) mostram como permutando a ordem dos itens são gerados
diferentes padrões de corte usando um processo similar ao FFD.
2.6 Exemplo de execução da Heurística Construtiva (os padrões verdes são
os incluídos na solução)
2.7 Este exemplo mostra como o movimento para criar melhores padrões
consegue uma solução com uma perda de comprimento 1cm e um retalho
a partir de uma solução com três perdas, cada uma de comprimento 1cm
(o que é 3cm de perda total) e um retalho.
2.8 Nas tabelas, as filas Valores, Itens e Número, respectivamente, representam os valores que podem ser obtidos como combinações lineares dos
itens, o tipo de item que chega no valor, e o número de itens desse tipo
necessários para chegar nesse valor. Quando adicionamos um padrão de
corte na solução, o vermelho indica o tamanho do objeto que será cortado
e os itens do padrão estão em verde.
2.9 Os valores obtidos por RGRL 1, RGRL 2 e RGRL 3 foram dominados, enquanto os valores obtidos por Const. H., GRASP BA e Evol. BA foram
não-dominados
2.10 Os resultados do GRASP BA foram dominados, enquanto os do Const.
H., RSHP e Evol. BA foram não-dominados
3.1
4.1
4.2
22
22
23
24
33
35
37
43
53
54
Os valores dentro dos vértices indicam o candidato livre que foi selecionado para gerar os subproblemas desse nó, enquanto os valores das
arestas são os candidatos livres que foram associados com o selecionado
para gerar o subproblema. As folhas mostram o último par de candidatos
emparelhados e é apressentada a solução associada à folha.
64
Padrão compartimentado não ótimo
Padrão compartimentado ótimo
75
76
Lista de Tabelas
2.1
2.2
2.3
2.4
2.5
2.6
2.7
2.8
2.9
2.10
2.11
2.12
2.13
2.14
2.15
2.16
2.17
2.18
2.19
2.20
2.21
2.22
2.23
3.1
3.2
4.1
Labels e seus significados.
Comprimentos e demandas dos itens da instância numérica 1
Comprimentos e demandas dos itens da instância numérica 2
Comprimentos e demandas dos itens da instância numérica 3
Comprimentos e demandas dos itens da instância prática 1
Comprimentos e demandas dos itens da instância prática 2
Instâncias aleatórias
Resultados do CPLEX com a instância numérica 1. O * indica que a
solução é ótima.
Resultados do CPLEX para o modelo 1 com a instância numérica 2.
Resultados do CPLEX para os modelos 2 e 3 com a instância numérica 2.
Resultados do CPLEX para o modelo 4 com a instância numérica 2. O *
indica que a solução é ótima.
Resultados do CPLEX com a instância prática 1. O * indica que a solução
é ótima.
Resultados do CPLEX para os modelos 1 e 2 com a instância prática 2. O
* indica que a solução é ótima.
Resultados do CPLEX para os modelos 3 e 4 com a instância prática 2. O
* indica que a solução é ótima.
Sementes para a geração de números pseudo-aleatórios
Soluções para a instância numérica 1. O * indica que a solução é um
ótimo de Pareto.
Soluções para a instância numérica 2. O * indica que a solução é um
ótimo de Pareto.
Soluções para a instância numérica 3.
Soluções para a instância prática 1. O * indica que a solução é um ótimo
de Pareto.
Soluções para a instância prática 2. O * indica que a solução é um ótimo
de Pareto.
Resultados com instâncias aleatórias.
Resultados com instâncias aleatórias.
Comparação com [6]
Soluções do CPLEX e das variantes do Branch-and-Bound. O (*) indica
que todas as soluções da classe foram ótimas.
Soluções da Busca Tabu. O (*) indica que todas as soluções da classe
foram ótimas.
Dados dos itens do exemplo
42
43
44
44
45
45
46
47
47
47
48
48
49
49
49
50
50
51
51
52
52
53
53
70
70
75
4.2
4.3
4.4
4.5
Parâmetros fixos para todas as intâncias
Parâmetros aleatórios para todas as intâncias
Descrição das classes de instâncias
Soluções para o Problema da Mochila Compartimentada
81
81
82
82
Lista de Algoritmos
2.1
2.2
2.3
2.4
2.5
2.6
3.1
3.2
3.3
3.4
Heurística Construtiva
Forma geral do GRASP
Algoritmo baseado no GRASP
Forma geral de um algoritmo evolutivo
Metaheurística Baseada em Algoritmos Evolutivos
Processo para construir os dados auxiliares para o problema da mochila.
Forma geral da Busca Tabu.
Busca Tabu para o Problema dos Companheiros Estáveis.
Forma Geral do Branch-and-Bound
Algoritmo para calcular o limite inferior de um nó a partir do limite inferior
do pai. Note que para este algoritmo ser O(n), deve ser pré-calculada uma
estrutura que permita saber para cada candidato livre quais dos restantes
candidatos livres ele prefere; o processo para calcular isto tem um custo
computacional de O(n2 ).
3.5 Processo de seleção do nó a ser explorado
3.6 Busca local aumentando a vizinhança
3.7 Primeira fase do processo para obter uma solução inicial para a busca local
3.8 Segunda fase do processo para obter uma solução inicial para a busca local
3.9 Processo guloso para obter uma solução inicial viável para a busca local
3.10 Método modificado de seleção do nó a ser explorado
4.1 Heurística Gulosa para o problema da Mochila Compartimentada
4.2 Forma geral do Path-relinking
4.3 Algoritmos baseado no GRASP e no Path-relinking
34
35
36
38
39
41
61
62
63
65
65
66
66
67
68
68
79
80
81
Lista de Códigos de Programas
A.1 Funções para Trabalhar com Vetores Inteiros na Memória
das GPUs
B.1 Kernels da Heurística Construtiva para o Problema de
Corte com Retalhos
B.2 Kernels do Algoritmo Baseado em GRASP para o Problema de
Corte com Retalhos
B.3 Kernels do Algoritmo Baseado em GRASP para o Problema de
Corte com Retalhos
B.4 Kernel do Algoritmo Baseado em Processos Evolutivos para
o Problema de Corte com Retalhos
C.1 Código para Executar os Kernels
C.2 Código para Executar os Kernels
C.3 Código para Executar os Kernels
87
88
89
90
91
92
93
94
CAPÍTULO 1
Introdução
A área de otimização combinatória é repleta de problemas de interesse prático.
Neste trabalho consideramos três destes problemas. Para cada um deles propomos novos
modelos matemáticos, assim como diferentes algoritmos heurísticos com suas implementações em paralelo usando unidades de processamento gráfico.
O primeiro problema estudado é um caso particular de problemas de corte de
objetos. Estes têm muitas aplicações na indústria e consistem no corte de um conjunto
de objetos maiores, que estão no estoque, para satisfazer certas demandas de itens, tendo
como possíveis objetivos, dentre outros, minimizar a perda de material e o custo dos objetos cortados. Em geral, estes problemas são difíceis de solucionar computacionalmente,
pertencendo uma boa parte deles à classe NP-difícil. Nós consideramos o problema de
corte uni-dimensional com retalhos, neste caso se a perda de material gerada no corte de
um objeto é suficientemente grande, então ela é considerada um retalho que será levado
em conta em futuros planejamentos de corte. Esta característica introduz maior complexidade ao problema e tem recebido atenção na literatura. Vários pesquisadores propuseram
modelos matemáticos e algoritmos para esse problema, ver referências [1, 5, 11, 12, 13],
com o intuito de encontrar boas soluções.
O segundo problema considerado é o problema dos companheiros estáveis
(stable roommates problem), que é uma subclasse dos problemas de emparelhamento
com preferêcias. Algumas das aplicações destes são: alocar médicos em treinamento em
hospitais, estudantes em moradias no campus e pacientes a possíveis doadores, entre
outras. Uma subclasse dos problemas de emparelhamento são os de emparelhamento
estável, introduzida por D. Gale e L.S. Shapley em College admissions and the stability
of marriage (1962) com o problema do casamento estável e dos companheiros estáveis.
O terceiro problema estudado é o problema da mochila compartimentada (que é
uma generalização do problema clássico da mochila). Este tipo de problema tem muitas
aplicações: cortar objetos maiores (bobinas, placas) para produzir itens menores, ou empacotar pequenos itens em espaços definidos. O problema da mochila compartimentada
consiste em dado um conjunto de itens agrupados em diferentes classes para serem alocados em uma mochila, onde itens de classes diferentes devem estar em compartimentos
17
diferentes da mochila, objetiva-se determinar as capacidades adequadas de cada compartimento e como estes devem ser carregados. Em [30], F.P. Marques e M.N. Arenales
introduzem o problema da mochila compartimentada.
Nos últimos anos as unidades de processamento gráfico (Graphics Processing
Units, GPUs) evoluíram de simples geradores de tela em poderosas plataformas programáveis, e em constraste com CPUs, as GPUs foram projetadas especificamente para
computações em paralelo. Assim, em teoria, as GPUs têm maior poder computacional
que as CPUs. Sendo esta a razão pela qual as GPUs têm sido usadas para melhorar o
desempenho de algoritmos que solucionam problemas não gráficos ([7, 24]).
Nas arquiteturas de computadores atuais, os espaços de memória da CPU e das
GPUs são diferentes. Isto significa que se um processo vai ser executado nas GPUs,
então, necessariamente, os dados requeridos por ele deverão ser copiados da memória da
CPU para os das GPUs e consequentemente os dados resultantes do processo deverão ser
copiados das memórias das GPUs para a da CPU. Assim, para obter um bom desempenho,
deve ser pouca a transferência de dados entre os diferentes espaços de memória e, por
outro lado, os processos selecionados para serem paralelizados devem ser aqueles que
consumem maior tempo computacional.
Para finalizar, as principais contribuições deste trabalho são:
• Para o Problema de Corte de Objetos Uni-dimensional com Retalhos:
– Dois novos modelos matemáticos;
– Três novos algoritmos heurísticos: uma heurística construtiva, um algoritmo
baseado no GRASP e um algoritmo evolutivo;
– Implementações em paralelo de processos para melhorar o desempenho das
heurísticas.
• Para o Problema dos Companheiros Estáveis:
–
–
–
–
Dois novos modelos matemáticos;
Uma metaheurística Busca Tabu;
Duas variantes do Branch-and-Bound;
Implementações em paralelo de processos para melhorar o desempenho dos
algoritmos propostos.
• Para o Problema da Mochila Compartimentada:
– Análise de um modelo quadrático;
– Proposta de um modelo em programação linear inteira;
– Uma heurística gulosa e uma metaheurística híbrida que usa GRASP com
path-relinking.
A dissertação é organizada como segue: no capítulo 2 são analisados modelos
e definições para o problema de corte uni-dimensional com retalhos, junto com novos
18
modelos matemáticos, projetos de três algoritmos heurísticos com processos em paralelo
para melhorar o desempenho dos mesmos e resultados computacionais. No capítulo
3 são apresentados dois modelos para o problema dos compaheiros estáveis, também
são projetadas uma busca tabu e adaptações do Branch-and-Bound para esse problema,
com testes computacionais comparando implementações sequenciais e paralelas. No
capítulo 4 são discutidos diferentes modelos matemáticos para o problema da mochila
compartimentada e também são propostas uma heurística gulosa, baseada em soluções do
problema clássico da mochila e uma metaheurística, baseada no GRASP que usa pathrelinking. As conclusões são dadas no capítulo 5.
CAPÍTULO 2
Problema de Corte Uni-dimensional de Objetos
com Retalhos
Os problemas de corte de objetos estão presentes nas mais variadas situações
práticas de processos industriais, como produção de papel, móveis, vidro, plástico,
calçados, roupas, chapas metálicas, circuitos impressos, entre outros. Estes problemas
consistem em cortar unidades maiores (unidades em estoque) em unidades menores
(unidades demandadas) de maneira a otimizar certos objetivos, como por exemplo:
minimizar o número de unidades em estoque necessárias para produzir as unidades
demandadas ou minimizar a perda de material quando são arranjadas geometricamente
as unidades demandadas dentro das unidades em estoque.
Neste capítulo consideramos um caso particular do problema de corte unidimensional de objetos, no qual o material que sobra dos cortes, se for suficientemente
grande, pode ser usado no futuro. Esta característica introduz dificuldade ao problema e
tem sido tratada na literatura por meio da criação de modelos matemáticos e projetos de
algoritmos para obter boas soluções ([1, 5, 6, 11, 12, 13]).
Os primeiros a considerar a existência de retalhos no problema de corte foram
Gradisar et al. em [11], ao propor um modelo aplicado à indústria têxtil e uma abordagem
de resolução heurística para o problema. O estudo em [12] é uma continuação daquele
começado em [11], neste caso considerando instâncias onde todos os objetos no estoque
são diferentes. O modelo matemático de [11] foi analisado e uma outra heurística foi
projetada.
Em [13] foi definido um novo algoritmo que combina as ideias de um Branchand-Bound com heurísticas sequenciais, melhorando as propostas de [11, 12].
Em [1] são apresentados dois modelos matemáticos para o problema de corte
uni-dimensional, que considera a existência de retalhos aplicado ao planejamento de corte
uni-dimensional de tubos metálicos na indústria aeronáutica agrícola. Estes modelos são
baseados no modelo anteriormente proposto em [11, 12, 13]. Os modelos foram resolvidos, por meio de uma linguagem de modelagem usando um software de otimização, sobre
instâncias práticas obtidas da empresa brasileira Neiva/Embraer.
2.1 Definição do Problema de Corte Uni-dimensional de Objetos com Retalhos
20
Em [5] são propostos critérios de qualidade de uma solução do problema de corte
uni-dimensional com retalhos. Também foram projetadas e implementadas heurísticas
determinísticas e os resultados obtidos foram comparados com os de [11]. Em [6] foi
proposta uma heurística e os resultados computacionais foram comparados com os de [5]
sobre intâncias aleatórias.
Este capítulo é organizado como segue. Na seção 2.1 são vistas definições para o
problema de corte uni-dimensional de objetos com retalhos. Na seção 2.2 são analisados
os modelos matemáticos para este problema e propostos novos modelos matemáticos.
A seção 2.3 apresenta uma heurística construtiva, um algoritmo baseado no GRASP
e um algoritmo evolutivo, com alguns processos em paralelo usados para melhorar
o desempenho dos algoritmos. A seção 2.4 mostra os testes computacionais usando
instâncias da literatura (práticas, numéricas e aleatórias).
2.1
Definição do Problema de Corte Uni-dimensional de
Objetos com Retalhos
Em [5] o problema de corte uni-dimensional de objetos com retalhos (onedimensional Cutting Stock Problem with Usable Leftover (CSPUL)) é definido como:
Um conjunto de peças (itens) tem que ser produzido cortando unidades maiores (objetos) de tamanho padrão (objetos dos fornecedores) ou não-padrão (retalhos de cortes
anteriores). A demanda dos itens e a quantidade de objetos no estoque são dados. Devese satisfazer a demanda cortando os objetos no estoque de forma que se gerem perdas
“pequenas” ou “suficientemente grandes” (retalhos) que retornarão ao estoque mas em
número reduzido.
A definição do problema usada nesta dissertação é similar a dada acima, porém
procura-se minimizar o número de retalhos no estoque. Isto é, o CSPUL é definido
como: Um conjunto de peças (itens) tem que ser produzido cortando unidades maiores
(objetos) de tamanho padrão (objetos dos fornecedores) ou não-padrão (retalhos de
cortes anteriores). A demanda dos itens e a quantidade de objetos no estoque são dadas.
Deve-se satisfazer a demanda cortando os objetos no estoque de forma que se gerem
perdas “pequenas” ou “suficientemente grandes” (retalhos) que retornarão ao estoque,
com o objetivo de reduzir o número final de retalhos no estoque.
Os valores para definir pequeno e suficientemente grande são definidos pelo
usuário. Assim, podem ser usados os parámetros β, θ e δ para definir esses valores:
• β ∈ (0, 1): usado para saber se uma sobra de material de um objeto padrão é
considerada pequena, para isto o comprimento da sobra deve ser menor ou igual
a βL, sendo L o comprimento do objeto.
2.1 Definição do Problema de Corte Uni-dimensional de Objetos com Retalhos
21
• θ ∈ (0, 1): usado para saber se uma sobra de material de um objeto não-padrão é
considerada pequena, para isto o comprimento da sobra deve ser menor ou igual a
θL, sendo L o comprimento do objeto.
• δ ∈ R∗+ : usado para saber se uma sobra é suficientemente grande para ser considerada retalho, para isto o comprimento da sobra deve ser maior ou igual a δ.
Este problema é multi-objetivo, pois além de minimizar a perda de material
procura-se minimizar o número de retalhos no estoque. Para classificar as soluções, em
[5] foi proposta a seguinte definição para uma solução ser ideal, aceitável ou indesejável.
Uma solução é considerada:
• Ideal: quando tem poucos objetos que geram perdas pequenas, nenhum objeto gera
perda de tamanho intermediário (scrap of intermediate size) (isto é, uma perda que
não é considerada nem pequena nem retalho) e muito poucos objetos que geram
retalhos.
• Aceitável: quando tem poucos objetos que geram perdas de tamanho intermediário
e poucos objetos que geram retalhos.
• Indesejável: quando tem muitos objetos que geram perdas de tamanho intermediário
ou muitos objetos que geram retalhos.
Na definição anterior os termos muito pouco, pouco e muito são dados pelo
usuário. Isto pode ser feito usando os parâmetros ε1 e ε2 , onde 0 < ε1 < ε2 < 1. Assim o
número de objetos com certa caraterística em uma solução é considerado:
• muito pouco: quando é menor ou igual a dε1 ηe,
• pouco: quando não é muito pouco e é menor ou igual a dε2 ηe,
• muito: quando é maior que dε2 ηe,
onde η é o número total de objetos usados na solução. O objetivo de usar estas definições
é gerar soluções ideais ou pelo menos aceitáveis.
Estas definições dão um tipo de classificação para as soluções, porém, em geral,
há instâncias com soluções aceitáveis melhores que soluções ideais. Ainda, encontramos
soluções indesejáveis que são tão boas quanto as ideais. Isto é visto no seguinte exemplo.
Considere a anstância:
• O estoque contém 200 objetos padrões todos com comprimento de 1000cm;
• Deve-se gerar três tipos de itens:
– 9 itens de comprimento 300cm;
– 903 itens de comprimento 100cm;
– 67 itens de comprimento 99cm.
• Sendo: β = 0.005, δ = 99, ε1 = 0.03, ε2 = 0.1.
2.1 Definição do Problema de Corte Uni-dimensional de Objetos com Retalhos
22
Consideremos as soluções 1, 2 e 3, a seguir:
Solução 1: (Figure 2.1)
Figura 2.1: Solução 1
• três objetos são cortados gerando cada um: três itens de comprimento 300cm e um
item de comprimento 100cm. Isto é, 3 × (3 × 300 + 100) = 3 × 1000.
• dez objetos são cortados gerando cada um: cinco itens de comprimento 100cm,
cinco itens de comprimento 99cm e uma perda pequena de comprimento 5cm. O que
produz uma perda total de 50cm. Isto é, 10 × (5 × 100 + 5 × 99) = 10 × (1000 − 5).
• dois objetos são cortados gerando cada um: quatro itens de comprimento 100cm,
cinco itens de comprimento 99cm e um retalho de comprimento 105cm. Isto é,
2 × (4 × 100 + 5 × 99) = 2 × (1000 − 105).
• Um objeto é cortado gerando dois itens de comprimento 100cm, sete itens de
comprimento 99cm e um retalho de comprimento 107cm. Isto é, 2 × 100 + 7 × 99 =
1000 − 107.
• 84 objetos são cortados gerando cada um: dez itens de comprimento 100cm. Isto é,
84 × (10 × 100) = 84 × 1000.
Solução 2: (Figure 2.2)
Figura 2.2: Solução 2
• três objetos são cortados gerando cada um: três itens de comprimento 300cm e um
item de comprimento 100cm. Isto é, 3 × (3 × 300 + 100) = 3 × 1000.
• 20 objetos são cortados gerando cada um: oito itens de comprimento 100cm, dois
itens de comprimento 99cm e uma perda pequena de comprimento 2cm. O que
produz uma perda total de 40cm. Isto é, 20 × (8 × 100 + 2 × 99) = 20 × (1000 − 2).
• três objetos são cortados gerando cada um: nove itens de comprimento 99cm e um
retalho de comprimento 109cm. Isto é, 3 × (9 × 99) = 3 × (1000 − 109).
2.1 Definição do Problema de Corte Uni-dimensional de Objetos com Retalhos
23
• 74 objetos são cortados gerando cada um: dez itens de comprimento 100cm. Isto é,
74 × (10 × 100) = 74 × 1000.
Solução 3: (Figure 2.3)
Figura 2.3: Solução 3
• três objetos são cortados gerando cada um: três itens de comprimento 300cm e um
item de comprimento 100cm. Isto é, 3 × (3 × 300 + 100) = 3 × 1000.
• 11 objetos são cortados gerando cada um: quatro itens de comprimento 100cm, seis
itens de comprimento 99cm e uma perda de tamanho intermediário de comprimento
6cm. O que produz uma perda total de 66cm. Isto é, 11 × (4 × 100 + 6 × 99) =
11 × (1000 − 6).
• Um objeto é cortado gerando seis itens de comprimento 100cm, um item de
comprimento 99cm e um retalho de comprimento 301cm. Isto é, 6 × 100 + 99 =
1000 − 301.
• 85 objetos são cortados gerando cada um: dez itens de comprimento 100cm. Isto é,
85 × (10 × 100) = 85 × 1000.
Cada uma das soluções fez 100 cortes e de acordo com a classificação das
soluções tem-se que a solução 1 é ideal, a 2 é aceitável e a 3 é indesejável. Não obstante,
o total de material perdido pela segunda solução é 40cm, menor que os 50cm perdidos
pela primeira solução, tendo as duas soluções 3 retalhos. Assim, podemos concluir que
uma solução aceitável (a segunda) é melhor que uma solução ideal (a primeira).
No caso da terceira solução, que é indesejável, apresenta só 1 retalho enquanto
a primeira gera um número maior de retalhos (3 retalhos). Sendo a diferença da perda
de material entre a terceira e a primeira soluções de 16cm, que pode ser considerada
desprezível comparada com o total de material cortado que é 100000cm. Desta forma
encontramos uma solução indesejável (a terceira) que é pelo menos tão boa quanto uma
ideal (a primeira). Além disto, existem instâncias para as quais não é possível encontrar
soluções ideais nem aceitáveis (veja as instâncias práticas da seção 2.4).
A figura 2.4 mostra a relação de dominância de Pareto entre as soluções 1, 2 e 3,
onde os objetivos considerados são a perda de material e o número de retalhos.
Pelas razões explicadas anteriormente, o nosso objetivo não será obter soluções
ideais e sim abordar o CSPUL como um problema multi-objetivo. Na seção que segue são
discutidos alguns modelos matemáticos para este problema.
2.2 Modelos Matemáticos para o Problema de Corte Uni-dimensional de Objetos com Retalhos
24
Figura 2.4: No gráfico a solução ideal está nas coordenadas
(50, 3), a aceitável em (40, 3) e a indesejável em
(66, 1). A solução ideal é dominada, enquanto as
soluções aceitável e indesejável são não-dominadas.
2.2
Modelos Matemáticos para o Problema de Corte Unidimensional de Objetos com Retalhos
2.2.1
Modelos Matemáticos na Literatura para o Problema de Corte
Uni-dimensional com Retalhos
No nosso conhecimento, o artigo de M. Gradisar et al. [11] é a primeira referência na literatura, que considera a existência de retalhos no problema de corte unidimensional de objetos. Dando assim a seguinte modelagem:
Dados:
•
•
•
•
•
•
•
m: número de objetos
d j : comprimento do objeto j (1 ≤ j ≤ m)
n: número de tipos de itens
si : comprimento dos itens de tipo i (1 ≤ i ≤ n)
bi : demanda dos itens de tipo i (1 ≤ i ≤ n)
UB: comprimento mínimo de uma sobra para ser considerada retalho
Y, M: constantes usadas para definir o número máximo de itens de tipos diferentes
gerados por um objeto
Variáveis:
•
•
•
•
•
xi j : número de itens de tipo i cortados do objeto j (1 ≤ i ≤ n e 1 ≤ j ≤ m)
δ j : sobra de material gerada pelo objeto j (1 ≤ j ≤ m)
∆i : demanda não satisfeita de itens de tipo i (1 ≤ i ≤ n)
t j : perda de material do objeto j (1 ≤ j ≤ m)
yi j : indica se um item de tipo i é cortado do objeto j (1 ≤ i ≤ n e 1 ≤ j ≤ m)
2.2 Modelos Matemáticos para o Problema de Corte Uni-dimensional de Objetos com Retalhos
25
• z j : indica se o objeto j é considerado na solução (1 ≤ j ≤ m)
Modelo:
n
min
∑ ∆i
[Demanda não Satisfeita]
(2-1)
∑ tj
[Perda de Material]
(2-2)
[Restrições de Mochila]
(2-3)
[Restrições de Demanda]
(2-4)
i=1
m
min
j=1
n
s.a :
∑ sixi j + δ j = d j
∀j
i=1
m
∑ xi j + ∆i = bi
∀i
∑ yi j ≤ Y ≤ M
∀j
j=1
n
(2-5)
i=1
(
tj =
(
yi j =
(
zj =
δ j , se z j = 1 e δ j < UB
0, c/c
0, se xi j = 0
1, c/c
∀j
∀i, j
0, se ∑ni=1 xi j = 0
1, c/c
(2-6)
(2-7)
∀j
(2-8)
Inteiros : xi j ≥ 0, δ j ≥ 0, t j ≥ 0, ∆i ≥ 0, yi j , z j ∈ {0, 1}
(1 ≤ i ≤ n e 1 ≤ j ≤ m)
O modelo anterior é bi-objetivo, as funções (2-1) e (2-2) procuram minimizar,
respectivamente, a demanda de itens não atendida e a perda de material. As restrições
(2-3) fazem com que a soma dos comprimentos dos itens cortados em um objeto seja
menor ou igual que o comprimento do objeto. Enquanto, as restrições (2-4) garantem que
o número de itens produzidos não seja maior que a demanda. Finalmente, as restrições
(2-5) limitam o número de itens diferentes que podem ser cortados em um objeto.
Em [12] e [13] o mesmo modelo foi estudado e novas variáveis foram incluídas,
junto com uma restrição que limita a um o número de retalhos maiores que o maior item.
Isto é:
m
∑ u j ≤ 1, onde: u j =
j=1
(
1, se δ j < d j e δ j > maxi si
0, c/c
Esta restrição não é considerada nesta dissertação, pois pode ser interessante ter
em uma solução poucos retalhos, mas, que sejam grandes.
2.2 Modelos Matemáticos para o Problema de Corte Uni-dimensional de Objetos com Retalhos
26
Em [1], modificou-se o modelo de [11] e foram propostas duas modelagens,
que incluíram as variáveis binárias w j (1 ≤ j ≤ m), empregadas para indicar se o objeto
j é usado na solução e não gera retalho. Na continuação mostramos os dois modelos
propostos (Modelo 1 and Modelo 2).
Modelo 1:
m
min
(2-9)
∑ tj
j=1
n
s.a :
∑ sixi j + δ j = d j
∀j
[Restrições de Mochila]
(2-10)
i=1
m
∑ xi j = bi
∀i
[Restrições de Demanda]
(2-11)
∑ xi j ≥ z j
∀j
[Restrições de Objetos]
(2-12)
[Restrições de Objetos]
(2-13)
[Máximo Número de Retalhos]
(2-14)
−z j + u j ≤ 0 ∀ j
[Restrições de Sobra]
(2-15)
wj +uj ≤ 1
[Restrições de Sobra]
(2-16)
[Restrições de Sobra]
(2-17)
δ j −UB ≥ −Mw j + ε ∀ j
[Restrições de Perda]
(2-18)
δ j −UB ≤ M(1 − w j ) ∀ j
[Restrições de Perda]
(2-19)
t j − Mw j ≤ 0
∀j
[Restrições de Perda]
(2-20)
t j − Mz j ≤ 0
∀j
[Restrições de Perda]
(2-21)
[Restrições de Perda]
(2-22)
[Restrições de Perda]
(2-23)
j=1
n
i=1
n
∑ xi j ≤ Mz j
∀j
i=1
m
∑ u j ≤ RUB
j=1
∀j
zj −wj −uj ≤ 0
tj −δj ≤ 0
∀j
∀j
δ j − t j + Mw j + Mz j ≤ 2M
∀j
δ j ,t j , xi j ≥ 0, xi j ∈ Z, z j , u j , w j ∈ {0, 1}
(1 ≤ i ≤ n e 1 ≤ j ≤ m)
Onde: UB = mini {si }, M = max j {d j } − UB, RUB é o limitante superior para o número
de retalhos em uma solução (foi sugerido RUB = 1), e ε é um número positivo que muda
o sinal da desigualdade (quando todos os valores são inteiros, foi sugerido ε = 1).
Este modelo considera só um objetivo que é minimizar a perda de material.
Sendo as restrições (2-12) e (2-13) as que garantem que z j = 1 se e somente se o objeto j
é considerado na solução. As restrições (2-14) forçam o número de retalhos ser menor ou
igual a RUB. Se um objeto é considerado na solução e tem sobra, então sua sobra é um
retalho ou uma perda de material, isto é garantido pelas restrições (2-15), (2-16) e (2-17).
2.2 Modelos Matemáticos para o Problema de Corte Uni-dimensional de Objetos com Retalhos
27
Enquanto as restrições (2-18), (2-19), (2-20), (2-21), (2-22) e (2-23) garantem que se a
sobra de um objeto considerado na solução não é um retalho, então é perda de material.
Modelo 2:
m
min
(2-24)
∑ tj
j=1
n
s.a :
∑ sixi j ≤ d j
∀j
[Restrições de Mochila]
(2-25)
[Restrições de Demanda]
(2-26)
[Máximo Número de Retalhos]
(2-27)
[Restrições de Sobras]
(2-28)
[Restrições de Sobras]
(2-29)
i=1
m
∑ xi j = bi
∀i
j=1
m
∑ u j ≤ RUB
j=1
n
d j z j − ∑ si xi j ≥ UBu j
∀j
i=1
n
d j z j − ∑ si xi j ≤ t j + Mu j
∀j
i=1
t j , xi j ≥ 0, xi j ∈ Z, u j , z j ∈ {0, 1} (1 ≤ i ≤ n e 1 ≤ j ≤ m)
O modelo 2 é muito parecido com o modelo 1, tentando as restrições (2-28) e (2-29)
expressar o mesmo conjunto de pontos que as restrições (2-12)-(2-23) do modelo 1.
Sendo qualquer solução viável do modelo 1, uma solução viável para o modelo 2, porém
o contrário não é verdadeiro. Isto é dado pela seguinte proposição.
Proposição 1. O conjunto de soluções viáveis do modelo 1 é um subconjunto
próprio do conjunto de soluções viáveis do modelo 2.
Demonstração:
Primeiramente será mostrado que o conjunto de soluções viáveis do modelo
1 é um subconjunto do conjunto de soluções viáveis do modelo 2. Para isto, seja
y = (x, z, u, w,t, δ) uma solução viável do modelo 1, a seguir é provado que y é também
uma solução viável do modelo 2:
Para y ser solução viável do modelo 2, deve satisfazer todas as restrições deste
modelo, assim analizemos cada uma dessas restrições:
• Restrições 2-25: ∑ni=1 si xi j ≤ d j ∀ j. Como y é solução viável do modelo 1 ela
satisfaz as restrições 2-10, dadas por: ∑ni=1 si xi j + δ j = d j ∀ j, onde δ j ≥ 0 ∀ j,
portanto resulta que y também satisfaz as restrições 2-25.
• Restrições 2-26: ∑mj=1 xi j = bi ∀i. Estas igualdades são exatamente as mesmas
restrições 2-11 do modelo 1, que y satisfaz por ser solução viavél desse modelo.
2.2 Modelos Matemáticos para o Problema de Corte Uni-dimensional de Objetos com Retalhos
28
• Restrição 2-27: ∑mj=1 u j ≤ RUB. Esta restrição é exatamente a mesma restrição 2-14
do modelo 1, que y satisfaz por ser solução viavél desse modelo.
• Restrições 2-28: d j z j − ∑ni=1 si xi j ≥ UBu j ∀ j. Como y é uma solução viável do
modelo 1, tem-se que y satisfaz a restrição 2-18, onde ∀ j:
δ j −UB ≥ −Mw j + ε
⇔
δ j + Mw j ≥ UB + ε ≥ UB
⇔
δ j u j + Mw j u j ≥ UBu j
(2-30)
Mas sendo que u j , w j são variáveis binárias das restrições 2-16, que são dadas
w j + u j ≤ 1, tem-se que em uma solução viável do modelo 1, w j u j = 0 para todo j.
Aplicando essa ideia em 2-30, tem-se que y satisfaz para todo j:
δ j u j ≥ UBu j
(2-31)
Das restrições 2-10 tem-se que para todo j, y satisfaz: δ j = d j − ∑ni=1 si xi j , portanto
a equação 2-31 fica:
n
d j u j − u j ∑ si xi j ≥ UBu j
(2-32)
i=1
Da restrição 2-15 tem-se que para todo j, y satisfaz: u j ≤ z j . Assim a restrição 2-32
pode ser substituida por:
n
d j z j − u j ∑ si xi j ≥ UBu j
(2-33)
i=1
A seguir é feita uma análise por casos que mostra que y satisfaz 2-28, para todo j:
– caso 1: Para os j em que u j = 0. Neste caso tem-se que a restrição 2-28 fica:
d j z j − ∑ni=1 si xi j ≥ 0, isto é garantido pelas restrições 2-10 e 2-13 do modelo
1. Portanto para os j em que u j = 0, y satisfaz 2-28.
– caso 2: Para os j em que u j = 1. Neste caso tem-se que a restrição 2-28 fica:
d j z j − ∑ni=1 si xi j ≥ UB, que é exatamente a forma em que fica a restrição 2-33
que y satisfaz. Assim, para os j em que u j = 1, y satisfaz 2-28.
• Restrições 2-29: d j z j − ∑ni=1 si xi j ≥ t j +Mu j
por casos:
∀ j. A análise destas restrições é feita
– caso 1: Para os j em que z j = 0. Neste caso a restrição 2-29 fica: − ∑ni=1 si xi j ≥
t j + Mu j , onde y satisfaz ∑ni=1 si xi j ≥ 0. Portanto − ∑ni=1 si xi j ≤ 0 e t j + Mu j ≥
0, o que implica que y satisfaz esta restrição para os j em que z j = 0.
2.2 Modelos Matemáticos para o Problema de Corte Uni-dimensional de Objetos com Retalhos
29
– caso 2: Para os j em que z j = 1. Como y é solução viável do modelo 1, y
satisfaz 2-23 para todo j:
δ j − t j + Mw j + Mz j ≤ 2M ⇔ δ j ≤ t j − Mw j − Mz j + 2M
Como z j = 1, então y satisfaz:
δ j ≤ t j − Mw j + M
⇔
δ j ≤ t j + M(1 − w j )
(2-34)
Note que, para todo j, y também satisfaz 2-10:
n
n
∑ sixi j + δ j = d j , daí tem-se que δ j = d j − ∑ sixi j
(2-35)
i=1
i=1
De 2-34 e 2-35 tem-se que y satisfaz:
n
d j − ∑ si xi j ≤ t j + M(1 − w j )
(2-36)
i=1
Sendo y solução viável do modelo 1, tem-se que y satisfaz 2-17:
zj −wj −uj ≤ 0 ⇔ zj −wj ≤ uj
Como z j = 1, então y satisfaz:
1−wj ≤ uj
(2-37)
De 2-36 e 2-37, tem-se que y satisfaz: d j − ∑ni=1 si xi j ≤ t j + Mu j , que é a
mesma restrição que 2-29 quando z j = 1. Assim está provado que para todo j,
com z j = 1, y satisfaz 2-29.
Desta forma tem-se que para todo j, y satisfaz 2-29.
Como y satisfaz todas as restrições do modelo 2, pode-se concluir que o conjunto
de soluções viáveis do modelo 1 é subconjunto do conjunto de soluções viáveis do modelo
2.
Para mostrar que o conjunto de soluções viáveis do modelo 1 é um subconjunto
próprio do conjunto de soluções viáveis do modelo 2, basta encontrar uma instância para
a qual o modelo 2 tenha uma solução viável que não seja solução viável do modelo 1. Para
isto, é considerada a seguinte instância: há somente um objeto no estoque, este objeto tem
tamanho 5cm, e a demanda é um único item de tamanho 2cm, de forma que não produza
retalhos (ou seja RUB = 0).
2.2 Modelos Matemáticos para o Problema de Corte Uni-dimensional de Objetos com Retalhos
30
Assim o modelo 2 para esta instância resulta em:
min
t1
s.a :
2x11 ≤ 5
x11 = 1
u1 ≤ 0
5z1 − 2x11 ≥ 2u1
5z1 − 2x11 ≤ t1 + Mu1
t1 , x11 ≥ 0, x11 ∈ Z, u1 , z1 ∈ {0, 1}
Note-se que uma solução para este modelo é: S = {u1 = 0, z1 = 1,t1 = 3, x11 = 1}.
Para S os valores de δ1 e w1 , correspondentes à mesma solução no modelo 1, são obtidos
pelas restrições 2-10 e 2-17 respectivamente, e resultam: δ1 = 3 e w1 = 1. Porém S não é
solução para o modelo 1 desta instância, pois não satisfaz a restrição de perda 2-19 que é:
δ1 − 2 ≤ M(1 − w1 ) ou seja 3 − 2 ≤ M(1 − 1). Portanto está provado com este exemplo
trivial que há soluções viáveis do modelo 2, que não são soluções viáveis do modelo 1. Estes modelos não solucionam exatamente o CSPUL, o que pode ser visto
analisando os objetivos dos modelos e do CSPUL, além de que não consideram os retalhos
que estão inicialmente no estoque. Porém trocado a função objetivo por
∑mj=1 d j z j
∑ t j + ∑m d j
j=1
j=1
m
conforme sugerido em [1], se dá prioridade aos objetos de menor tamanho,
considerando a minimização do número de retalhos como um objetivo secundário.
Na próxima subseção são propostos novos modelos para o CSPUL.
2.2.2
Novos Modelos Matemáticos para o CSPUL
Como o CSPUL minimiza o número de retalhos no estoque é necessário considerar os objetos que foram retalhos de cortes anteriores. Para isto é definido:
R: conjunto de objetos no estoque que foram retalhos de planejamentos de corte anteriores
(isto é, conjunto de objetos não-padrões).
Os modelos propostos em [1] permitem soluções simétricas, assim soluções
similares podem ser obtidas trocando os padrões de corte de objetos do mesmo tipo.
Com o objetivo de evitar algumas destas situações, propomos ordenar os objetos pelos
comprimentos e adicionar as seguintes restrições:
2.2 Modelos Matemáticos para o Problema de Corte Uni-dimensional de Objetos com Retalhos
z j+1 ≤ z j
∀j
31
se os objetos j e j + 1 são do mesmo tipo.
Assim reduzimos o número de soluções simétricas permitidas pelo modelo 2, e obtemos
o seguinte modelo.
Modelo 3:
m
min
(2-38)
∑ tj
j=1
m
min
∑ u j + ∑ (1 − z j )
j=1
n
s.a :
[Retalhos no Estoque]
(2-39)
[Restrições de Mochila]
(2-40)
[Restrições de Demanda]
(2-41)
[Restrições de Sobras]
(2-42)
[Restrições de Sobras]
(2-43)
j∈R
∑ sixi j ≤ d j
∀j
i=1
m
∑ xi j = bi
∀i
j=1
n
d j z j − ∑ si xi j ≥ UBu j
∀j
i=1
n
d j z j − ∑ si xi j ≤ t j + Mu j
∀j
i=1
z j+1 ≤ z j
∀ j se os objetos j e j + 1 são do mesmo tipo
(2-44)
t j , xi j ≥ 0, xi j ∈ Z, u j , z j ∈ {0, 1} (1 ≤ i ≤ n e 1 ≤ j ≤ m)
Porém, o modelo 3 ainda permite soluções simétricas, assim é proposto o modelo
4.
Dados do Modelo 4:
•
•
•
•
•
m: número de tipos de objetos;
R: conjunto de tipos de objetos não padrões (retalhos de cortes anteriores);
C j : número de objetos do tipo j (1 ≤ j ≤ m);
K j : número de possíveis padrões de corte para objetos de tipo j (1 ≤ j ≤ m);
ai jk : número de itens do tipo i no padrão de corte k de objetos de tipo j (1 ≤ i ≤ n,
1 ≤ j ≤ m, 1 ≤ k ≤ K j )
• u jk : indica se o padrão de corte k de objetos de tipo j gera um retalho (1 ≤ j ≤ m,
1 ≤ k ≤ K j)
• t jk : perda de material gerada pelo padrão de corte k de objetos de tipo j (1 ≤ j ≤ m,
1 ≤ k ≤ K j)
Variáveis do Modelo 4:
2.3 Algoritmos
32
• x jk : número de vezes que o padrão de corte k de objetos de tipo j é incluído na
solução
Modelo 4:
m Kj
min
∑ ∑ t jk x jk
[Perda de Material]
(2-45)
[Retalhos no Estoque]
(2-46)
[Restrições de Demanda]
(2-47)
[Restrições de Estoque]
(2-48)
j=1 k=1
m Kj
min
Kj
∑ ∑ u jk x jk + ∑ (C j − ∑ x jk )
j=1 k=1
j∈R
k=1
m Kj
s.a :
∑ ∑ ai jk x jk = bi
∀i
j=1 k=1
Kj
∑ x jk ≤ C j
∀j
k=1
x jk ≥ 0, x jk ∈ Z (1 ≤ j ≤ m e 1 ≤ k ≤ K j )
Neste modelo as restrições (2-48) impedem que uma solução considere mais
objetos de um determinado tipo dos que há no estoque.
É ipmortante mencionar que o número de variáveis do modelo 4 é exponencial
no tamanho da instância que é dado pelo comprimento do maior objeto padrão e as
combinações de items que podem ser alocados nele. Porém, podería-se utilizar um
algoritmo de geração de colunas com esse modelo.
2.3
Algoritmos
Nesta seção são descritos os algoritmos que projetamos para o CSPUL. Apresentamos uma heurística construtiva baseada no First Fit Decreasing algorithm (FFD) e
duas metaheurísticas: uma baseada no GRASP e outra em algoritmos evolutivos. Também mostramos como pode ser melhorado o desempenho das nossas propostas usando
processos em paralelo.
2.3.1
Heurística Construtiva
Dada uma instância do CSPUL, o procedimento FFD é aplicado em cada objeto:
corta o objeto para gerar itens do maior tipo tantas vezes quanto seja possível, levando
em conta que não se pode gerar um número maior de itens do que os demandados, depois
gera itens do segundo maior tipo, e assim até gerar itens do menor tipo.
2.3 Algoritmos
33
A heurística construtiva usa um procedimento com uma ideia similar, só que
selecionando os tipos de itens a serem gerados pela ordem em que são dados na lista de
itens e não pelo tamanho. Isto garante que gerando permutações da lista de itens se obtem
diferentes soluções, e assim oferecendo diversidade de soluções iniciais. A figura 2.5
mostra como diferentes padrões de corte são gerados simplesmente permutando a ordem
dos itens.
Figura 2.5: a), b) e c) mostram como permutando a ordem dos
itens são gerados diferentes padrões de corte usando
um processo similar ao FFD.
A heurística construtiva é descrita pelo algoritmo 2.1, e a figura 2.6 mostra como
ela funciona. Esta heurística consiste em três blocos principais:
• Da linha 3 até a 8: para cada tipo de objeto aplica-se o procedimento similar ao
FFD para gerar padrões de corte, incluindo aqueles padrões que não têm sobras na
solução.
• Da linha 10 até a 26: se no bloco anterior nenhum padrão foi incluído na solução,
então cada padrão é melhorado e novamente são incluídos na solução aqueles
padrões sem sobras.
• Da linha 28 até a 33: se nenhum dos blocos anteriores adicionou novos padrões
na solução, então os padrões que não têm perdas de tamanho intermediário são
incluídos na solução. Se todos os padrões têm perdas de tamanho intermediário,
então é incluído na solução aquele com a menor perda.
2.3 Algoritmos
34
Algoritmo 2.1: Heurística Construtiva
Dados: Instância do problema
1 início
2
repita
3
para cada tipo de objeto k faça
4
se há objetos de tipo k no estoque então aplica o processo similar ao FFD para obter o padrão pk
5
6
para cada padrão pk faça
se pk é viável e não tem sobra então adiciona pk na solução, atualiza as demanadas não satisfeitas para os
itens no padrão e elimina um objeto de tipo k do estoque
7
8
9
10
11
12
13
14
se nenhum padrão foi incluído na solução nesta iteração então
para cada padrão pk faça
cria os padrões p̂k e p̄k iguais a pk
cria a varável v igual ao primeiro tipo de item no padrão pk
repita
tira um item de tipo v de p̂k e de p̄k
aplica o processo similar ao FFD para completar o padrão p̄k sem considerar itens de tipo v
se ((a sobra de p̄k é menor que a de pk ) ou (a sobra de pk é méia e a de p̄k um retalho)) e não( a
sobra de pk é retalho e a de p̄k é méia) então
pk ← p̄k
15
16
17
v ← próximo tipo de item em p̂k , se v é o último tipo de item em p̂k , então que seja o primeiro
tipo de item em p̂k
até p̂k não tenha itens ou pk não tenha sobra
18
19
20
para cada padrão pk faça
se pk é viável e não tem sobra então
adiciona pk na solução, atualiza as demandas não satisfeitas para os itens no padrão e elimina
um objeto de tipo k do estoque
21
22
23
se nenhum padrão foi incluído na solução nesta iteração então
repita
seleciona o melhor padrão pk , onde: se há padrões viáveis com sobras pequenas, então o melhor
é aquele viável com a menor sobra; senão, se há padrões viáveis com retalhos, então o melhor é
aquele viável com o menor retalho; senão o melhor padrão é aquele viável com a menor perda
se (pk tem sobra pequena ou retalho) ou (é a primeira iteração do repita) então
adiciona pk na solução, atualiza as demandas não satisfeitas para os itens no padrão e
elimina um objeto de tipo k do estoque
24
25
26
até nenhum padrão seja adicionado na solução
27
até o estoque está vazio ou as demandas de itens estão satisfeitas
28 fim
2.3.2
Algoritmo Baseado no GRASP
A forma geral do GRASP é descrita pelo algoritmo 2.2.
O algoritmo baseado no GRASP aqui proposto considera o problema multiobjetivo e é mostrado pelo algoritmo 2.3.
As condições de parada usadas são o máximo número de iterações e o máximo
número de iterações sem incluir novas soluções no pool. Na continuação definimos conceitos empregados pelo algoritmo, que são: a) qualidade de uma solução e b) vizinhança
de uma solução.
Definição de Qualidade de uma Solução: É empregado o critério de dominância
de Pareto para expressar a qualidade de uma solução. Dizemos que a solução soli domina
a sol j se e somente se soli melhora sol j em pelo menos um dos objetivos e soli não é pior
que sol j em nenhum objetivo.
Assim, definimos para a solução solk os conjuntos Domk =
{soll |soll domina solk } e Domk = {soll |solk domina soll }. Desta forma dizemos que
2.3 Algoritmos
35
Figura 2.6: Exemplo de execução da Heurística Construtiva (os
padrões verdes são os incluídos na solução)
Algoritmo 2.2: Forma geral do GRASP
Dados:
1 início
2
repita
3
calcula uma solução gulosa aleatória inicial
4
faz busca local na solução calculada
5
se a solução obtida melhora a melhor solução até o momento então
atualiza a melhor solução até momento com o valor da nova solução
6
até satisfazer condições de parada
7 fim
2.3 Algoritmos
36
Algoritmo 2.3: Algoritmo baseado no GRASP
Dados: Instância do problema
1 início
2
pool: conjunto de soluções com capacidade limitada, inicialmente vazio
3
repita
4
sol: solução inicial calculada com a heurística construtiva com uma ordem
aleatória dos itens
5
repita
6
se (pool não está cheia) ou (sol é melhor que alguma solução do pool)
então
7
se pool está cheia então
8
remover a pior solução do pool
incluir sol no pool
9
atualiza sol como um dos vizinhos
até satisfazer condições internas de parada
até satisfazer condições de parada
tirar do pool todas as soluções dominadas
10
11
12
13
14
fim
a solução soli é melhor que a sol j se e somente se:
• soli ∈ Dom j , ou
• sol j ∈
/ Domi e |Domi | < |Dom j |, ou
• sol j ∈
/ Domi e |Domi | = |Dom j | e soli é melhor que sol j seguindo a definição de
ideal, aceitável e indesejável discutida na seção 2.1, ou
• sol j ∈
/ Domi e |Domi | = |Dom j | e sol j não é melhor que soli seguindo a definição
de ideal, aceitável e indesejável e |Domi | > |Dom j |.
Definição de Vizinhança: Consideramos quatro possíveis movimentos de uma
solução para uma vizinha. A decisão de qual movimento escolher é feita dinamicamente.
• Movimento para criar melhores padrões: usado quando na solução atual existem
padrões com perdas de tamanho intermediário. A ideia é eliminar todos os padrões
com perdas de tamanho intermediário da solução e criar um possível padrão inviável
com todas as demandas não satisfeitas. Se o padrão resultante é inviável, então um
item do primeiro tipo no padrão é removido; se ainda o padrão resultante é inviável,
então um item do segundo tipo é removido e assim sucessivamente até obter um
padrão viável. Se um item do último tipo é removido e ainda o padrão é inviável,
então o processo continua pelos itens do primeiro tipo. Este processo é repetido até
que todas as demandas dos itens sejam satisfeitas. A figura 2.7 mostra um exemplo
deste tipo de movimento.
• Movimento para eliminar retalhos: usado quando o número de retalhos gerados
pela solução atual é maior que uma quantidade desejável (que é calculada como
2.3 Algoritmos
37
Figura 2.7: Este exemplo mostra como o movimento para criar
melhores padrões consegue uma solução com uma
perda de comprimento 1cm e um retalho a partir de
uma solução com três perdas, cada uma de comprimento 1cm (o que é 3cm de perda total) e um retalho.
uma fração do número de perdas pequenas). A ideia é eliminar todos os padrões
que geram sobras, e depois, solucionar para cada objeto j o seguinte problema da
mochila, considerando somente os itens com demandas não satisfeitas:
n
max
∑ sk xk
k=1
n
s.a
∑ sk xk ≤ d j
k=1
xk ≤ b̂k
xk ≥ 0, xk ∈ Z (1 ≤ k ≤ n)
onde: d j é o comprimento do objeto j, sk o comprimento dos itens de tipo k, e b̂k a
demanda não satisfeita de itens de tipo k.
2.3 Algoritmos
38
Após solucionar o problema da mochila, o padrão com menor sobra é incluído na
solução, e assim o processo é repetido até satisfazer todas as demandas.
• Movimento para eliminar perdas pequenas: usado quando o número de perdas
pequenas geradas pela solução atual é maior que uma quantidade desejável (que
é calculada como uma proporção do número de retalhos). A ideia é similar ao
movimento para eliminar retalhos, tendo só diferença no momento de adicionar
um novo padrão na solução; pois se o padrão selecionado tem uma perda pequena e
não foram adicionados padrões com retalhos ou sem sobra, então o menor item do
padrão é removido para assim criar um retalho.
• Movimento para diversificar: usado para gerar novas soluções e tentar evitar ótimos
locais. Neste caso são removidos todos os padrões com sobras da solução atual, e
é aplicada a heurística construtiva ao subproblema com os objetos não usados do
estoque e com as demandas não satisfeitas.
É importante enfatizar que este algoritmo baseado no GRASP retorna um conjunto de soluções não-dominadas. Na próxima subseção introduzimos outra metaheurística, neste caso baseada em algoritmos evolutivos, que também produz um conjunto de
soluções não-dominadas.
2.3.3
Metaheurística Baseada em Algoritmos Evolutivos
A forma geral de um algoritmo evolutivo é descrita pelo algoritmo 2.4.
Algoritmo 2.4: Forma geral de um algoritmo evolutivo
Dados:
1 início
2
Gera uma população inicial de soluções
3
repita
4
calcula um valor de qualidade para cada solução
5
considerando a qualidade, seleciona um subconjunto da população para ser
os pais da próxima população
6
combina os pais selecionados para criar novas soluções
7
aplica um operador de mutação nas novas soluções
8
inclui na próxima população as melhores soluções da população anterior e
das novas criadas nesta iteração
9
até satisfazer as condições de parada
10 fim
A metaheurística baseada em algoritmos evolutivos proposta nesta subseção é
descrita pelo algoritmo 2.5. É usado o mesmo critério de qualidade de uma solução
definido para o algoritmo baseado no GRASP da subseção anterior. Para esta metaheurística foram definidos um operador de combinação e dois de mutação.
2.3 Algoritmos
39
A combinação entre duas soluções (pais) adiciona de forma alternada, em uma
nova solução, aqueles padrões de corte dos pais que não geram sobra. Se não é possível
adicionar mais um padrão na nova solução sem fazê-la inviável, então é aplicado o
primeiro operador de mutação nesta nova solução (que ainda é uma solução parcial).
Dada uma solução parcial, o primeiro operador de mutação soluciona o subproblema com as demandas não satisfeitas e os objetos não usados, aplicando uma estratégia
similar à usada no movimento para eliminar retalhos descrito na subseção anterior.
Dada uma solução viável, o segundo operador de mutação atribui a cada padrão
de corte um valor de rank, baseado no número de itens grandes que este padrão gera.
Onde, um item é considerado grande se é maior ou igual a uma fracção do menor objeto
padrão. Assim, todos os padrões de corte com rank zero ou com sobra são eliminados da
solução e é aplicada uma estratégia similar à usada no movimento para eliminar retalhos
da subseção anterior, seguindo também o objetivo de maximar o rank dos padrões de corte
a serem incluídos na solução.
Algoritmo 2.5: Metaheurística Baseada em Algoritmos Evolutivos
Dados: Instância do problema
1 início
2
poolcap ← capacidade do pool
3
pool: conjunto inicial de soluções geradas pela heurística construtiva usando
ordenamentos aleatórios dos itens
4
repita
5
S ← {}
6
para i = 1 até poolcap faça
7
para j = i + 1 até poolcap faça
8
aplica o operador de combinação nas soluções i e j do pool, e na
solução parcial resultante s aplica o primeiro operador de mutação
9
S ← S ∪ {s}
para cada solução s ∈ S faça
se s é melhor que alguma solução do pool então
remove a pior solução do pool
adiciona s no pool
10
11
12
13
se nenhuma nova solução foi adicionada no pool então
para cada solução s ∈ pool faça
aplica o segundo operador de mutação em s e adiciona a solução
mutada em S
S ← S ∪ pool
pool ← {}
pool ← as poolcap melhores soluções de S
14
15
16
17
18
19
até satisfazer as condições de parada
20
21
fim
2.3 Algoritmos
40
O algoritmo 2.5 consiste em:
• Da linha 5 até 10: a cada par de soluções na população é aplicado o operador de
combinação para gerar uma nova solução parcial, na qual é aplicado o primeiro
operador de mutação para assim obter uma nova solução viável.
• Da linha 11 até 17: cada nova solução é comparada com as soluções na população
e se é melhor que a pior solução da população, então a pior solução da população é
substituída pela nova solução.
• Da linha 18 até 24: se a população não é modificada, então a todas as soluções da
população é aplicado o segundo operador de mutação, e as melhores soluções são
selecionadas para a população.
2.3.4
Processos Paralelos
Nesta subseção são explicadas algumas ideias para os processos paralelos, que
foram implementados sob a plataforma CUDA usando GPUs, para melhorar o desempenho da heurística construtiva, do algoritmo baseado no GRASP e da metaheurística
baseada em algoritmos evolutivos. Um ponto relevante a ter em conta é que quando usamos paralelismo com GPUs, a transferência de dados entre CPU e GPUs pode consumir
tempo computacional razoável.
Assim, decidimos paralelizar os processos que demoram mais tempo e, simultaneamente, não requerem grandes transferências de dados entre diferentes espaços de
memória.
Na heurística construtiva consideramos:
(a) no início os vetores de dados contendo o comprimento dos objetos e dos itens são
copiados da memória da CPU para a memória compartilhada das GPUs;
(b) para cada tipo de objeto é criado um thread, que é responsável por executar o
processo similar ao FFD. Antes disto é preciso copiar os vetores com os dados
das demandas dos itens e do número de objetos no estoque, da memória da CPU
para a das GPUs. Assim, os padrões resultantes são copiados do espaço de memória
das GPUs para o da CPU;
(c) para cada padrão pk é criado um thread que executa o bloco da linha 10 até a 26 do
algoritmo 2.1. Sendo só necessário copiar os padrões resultantes da memória das
GPUs para a da CPU.
No algoritmo baseado no GRASP consideramos:
(a) as considerações anteriores aplicadas na heurística construtiva;
(b) quando se soluciona o problema da mochila clássico para todos os tipos de objetos
(a figura 2.8 descreve o processo):
2.3 Algoritmos
41
– cria dados auxiliares para o problema da mochila, onde a capacidade será o
comprimento do maior tipo de objeto no estoque (max d j ). Primeiramente o
vetor com as demandas dos itens é copiado da memória da CPU para a das
GPUs, depois para cada item i são criados si threads, onde si é o comprimento
do item i. Cada um destes threads executa o algoritmo 2.6;
– Um thread é criado para cada tipo de objeto, onde cada thread é responsável
por encontrar um padrão viável que minimize a sobra. Para isto, uma cópia do
vetor com os objetos disponíveis no estoque é feita da memória da CPU para
a das GPUs, e os padrões resultantes são copiados da memória das GPUs para
a da CPU.
A metaheurística baseada em algoritmos evolutivos usa processos paralelos
similares aos discutidos anteriormente. Além disso, quando o segundo operador de
mutação cria os dados para solucionar o problema da mochila, um vetor com os ranks
dos padrões de cortes é calculado por cada thread.
Algoritmo 2.6: Processo para construir os dados auxiliares para o problema da
mochila.
Dados:
L1 ∈ Nmax{d j +1} : vetor com os valores entre 0 e max d j que podem ser obtidos por
combinações lineares dos comprimentos dos itens, satisfazendo as restrições de
demandas. L1i é o tipo de item que chega no valor i (se o valor não pode ser obtido
por combinação linear dos comprimentos dos itens, então L1i = 0)
L2 ∈ Nmax{d j +1} : o vetor, em cada possição i, tem o número de itens de tipo L1i
necessários para obter o valor i na combinação linear
k ∈ N: tipo de item atual
bk ∈ N: demanda não satisfeita de tipo de item atual
sk ∈ N: comprimento do tipo de item atual
p ∈ N, 0 ≤ p < sk
1 início
2
se bk > 0 então
3
para i = p até (max d j ) − sk com incremento sk faça
4
se L1i ≥ 1 e L1i+sk = 0 e (L1i 6= k or L2i < bk ) então
5
L1i+sk ← k
6
L2i+sk ← 1
7
se L1i = k então L2i+sk ← L2i + 1
8
fim
2.4 Testes Computacionais
2.4
42
Testes Computacionais
Nesta seção apresentamos experimentos computacionais sobre três tipos de
instâncias: instâncias numéricas ([13]), instâncias práticas ([1]) e intâncias aleatórias ([5]).
A tabela 2.1 mostra os significados dos labels que aparecem nas tabelas com os
resultados dos experimentos.
Label
Obj.Cut
To.Length
Total Loss
Total Ret.
OSScrap
ONSScrap
ORetail
Solution
RGRL 1
RGRL 2
RGRL 3
Const. H.
GRASP BA
Evol. BA
Var.Numb.
Const.Numb.
RUB
Init.Sol.
Init.GAP
Last.Sol.
Nod.Numb.
Iter.
Stop.Crit
Time
Significado
número de objetos cortados
comprimento total de material cortado
comprimento total das sobras
comprimento total dos retalhos
número de padrões que geram perda pequena
número de padrões que geram perdas de tamanho intermediário
número de padrões que geram retalhos
classificação das soluções onde: ID é ideal,
AC é aceitável, e UD é indesejável
algoritmo ideal RGRL 1 em [5]
algoritmo ideal RGRL 2 em [5]
algoritmo ideal RGRL 3 em [5]
heurística construtiva
algoritmo baseado no GRASP
metaheurística baseada em algoritmos evolutivos
número de variáveis
número de restrições
número de retalhos
valor da solução inicial inteira
gap inicial
valor da última solução inteira
número de nós na árvore de enumeração
número de iterações
critério de parada, onde OPT é por otimalidade e
OME é por out of memory exception
tempo de execução em segundos
Tabela 2.1: Labels e seus significados.
2.4.1
Instâncias
Instâncias Numéricas
Foram testadas três instâncias numéricas:
• Instância numérica 1: 20 tipos de objetos com comprimentos entre 2200 e 6000
cm, tendo só um objeto de cada tipo no estoque. A tabela 2.2 contém os dados de
comprimentos e demandas dos itens.
2.4 Testes Computacionais
43
Figura 2.8: Nas tabelas, as filas Valores, Itens e Número, respectivamente, representam os valores que podem ser obtidos como combinações lineares dos itens, o tipo de
item que chega no valor, e o número de itens desse
tipo necessários para chegar nesse valor. Quando adicionamos um padrão de corte na solução, o vermelho
indica o tamanho do objeto que será cortado e os itens
do padrão estão em verde.
Item Comprimento (cm) Demanda
1
235
4
2
200
51
3
347
42
4
471
16
5
274
37
Tabela 2.2: Comprimentos e demandas dos itens da instância
numérica 1
2.4 Testes Computacionais
44
• Instância numérica 2: 20 tipos de objetos com comprimentos 2100 e 5000 cm,
tendo só um objeto de cada tipo no estoque. A tabela 2.3 contém os dados de
comprimentos e demandas dos itens.
Item Comprimento (cm) Demanda
1
549
39
2
433
27
3
207
43
4
308
30
5
583
2
Tabela 2.3: Comprimentos e demandas dos itens da instância
numérica 2
• Instância numérica 3: 90 tipos de objetos com comprimentos entre 3000 e 9000
cm, tendo só um objeto de cada tipo no estoque. A tabela 2.4 contém os dados de
comprimentos e demandas dos itens.
Item Comprimento (cm) Demanda
1
569
34
2
718
26
3
520
25
4
540
12
5
492
30
6
547
2
7
632
6
8
430
36
9
750
7
10
387
20
11
804
3
12
389
32
13
835
18
14
684
39
15
687
10
Tabela 2.4: Comprimentos e demandas dos itens da instância
numérica 3
Instâncias Práticas
Foram testadas duas intâncias práticas:
• Instância prática 1: 10 objetos de um único tipo no estoque cada um com
comprimento 3000 cm. A tabela 2.5 contém os dados de comprimentos e demandas
dos itens.
2.4 Testes Computacionais
45
Item Comprimento (cm) Demanda
1
250
2
2
273
2
3
285
4
4
525
4
5
1380
4
Tabela 2.5: Comprimentos e demandas dos itens da instância
prática 1
• Instância prática 2: 10 objetos de um único tipo no estoque cada um com
comprimento 6000 cm. A tabela 2.6 contém os dados de comprimentos e demandas
dos itens.
Item Comprimento (cm) Demanda
1
370
5
2
905
5
3
910
5
4
930
5
Tabela 2.6: Comprimentos e demandas dos itens da instância
prática 2
Instâncias Aleatórias
Foram testadas 320 instâncias aleatórias, agrupadas em 16 classes de 20 instâncias cada uma. A tabela 2.7 dá a descripção de cada classe de instâncias, representando:
No. Obj. Type, o número de diferentes tipos de objetos; No. Itm. Type, o número de diferentes tipos de itens; e Items, os tipos de itens. Existem dois tipos de itens: pequeno que
são itens menores que 25% do tamanho do menor objeto padrão, e tamanho médio, de
comprimentos aleatórios, que podem ser maiores que 25% do tamanho do menor objeto
padrão.
2.4.2
Discussões sobre os Modelos Matemáticos
A qualidade dos modelos matemáticos é analizada considerando instâncias
numéricas e práticas. Para obter a fronteira de Pareto para uma instância dada, são solucionados vários modelos mono-objetivos fixando os diferentes valores possíveis para o
máximo número de retalhos. Todos os modelos foram resolvidos usando o ILOG CPLEX
9.0 em um PC Intel Core 2 Duo, 2.8GHz e 3.25GB de RAM sob o sistema operacional
Microsoft Windows XP Professional.
2.4 Testes Computacionais
46
Classe No. Obj. Type No. Itm. Type
1
5
10
2
5
10
3
5
20
4
5
20
5
5
40
6
5
40
7
7
10
8
7
10
9
7
20
10
7
20
11
7
40
12
7
40
13
9
10
14
9
10
15
9
20
16
9
20
Items
pequeno
tamanho médio
pequeno
tamanho médio
pequeno
tamanho médio
pequeno
tamanho médio
pequeno
tamanho médio
pequeno
tamanho médio
pequeno
tamanho médio
pequeno
tamanho médio
Tabela 2.7: Instâncias aleatórias
Para gerar as colunas do modelo 4 foi usado um algoritmo de enumeração dos
padrões para cada tipo de objeto, e os tempos de execuções deste algoritmo, para as
instâncias testadas, foram desprezíveis (menos de um milésimo de um segundo).
Discussões sobre as Instâncias Numéricas
É importante notar que para as instâncias numéricas os modelos 2 e 3 são o
mesmo. A tabela 2.8 e as tabelas 2.9, 2.10, 2.11 mostram os resultados obtidos pelo
CPLEX para as instâncias numéricas 1 e 2. Nestas tabelas pode-se ver que o modelo
4 foi melhor que os modelos 1, 2 e 3. Com o modelo 4 o CPLEX encontrou soluções
ótimas usando menos nós na árvore de enumeração, menos iterações e menos tempo
computacional do que com os outros modelos. Além disto, usando os modelos 1, 2 e
3 o CPLEX parou antes de encontrar soluções ótimas por Out of Memory Exception.
Quando comparamos os resultados obtidos pelo CPLEX usando os modelos,
observamos que com o modelo 4:
• obteve soluções ótimas para todas as instâncias numéricas;
• provou otimalidade das soluções em quase todos os testes com as intâncias numéricas;
1
• precisou menos que 10
do tempo de execução usado com os outros modelos;
1
• usou menos que 10
do número de nós na árvore de enumeração usado com os outros
modelos;
2.4 Testes Computacionais
Var.Numb.
Const.Numb.
RUB
Init.Sol.
Init.GAP
Last.Sol.
Nod.Numb.
Iter.
Stop.Crit.
Time
47
Modelo 1
200
246
0
1
812
666
100
100
412
56
12311549 13982753
246490262 51903397
OME
OME
81131.97 99449.89
Modelo 2 e Modelo 3
160
66
0
1
1612
706
100
100
212
2
299588
2816951
63764569 72973808
OME
OME
54980.63 224907.99
Modelo 4
228928
26
0
1
212
128
100
100
12*
0*
159119
14800
326807
68008
OME
OPT
851.56 5239.51
Tabela 2.8: Resultados do CPLEX com a instância numérica 1. O
* indica que a solução é ótima.
Var.Numb.
Const.Numb.
RUB
Init.Sol.
Init.GAP
Last.Sol.
Nod.Numb.
Iter.
Stop.Crit.
Time
0
1523
100
763
13319148
133503248
OME
13213.92
1
1144
100
412
16888927
274466473
OME
20635.11
Modelo 1
200
246
2
1044
100
588
13788840
127304689
OME
15711.78
3
747
100
263
14090112
166485902
OME
34251.25
4
1319
100
335
13225677
129522082
OME
56088.31
Tabela 2.9: Resultados do CPLEX para o modelo 1 com a instância numérica 2.
Var.Numb.
Const.Numb.
RUB
Init.Sol.
Init.GAP
Last.Sol.
Nod.Numb.
Iter.
Stop.Crit.
Time
0
6359
100
639
11246014
113908074
OME
12484.94
Modelo 2 e Modelo 3
160
66
1
2
3
2480
2704
2988
100
100
100
322
99
11
31677069
21057922
32281347
172418711 121279869 221740224
OME
OME
OME
233656.75
79663.91
32032.25
4
1256
100
46
28203188
186045954
OME
30844.71
Tabela 2.10: Resultados do CPLEX para os modelos 2 e 3 com a
instância numérica 2.
2.4 Testes Computacionais
48
Var.Numb.
Const.Numb.
RUB
Init.Sol.
Init.GAP
Last.Sol.
Nod.Numb.
Iter.
Stop.Crit.
Time
0
183
98
31*
561368
3012034
OME
1793.03
Modelo 4
44389
26
1
2
92
2*
97.2
61.96
3*
2*
9
8
229
226
OPT
OPT
210.8 183.02
3
1*
100
1*
57
778
OPT
60.67
4
1
100
0*
260
5025
OPT
111.02
Tabela 2.11: Resultados do CPLEX para o modelo 4 com a instância numérica 2. O * indica que a solução é ótima.
Discussões sobre as Instâncias Práticas
A tabela 2.12 e as tabelas 2.13, 2.14 mostram os resultados obtidos pelo CPLEX
para as instâncias práticas 1 e 2. Destas tabelas tem-se que o CPLEX usando o modelo
4 obteve soluções ótimas em menos tempo que com os outros modelos. De fato, para
estas intâncias e com o modelo 4 o CPLEX alcançou soluções ótimas na raíz da árvore de
enumeração, provando a otimalidade em poucas iterações.
Assim quando comparamos os resultados obtidos, observamos que com o modelo 4:
• o GAP foi menor, sendo zero em quase todos os testes com as instâncias práticas;
• obteve soluções ótimas na raíz da árvore de enumeração para todas as intâncias
práticas;
• provou otimalidade de todas as soluções obtidas com as instâncias práticas;
• precisou de menos tempo de execução que o usado com os outros modelos;
• usou menos nós na árvore de enumeração que com os outros modelos.
Var.Numb.
Const.Numb.
RUB
Init.Sol.
Init.GAP
Last.Sol.
Nod.Numb.
Iter.
Stop.Crit.
Time
Modelo 1
100
126
1
2
574
244
100
100
240*
0*
24639
30
116008
179
OPT OPT
143.5 0.92
Modelo 2
80
36
1
2
574
264
100
100
240*
0*
64134
135
239880
509
OPT OPT
35.49 1.05
Modelo 3
80
45
1
2
529
70
100
100
240*
0*
331
69
1385
354
OPT OPT
1.13
1
Modelo 4
257
7
1
2
240*
0*
0
0
240*
0*
1
0
26
10
OPT OPT
0.75 0.31
Tabela 2.12: Resultados do CPLEX com a instância prática 1. O *
indica que a solução é ótima.
2.4 Testes Computacionais
Var.Numb.
Const.Numb.
RUB
Init.Sol.
Init.GAP
Last.Sol.
Nod.Numb.
Iter.
Stop.Crit.
Time
49
1
435
100
250*
316596
923668
OPT
203.74
Modelo 1
90
125
2
110
100
70*
2200604
7593572
OPT
1872.75
3
0*
0
0*
0
14
OPT
0.75
1
3875
100
250*
270638
576347
OPT
149.39
Modelo 2
70
35
2
2034
100
70*
805423
2231684
OPT
82.53
3
0*
0
0*
0
12
OPT
0.74
Tabela 2.13: Resultados do CPLEX para os modelos 1 e 2 com a
instância prática 2. O * indica que a solução é ótima.
Var.Numb.
Const.Numb.
RUB
Init.Sol.
Init.GAP
Last.Sol.
Nod.Numb.
Iter.
Stop.Crit.
Time
1
6060
100
250*
1888
6872
OPT
1.88
Model 3
70
44
2
3
190 5615
100
100
70*
0*
5072
18
16508
151
OPT OPT
3.91 1.13
1
250*
18.46
250*
10
75
OPT
0.81
Model 4
343
6
2
3
70*
0*
16.67
0
70*
0*
0
0
26
27
OPT OPT
0.83 0.70
Tabela 2.14: Resultados do CPLEX para os modelos 3 e 4 com a
instância prática 2. O * indica que a solução é ótima.
2.4.3
Discussões sobre os Algoritmos
Para comparar os resultados obtidos pelas nossas propostas com os resultados de
[5], foi usado o critério de qualidade definido em [5], com ε1 = 0.03, ε2 = 0.1, β = 0.005,
θ = 0.05 e δ = min si , onde si é o comprimento do item i.
As nossas implementações usam o compilador GNU C 4.3.3 e os experimentos
foram testados em um PC Intel Core 2 Duo, 2.4GHz and 2GB of RAM sob Ubuntu
9.04. Os processos em paralelo usam uma placa NVIDIA GeForce GTS 250. Os números
pseudo-aleatórios usados nas implementações foram gerados pela função random padrão
do GNU C 4.3.3, com as sementes dadas na tabela 2.15.
49 7
56
42 5
83 13 75
23 17
Tabela 2.15: Sementes para a geração de números pseudoaleatórios
2.4 Testes Computacionais
50
Discussões sobre as Instâncias Numéricas
As tabelas 2.16, 2.17 e 2.18 mostram os resultados obtidos pelas heurísticas para
as instâncias numéricas 1, 2 e 3.
Destas tabelas pode-se ver que em alguns casos os algoritmos RGRL 1, RGRL 2
e RGRL 3 usaram menos objetos que os nossos, porém o comprimento total de material
cortado por RGRL 1, RGRL 2 e RGRL 3 foi maior que o feito pelas nossas heurísticas. Isto é
devido a que RGRL 1, RGRL 2 e RGRL 3 selecionaram maiores objetos do estoque dos que
os selecionados pelas nossas propostas.
Também temos que o GRASP BA e o Evol. BA deram um conjunto de soluções
não-dominadas, o que permite ao usuário selecionar a estratégia de corte que considere
mais adequada. Notemos que o desempenho das nossas metaheurísticas parece ser ideal,
segundo a definição proposta em [5]. Inclusive, para a intância numérica 1 o GRASP BA e
o Evol. BA obtiveram todas as soluções da fronteira de Pareto, e para a intância numérica
2 quase todas as soluções que o Evol. BA gerou são ótimos de Pareto, enquanto para esta
instância nenhum outro algoritmo conseguiu uma solução ótima de Pareto.
Obj.Cut.
Tot.Length
Total Loss
Total Ret.
OSScrap
ONSScrap
ORetail
Solution
RGRL 1
10
45245
0
1857
0
0
1
ID*
RGRL 2
10
45245
0
1857
0
0
1
ID*
RGRL 3
10
46507
0
3119
0
0
2
AC
Const. H.
12
44400
21
991
5
0
1
AC
11
43400
12
0
2
0
0
ID
GRASP BA
12
11
43400 43600
12
0
0
212
1
0
0
0
0
1
ID*
ID*
Evol. BA
11
10
43400 43600
12
0
0
212
1
0
0
0
0
1
ID*
ID*
Tabela 2.16: Soluções para a instância numérica 1. O * indica que
a solução é um ótimo de Pareto.
Obj.Cut.
Tot.Length
Total Loss
Total Ret.
OSScrap
ONSScrap
ORetail
Solution
RGRL 1
15
57554
6
2367
4
0
2
AC
RGRL 2
16
58159
3
2972
4
0
3
UND
RGRL 3
14
56395
7
1207
5
0
2
AC
Const. H.
16
57450
71
2198
12
0
3
UND
16
55488
10
297
6
0
1
AC
GRASP BA
16
16
58528 55792
7
17
3340
594
4
5
0
0
3
2
UND
AC
17
58500
1
3318
1
0
9
UND
15
55820
12
627
2
0
2
AC
Evol. BA
15
14
55212 55392
31
3
1365
208
6
3
0
0
0
1
AC*
AC*
Tabela 2.17: Soluções para a instância numérica 2. O * indica que
a solução é um ótimo de Pareto.
Discussões sobre Instâncias Práticas
As soluções para as instâncias práticas não são classificadas como ideal,
aceitável ou indesejável porque foram cortados poucos objetos e os valores de ε1 e ε2
2.4 Testes Computacionais
Obj.Cut.
Tot.Length
Total Loss
Total Ret.
OSScrap
ONSScrap
ORetail
Solution
RGRL 1
22
172114
0
3098
0
0
1
ID
51
RGRL 2
22
172114
0
3098
0
0
1
ID
RGRL 3
22
170989
0
1943
0
0
1
ID
Const. H.
30
169628
8
574
4
0
1
ID
GRASP BA
27
26
169468 169052
0
6
422
0
0
1
0
0
1
0
ID
ID
Evol. BA
27
27
169468 169048
0
2
422
0
0
1
0
0
1
0
ID
ID
Tabela 2.18: Soluções para a instância numérica 3.
não são apropriados.
Para estas intâncias práticas os desempenhos do GRASP BA e o Evol. BA
foram melhores do que o do resto dos algoritmos. A tabela 2.19 mostra que o GRASP
BA obteve todas as soluções da fronteira de Pareto para a instância prática 1 e o
Evol. BA deu uma solução não dominada, enquanto o resto dos algoritmos geraram
soluções dominadas para a mesma instância. A tabela 2.20 mostra que nossos algoritmos
conseguiram soluções ótimas de Pareto para a instância prática 2, enquanto os algoritmos
em [5] não conseguiram.
Obj.Cut.
Tot.Length
Total Loss
Total Ret.
OSScrap
ONSScrap
ORetail
Solution
RGRL 1
5
15000
0
5194
0
0
3
-
RGRL 2
5
15000
0
5194
0
0
3
-
RGRL 3
5
15000
4
5190
1
0
3
-
Const. H.
5
15000
14
5180
1
0
4
-
GRASP BA
4
4
12000 12000
0
240
2194
1954
0
0
0
1
2
1
*
*
Evol. BA
4
12000
0
2194
0
0
2
*
Tabela 2.19: Soluções para a instância prática 1. O * indica que a
solução é um ótimo de Pareto.
2.4.4
Discussões sobre Instâncias Aleatórias
As tabelas 2.21 e 2.22 apresentam os resultados dos nossos algoritmos e os
propostos em [5] para as instâncias aleatórias, nos quais os nossos algoritmos:
•
•
•
•
usaram menos objetos padrões;
usaram mais objetos não padrões (retalhos que estavam no estoque);
geraram menos retalhos;
usaram menos tempo computacional;
2.4 Testes Computacionais
Obj.Cut.
Tot.Length
Total Loss
Total Ret.
OSScrap
ONSScrap
ORetail
Solution
RGRL 1
3
18000
150
2275
0
1
2
-
52
RGRL 2
3
18000
150
2275
0
1
2
-
RGRL 3
3
18000
150
2275
0
1
2
-
Const. H.
3
18000
0
2425
0
0
3
*
GRASP BA
3
3
18000 18000
0
250
2425
2175
0
0
0
2
3
1
*
*
Evol. BA
3
18000
0
2425
0
0
3
*
Tabela 2.20: Soluções para a instância prática 2. O * indica que a
solução é um ótimo de Pareto.
• em particular, a metaheurística baseada em algoritmos evolutivos gerou a menor
perda de material. Enquanto a heurística construtiva e o algoritmo baseado no
GRASP geraram mais perda de material que as propostas de [5].
A figura 2.9 mostra a relação de dominância entre nossos algoritmos e os
propostos em [5].
Obj.Cut.
Tot.Length
Total Loss
Total Ret.
OSScrap
ONSScrap
ORetail
Solution
Time/Parallel Time
RGRL 1
106.9
111957.6
11.5
587.4
3.2
0.1
2.6
ID
22.55
RGRL 2
106.9
111923.5
11.8
552.8
3.2
0.1
2.6
ID
22.74
RGRL 3
106.9
111979.4
12.5
601.9
3.6
0.1
2.8
ID
81.85
Const. H.
129.6
112511.8
484.8
668.3
109.2
18.2
2.2
UND
0.003 / 0.003
GRASP BA
119.9
112033
41.2
632.9
5.2
1
2
AC
0.95 / 0.57
Evol. BA
117.6
112053.3
9.4
685
3.4
0.03
2.5
ID
1.64 / 0.7
Tabela 2.21: Resultados com instâncias aleatórias.
Comparação com os Resultados de [6]
Em [6] foi proposta uma heurística (denominada RSHP) e foram reportados os
resultados computacionais com as mesmas instâncias aleatórias de [5]. Os autores não
deram resultados sobre outras instâncias da literatura. A tabela 2.23 mostra os resultados
dos nossos algoritmos e os reportados em [6].
As soluções geradas pela heurística RSHP apresentam menos retalhos, porém
usam menos objetos não-padrões do que os usados pela nossa heurística construtiva.
Assim, o número total de retalhos no estoque final da heurística construtiva é menor. Por
outro lado, a perda de material gerada pela nossa metaheurística baseada em algoritmos
evolutivos é menor que a gerada pelo algoritmo RSHP. A figura 2.10 mostra a relação de
dominância entre o RSHP e nossas propostas.
2.4 Testes Computacionais
Stand.Cut.
NonStand.Cut.
Stand.Length
NonStand.Length
Stand. Loss
NonStand. Loss
Stand.Ret.
NonStand.Ret.
53
RGRL 1
102.6
4.3
110932.2
1025.4
6.2
5.3
383.5
195.7
RGRL 2
102.5
4.4
110881.9
1041.6
6.6
5.3
342
210.9
RGRL 3
102.6
4.5
110926.9
1052.5
7
5.1
383.8
217.5
Const. H.
102.6
27
105718.1
6793.7
296.7
188.1
648.3
20
GRASP BA
103.8
16.1
107786
4247
34.2
7
592.2
40.7
Tabela 2.22: Resultados com instâncias aleatórias.
Figura 2.9: Os valores obtidos por RGRL 1, RGRL 2 e RGRL 3 foram
dominados, enquanto os valores obtidos por Const. H.,
GRASP BA e Evol. BA foram não-dominados
Tot.Length
Stand.Cut.
NonStand.Cut.
Total Loss
Total Ret.
ORetail
Time/Parallel Time
RSHP
111672
101.5
23.6
9.8
303.2
1.2
1.56
Const. H.
112511.8
102.6
27
484.8
668.3
2.2
0.003 / 0.003
GRASP BA
112033
103.8
16.1
41.2
632.9
2
0.95 / 0.57
Tabela 2.23: Comparação com [6]
Evol. BA
112053.3
103.6
15.2
9.4
685
2.5
1.64 / 0.7
Evol. BA
103.6
15.2
107872.6
4180.7
5.7
3.7
579
106
2.4 Testes Computacionais
Figura 2.10: Os resultados do GRASP BA foram dominados, enquanto os do Const. H., RSHP e Evol. BA foram nãodominados
54
CAPÍTULO 3
Problema de Emparelhamento Estável
Existem muitos problemas em otimização combinatória em que há necessidade
de emparelhamento com preferências. Uma subclasse destes problemas é referida como
emparelhamento estável e foi introduzida por D. Gale and L.S. Shapley em College
admissions and the stability of marriage (1962), com os problemas do casamento estável
(stable marriage) e o dos companheiros estáveis (roommates stable matching).
Em [23] é dada a seguinte definição formal do problema do casamento estável:
Uma instância do problema consiste de um conjunto de 2n pessoas, sendo n homens
e n mulheres. Cada pessoa tem uma lista de preferência sobre os membros do sexo
oposto; assim, se um homem m prefere uma mulher w1 mais do que uma mulher w2 , então
escrevemos w1 m w2 (uma notação similar é usada para a preferência das mulheres).
Desta forma uma assignação (ou emparelhamento) M é um conjunto de pares disjuntos
homem-mulher, e se um homem m é associado com uma mulher w, escrevemos M(m) = w
e M(w) = m. E um casamento estável é uma assignação sem blocking pairs, onde um
blocking pair para M é um par homem-mulher (m, w) tal que: M(m) 6= w, w m M(m) e
m w M(w).
Gale e Shapley propuseram um algoritmo de tempo polinomial para encontrar
casamentos estáveis para as instâncias do problema. Isto foi feito mostrando que para
qualquer instância do problema existe pelo menos um emparelhamento estável. Uma variante do problema do casamento estável é o problema dos companheiros estáveis, e para
este problema nem sempre existe um emparelhamento estável. O problema dos companheiros estáveis tem recebido atenção na literatura. Como resultado vários pesquisadores
criaram algoritmos eficientes que determinam se um emparelhamento estável existe ou
dizem que não é possível encontrá-lo para certas classes de instâncias ([2, 9, 18, 19, 21]).
Mas, como em muitos casos pode não existir uma assignação estável para as instâncias do
problema, seria interessante encontrar, por exemplo, um emparelhamento que minimiza
o número de blocking pairs. Assim, uma definição para o problema dos companheiros
estáveis, dada em [23], é:
56
Uma instância do problema dos companheiros estáveis consiste de n = 2N (N ∈ N)
pessoas, onde cada uma delas tem uma lista de preferências sobre as n − 1 restantes.
O objetivo é encontrar um emparelhamento que minimize o número de blocking pairs.
Matematicamente isto pode ser escrito como:
min
∑
zm,w
(m,w)∈M
s.a :
∀(m, w) : se pm (M(m)) ≤ pm (w) ou pw (M(w)) ≤ pw (m),
então zm,w = 0 senão zm,w = 1
onde: pr (t) é a preferência da pessoa r pela pessoa t
3.0.5
Variantes
As principais formas que o problema dos companheiros estáveis têm sido visto
na literatura são:
• Determinar se existe um emparelhamento estável para uma instância do problema.
Esta variante é um problema de decisão que pertence a classe NP-completo e tem
sido tratada em subcasos, em alguns deles é possível encontrar soluções em tempo
polinomial:
– Para instâncias onde as preferências são estritas (isto é, nenhuma pessoa tem
igual preferência por outras duas), o problema dos companheiros estáveis pode
ser solucionado em tempo polinomial. (Ver referências [19, 21])
– Para instâncias que permitem empates nas listas preferências, são analizadas
diferentes definições de estabilidade:
∗ Estabilidade fraca. Um emparelhamento M tem estabilidade fraca se
não existem dois participantes x e y, onde cada um deles prefere estritamente o outro ao invés do companheiro em M. Esta definição é equivalente à de estabilidade e é provado que este problema é NP-completo.
(Ver referências [9, 21])
∗ Super-estabilidade. Um emparelhamento M é super-estável se não existem dois participantes x e y, onde cada um deles prefere ou tem a mesma
preferência pelo outro que pelo companheiro em M. Em [21] esta variante
foi resolvida dando um algoritmo de tempo polinomial.
– Companheiros estáveis geométricos. Considera instâncias obtidas de uma
representação geométrica das listas de preferências, onde um participante é
representado por um ponto do espaço mêtrico e as preferências são dadas pelas
3.1 Novos Modelos Matemáticos para o Problema dos Companheiros Estáveis
57
distâncias dele aos outros participantes. Para instâncias deste tipo existem
algoritmos de tempo polinomial. (Ver referência [2])
• Determinar se dada uma instância do problema ela é bi-estável. Esta variante foi
tratada em [32], demonstrando que existem algoritmos de tempo polinomial para
resolvê-la.
Bi-estabilidade. Dada uma instância do problema dos companheiros estáveis, uma
nova instância é obtida invertendo as listas de preferências. Um emparelhamento é
bi-estável se é estável tanto para a instância original quanto para a instância com
as listas de preferências invertidas. Este conceito foi introduzido em [34].
• Determinar se uma instância do problema é estável para quartos triplos. Neste
caso se considera que a assignação não é um conjunto de pares de pessoas, mas sim
um conjunto de trios. Em [25] foi demonstrado que esta variante pertence a classe
NP-completo.
Neste capítulo, na seção 3.1 apresentamos um modelo quadrático e um linear
para o problema dos companheiros estáveis. Na seção 3.2 propomos uma metaheurística
Busca Tabu, que é melhorada com processos em paralelo usando GPUs. Na seção
3.3 damos um algoritmo Branch-and-Bound para solucionar o problema. A seção 3.5
apresenta os testes computacionais feitos sobre instâncias geradas aleatoriamente.
3.1
Novos Modelos Matemáticos para o Problema dos
Companheiros Estáveis
Nas duas subseções que seguem são apresentados um modelo em programação
quadrática e um em programação linear inteira para o problema dos companheiros
estáveis.
3.1.1
Novo Modelo Quadrático
A forma geral de um modelo de otimização quadrático com variáveis binárias
(quadratic binary program (QBP)) é:
min / max
s.a :
f (x) = xQx
xAi x ≤ ai
(1 ≤ i ≤ m)
xAx = a; B1 x = b1 ; B2 x ≤ b2
onde :
Q, A, Ai ∈ Rn×n ; a, ai ∈ R; B1 ∈ Rm1 ×n ; b1 ∈ Rm1 ;
B2 ∈ Rm2 ×n ; b2 ∈ Rm2 ; x ∈ {0, 1}n e f : {0, 1}n → R
3.1 Novos Modelos Matemáticos para o Problema dos Companheiros Estáveis
58
Para modelar o problema dos companheiros estáveis como um QBP considere as
variáveis binárias xi, j para 1 ≤ i, j ≤ n:
(
xi, j =
1
0
se a pessoa i é associada com a j
c/c
Como xi, j = x j,i e xi,i = 0, tem-se que as variáveis xi, j só tem significado quando
1 ≤ j < i ≤ n. Assim um modelo matemático para este problema pode ser:
n i−1
min
∑ ∑ zi, j
i=2 j=1
s.a :
i−1
n
∑ xi,k pi(k) + ∑
se
k=1
j−1
ou
xk,i pi (k) − pi ( j) ≤ 0
(3-1)
k=i+1
n
∑ x j,k p j (k) + ∑
k=1
xk, j p j (k) − p j (i) ≤ 0
k= j+1
então zi, j = 0 senão zi, j = 1 (1 ≤ j < i ≤ n)
i−1
n
∑ xi, j + ∑
j=1
x j,i = 1 (1 ≤ i ≤ n)
(3-2)
j=i+1
xi, j , zi, j ∈ {0, 1}
(1 ≤ j < i ≤ n)
(3-3)
Onde o objetivo é minimizar o número de blocking pairs. As restrições (31) garantem que zi, j = 1 se e somente se os participantes i e j formam um blocking
pair, enquanto as restrições (3-2) garantem que cada participante tem exatamente um
companheiro.
Introduzindo as variáveis binárias y1i, j e y2i, j , onde zi, j = (1 − y1i, j )(1 − y2i, j ), as
restrições (3-1) podem ser transformadas em:
i−1
y1i, j
xk,i pi (k) − pi ( j)
∑ xi,k pi(k) + ∑
k=1
j−1
y2i, j
!
n
n
∑ x j,k p j (k) + ∑
k=1
≤0
k=i+1
!
xk, j p j (k) − p j (i)
≤ 0.
k= j+1
Assim um QBP para o problema dos companheiros estáveis é:
3.1 Novos Modelos Matemáticos para o Problema dos Companheiros Estáveis
59
n i−1
min
∑ ∑ zi, j
i=2 j=1
s.a :
i−1
y1i, j
!
n
y2i, j
(1 ≤ j < i ≤ n)
(3-4)
!
n
xk, j p j (k) − p j (i)
∑ x j,k p j (k) + ∑
k=1
≤0
(1 ≤ j < i ≤ n) (3-5)
k= j+1
i−1
n
∑ xi, j +
x j,i = 1
j=i+1
zi, j = (1 − y1i, j )(1 − y2i, j )
xi, j , y1i, j , y2i, j , zi, j ∈ {0, 1}
j=1
≤0
k=i+1
j−1
3.1.2
xk,i pi (k) − pi ( j)
∑ xi,k pi(k) + ∑
k=1
∑
(1 ≤ i ≤ n)
(3-6)
(1 ≤ j < i ≤ n)
(3-7)
(1 ≤ j < i ≤ n)
(3-8)
Novo Modelo Linear Inteiro
A forma geral de um modelo de otimização linear com variáveis binárias (linear
binary program (LBP)) é:
min / max
s.a :
onde :
f (x) = cx
A1 x = b1 ; A2 x ≤ b2
c ∈ Rn ; A1 ∈ Rm1 ×n ; A2 ∈ Rm2 ×n ; b1 ∈ Rm1 ; b2 ∈ Rm2 ;
x ∈ {0, 1}n e f : {0, 1}n → R
Note que no QBP proposto na subseção anterior as restrições (3-6) já estão na
forma de LBP, enquanto as restrições (3-4) e (3-5) podem ser escritas como:
i−1
n
∑ xi,k pi(k) + ∑
k=1
j−1
xk,i pi (k) − Ly1i, j ≤ pi ( j) (1 ≤ j < i ≤ n)
k=i+1
n
∑ x j,k p j (k) + ∑
k=1
onde
xk, j p j (k) − Ly2i, j ≤ p j (i) (1 ≤ j < i ≤ n)
k= j+1
L = max{mi, j } (1 ≤ j < i ≤ n).
As restrições (3-7) podem ser transformadas em:
y1i, j + y2i, j − zi, j ≤ 1 (1 ≤ j < i ≤ n)
(Observe que as variáveis yrij do QBP são iguais a 1−yrij do LBP, onde: r ∈ {1, 2}
3.2 Busca Tabu para o Problema dos Companheiros Estáveis
60
e 1 ≤ j < i ≤ n)
Desta forma, aplicando as modificações acima no QBP proposto anteriormente,
obtemos um LBP para o problema dos companheiros estáveis:
n i−1
min
∑ ∑ zi, j
i=2 j=1
s.a :
y1i, j + y2i, j − zi, j ≤ 1
i−1
(1 ≤ j < i ≤ n)
n
∑ xi,k pi(k) +
k=1
j−1
∑
xk,i pi (k) − Ly1i, j ≤ pi ( j) (1 ≤ j < i ≤ n)
k=i+1
n
∑ x j,k p j (k) + ∑
k=1
i−1
xk, j p j (k) − Ly2i, j ≤ p j (i) (1 ≤ j < i ≤ n)
k= j+1
n
∑ xi, j + ∑
x j,i = 1
j=i+1
1
2
xi, j , yi, j , yi, j , zi, j
(1 ≤ i ≤ n)
j=1
3.2
∈ {0, 1}, (1 ≤ j < i ≤ n)
Busca Tabu para o Problema dos Companheiros Estáveis
3.2.1
Forma Geral da Busca Tabu
A Busca Tabu é uma metaheurística, proposta por Fred Glover em 1986, que
está baseada na ideia de busca local. Para aplicar esta metaheurística a um problema é
necessário ter uma definição de vizinhança V (x) para cada solução x e também uma lista
limitada que armazena os movimentos que são considerados tabu. O algoritmo 3.1 mostra
a forma geral da Busca Tabu.
3.2.2
Busca Tabu para o Problema dos Companheiros Estáveis
Nesta proposta definimos a vizinhança de uma solução x como a troca de
parceiros em duas associações da solução:
V (x) = {x̄|∀s ∈ {1, 2} ∃ks , ls : x̄ks ,ls 6= xks ,ls e ∀(i, j) 6= (ks , ls ) x̄i, j = xi, j }
Se a solução x̄ é selecionada de V (x) trocando as associações (k1 , l1 ) e (k2 , l2 )
de x, resulta em (k1 , l2 ) e (k2 , l1 ) em x̄. Então, definimos como movimento tabu qualquer
movimento que coloque juntos k1 com l1 ou k2 com l2 . A capacidade da lista tabu usada
3.3 Branch-and-Bound para o Problema dos Companheiros Estáveis
61
Algoritmo 3.1: Forma geral da Busca Tabu.
Dados: Instância do problema
1 início
2
gere uma solução inicial x
3
x∗ ← x
4
/*crie a lista tabu*/
5
T SList ← {}
6
repita
7
/*obtenha o melhor vizinho sem usar movimentos da lista tabu*/
x ← minx̄∈V (x)\T SList F(x̄)
8
9
/*atualize a lista tabu*/
10
Insera em T SList o último movimento
11
se F(x) < F(x∗ ) então x∗ ← x /*atualize a melhor solução encontrada*/
12
até satisfazer as condições de parada
13 fim
é no máximo 20 e depende do tamanho da instância. O algoritmo 3.2 ilustra a ideia da
nossa proposta, que é baseada na Busca Tabu em [3].
3.3
Branch-and-Bound para o Problema dos Companheiros Estáveis
3.3.1
Forma Geral do Branch-and-Bound
Branch-and-Bound (B&B) são esquemas enumerativos que seguem uma estratégia de divisão e conquista dividindo um problema de otimização em um conjunto de
subproblemas, de forma que a solução do problema original possa ser obtida através da
solução dos subproblemas. As divisões são feitas sempre observando que os subproblemas
devem ser mais fáceis de serem resolvidos que o problema original (e tentando que sejam
disjuntos). Também busca-se descartar subproblemas por enumeração implícita. Para isto
são calculados limites para cada subproblema, geralmente fazendo alguma relaxação do
subproblema (Relaxação Linear, Relaxação Lagrangeana, ou alguma outra). Assim, se o
limite do subproblema não melhora a melhor solução obtida até o momento no algoritmo,
este subproblema não precisa ser solucionado. Em geral, a decomposição em subproblemas é vista recursivamente, o que permite uma representação gráfica do processo em
forma de árvore de enumeração onde a raiz é o problema original, cada nó interno é um
subproblema do nó pai e as folhas são soluções. Uma definição geral do B&B é dada pelo
algoritmo 3.3.
3.3 Branch-and-Bound para o Problema dos Companheiros Estáveis
62
Algoritmo 3.2: Busca Tabu para o Problema dos Companheiros Estáveis.
Dados: Instância do problema dos companheiros estáveis
1 início
2
Gere uma solução inicial x associando o participante i com o i + 1, para cada
i = 1, 3, ..., 2k + 1, ...
3
x∗ ← x
4
/*crie a lista tabu*/
5
T SList ← {}
6
repita
7
/*se há um vizinho de x que é obtido por um movimento que não é tabu e
que melhora a melhor solução até o momento, faça busca local neste
vizinho*/
8
se ∃x̄ ∈ V (x) \ T SList e F(x̄) < F(x∗ ) então
9
/*busca local no vizinho de x*/
10
repita
11
x∗ ← x̄
x̄ ← minx∈V (x̄) F(x)
12
13
até F(x̄) ≥ F(x∗ )
14
x ← x∗
senão
/*atribua a x o melhor vizinho que é obtido por um movimento que não
é tabu*/
x ← minx̄∈V (x)\T SList F(x̄)
15
16
17
/*atualize a lista tabu*/
Insera em T SList o último movimento
até atingir um máximo de iterações
18
19
20
21
fim
3.3.2
Branch-and-Bound para o Problema dos Companheiros Estáveis
Para solucionar o problema dos companheiros estáveis usando Branch-andBound, deve ser definida a decomposição de um problema em subproblemas. Para
isto escolhe-se um candidato livre (que não tenha ainda companheiro) e associando-o
com cada um dos outros candidatos livres cria-se os diferentes subproblemas disjuntos.
A figura 3.1 mostra a árvore de enumeração completa para uma instância com seis
candidatos.
Dessa forma é garantido que o problema de cada nó é a união dos subproblemas
dos filhos que, além disso, são mutuamente independentes.
Como o objetivo é minimizar o número de blocking pairs, para cada subproblema
é preciso definir uma função que calcule um limite inferior. Geralmente é usada uma
relaxação linear, mas nos testes feitos a relaxação linear dos modelos propostos gerou
3.3 Branch-and-Bound para o Problema dos Companheiros Estáveis
63
Algoritmo 3.3: Forma Geral do Branch-and-Bound
Dados: Instância do problema
1 início
2
S ← {problema original}
3
z ← +∞
4
calcule uma relaxação do problema original
5
repita
6
escolha um problema P ∈ S
7
S ← S − {P}
8
se o valor da relaxação de P não é pior que z então
9
se a solução da relaxação de P é inteira então
10
z ← valor da relaxação de P
senão
expanda P em k subproblemas menores: P1 , ..., Pk
para i = 1...k faça
calcule a relaxação de Pi
se o valor da relaxação de Pi não é pior que z então
S ← S ∪ {Pi }
11
12
13
14
15
16
até S = φ
17
18
19
fim
Retorne z
limitantes muito ruins. Portanto, é usada uma função combinatória para obter os limitantes
inferiores, que é mais simples de executar e dá uma boa noção do menor número de
blocking pairs que terá o subproblema. Assim, os candidatos x e y são considerados um
blocking pair pela função que calcula o limite (o que é, aumentar em uma unidade o valor
do limite), se:
• x e y não estão livres e cada um prefere ao outro do que ao candidato com quem
foram associados.
• x não é livre e y é livre, e x prefere a y ao invés do canditado com quem foi associado,
e para todo candidato z que seja livre, y prefere x do que z.
Para calcular este limitante é necessário analisar todos os possíveis pares (sendo
pares) e ver se formam blocking pairs (que tem um custo O(n)). O que implica um
esforço computacional de O(n3 ). Porém esse processo pode ser feito em O(n2 ) dividindoo em duas fases de O(n2 ) cada uma, mas a diferença entre um subproblema e o do pai é
que tem um par de candidatos a mais que não são livres. Portanto, usando essa informação
a segunda fase pode ser calculada em O(n). O algoritmo 3.4 mostra como calcular o limite
inferior de um nó, usando o valor do limite do nó pai.
O(n2 )
3.3 Branch-and-Bound para o Problema dos Companheiros Estáveis
64
Figura 3.1: Os valores dentro dos vértices indicam o candidato
livre que foi selecionado para gerar os subproblemas
desse nó, enquanto os valores das arestas são os candidatos livres que foram associados com o selecionado
para gerar o subproblema. As folhas mostram o último
par de candidatos emparelhados e é apressentada a
solução associada à folha.
A seleção do nó que irá se expandir é feita dando prioridade à altura do nó na
árvore de busca, se há dois nós com igual altura então é selecionado aquele com menor
limite inferior. O algoritmo 3.5 mostra esta ideia.
3.3.3
Estratégias para Melhorar o Desempenho do Branch-andBound
Para um melhor desempenho do Branch-and-Bound foram usadas as seguintes
estratégias:
Solução Inicial. É bem sabido que uma boa solução inicial geralmente garante
um melhor desempenho do Branch-and-Bound, permitindo que sejam cortados mais nós e
evitando assim analisar subproblemas onde não há ótimos. Para calcular uma boa solução
inicial é usada uma busca local que aumenta a vizinhança se não encontra uma melhor
solução na vizinhança atual, o algoritmo 3.6 mostra a ideia desta busca local.
A solução inicial da busca local anterior é gerada por um processo similar ao
proposto em [21] para obter emparelhamentos super-estáveis. Os algoritmos 3.7 e 3.8
mostram as fases um e dois deste processo.
Após aplicar a segunda fase teremos um emparelhamento que se não é superestável terá participantes sem companheiros. Portanto, para gerar uma solução viável é
aplicado, sobre a solução da segunda fase, um processo guloso descrito pelo algoritmo
3.9.
As vizinhanças V1 e V2 usadas pelo algoritmo 3.6 são definidas como:
3.3 Branch-and-Bound para o Problema dos Companheiros Estáveis
65
Algoritmo 3.4: Algoritmo para calcular o limite inferior de um nó a partir do limite
inferior do pai. Note que para este algoritmo ser O(n), deve ser pré-calculada uma
estrutura que permita saber para cada candidato livre quais dos restantes candidatos
livres ele prefere; o processo para calcular isto tem um custo computacional de
O(n2 ).
Dados: lb ← limite inferior do pai
[x, y] ← candidatos associados para gerar o subproblema
1 início
2
para cada candidato z tal que z 6= x e z 6= y faça
3
/*Analise se z forma um blocking pair com x e/ou y*/ se z não é livre então
4
/*Analise se z forma um blocking pair com x e/ou y considerado no nó
pai*/ se z prefere x ao invés do candidato com quem foi associado e x
prefere z ao invés de y e existe um candidato livre t que x prefere ao
invés de z ou x é indiferente entre t e z então lb ← lb + 1
5
se z prefere y ao invés do candidato com quem foi associado e y prefere
z ao invés de x e existe um candidato livre t que y prefere ao invés de z
ou y é indiferente entre t e z então lb ← lb + 1
6
senão
7
se x prefere z ao invés de y e não há um candidato livre t que z prefere
ao invés de x ou z seja indiferente entre t e x então lb ← lb + 1
8
se y prefere z ao invés de x e não há um candidato livre t que z prefere
ao invés de y ou z seja indiferente entre t e y então lb ← lb + 1
9
fim
Algoritmo 3.5: Processo de seleção do nó a ser explorado
Dados: L: lista de nós
1 início
2
node ← primeiro nó em L
3
para cada nó no em L faça
4
se Height(no) > Height(node) or
(Height(no) = Height(node) e lb(no) < lb(node)) então node ← no
5
fim
3.3 Branch-and-Bound para o Problema dos Companheiros Estáveis
Algoritmo 3.6: Busca local aumentando a vizinhança
Dados: Instância do problema dos companheiros estáveis
1 início
2
s ← solução inicial, calculada por um algoritmo guloso baseado na proposta de
[21]
3
repita
4
t ← melhor solução em V1 (s)
5
se t melhora s então s ← t
6
senão
7
t ← melhor solução em V2 (s)
8
se t melhora s então s ← t
até não seja melhorada a solução s
9
10
fim
Algoritmo 3.7: Primeira fase do processo para obter uma solução inicial para a
busca local
Dados: listas dos participantes
1 início
2
repita
3
p ← um participante livre que não tem lista vazia
4
para cada participante q na frente da lista de p faça
5
associe p com q
6
para cada sucessor estrito r de p na lista de q faça
7
se r está associado com q então quebre associação
8
elimine o par {q, r}/*elimine q da lista de r e r da lista de q*/
se Há dois ou mais participantes associados a q então
quebre todas as associações com q
para cada r empatado com p na lista de q (incluindo o próprio p)
faça
elimine o par {q, r}
9
10
11
12
até as listas de todos os participantes livres estejam vazias
13
14
fim
66
3.4 Melhorando as Implementações com Programação Paralela em GPUs
67
Algoritmo 3.8: Segunda fase do processo para obter uma solução inicial para a
busca local
Dados: Instância do problema dos companheiros estáveis
1 início
2
T ← tabela com lista s de preferências resultante ao aplicar a primeira fase na
tabela de preferências dos dados
3
repita
4
x ← um participante com mais de um elemento na sua lista em T
5
y ← um participante que tem a x na frente da lista de preferência em T
6
z ← o participante que está na frente da lista de x em T
7
Tx ← tabela resultante ao eliminar todos os pares {z, w} de T , onde w
empata ou sucede a x na lista de z
8
Tx ← tabela resultante ao aplicar a primeira fase em Tx
9
se Tx tem o mesmo número de listas vazias que T então T ← Tx
10
senão
11
Ty ← tabela resultante ao eliminar todos os pares {x, w} de T , onde w
empata ou sucede a y na lista de x
12
T ← tabela resultante ao aplicar a primeira fase em Ty
até todas as listas em T tenham no máximo um elemento ou T não mude o
valor
13
14
fim
• V1 (x) = {y|y é um emparelhamento ∩ ∃i, j : x(i) = y( j) ∩ x( j) = y(i) ∩ ∀k 6∈
{i, j, x(i), x( j)} : x(k) = y(k)}
• V2 (x) = {y|y é um emparelhamento ∩ ∃i, j, k : x(i) = y( j) ∩ x( j) = y(k) ∩ x(k) =
y(i) ∩ ∀l 6∈ {i, j, k, x(i), x( j), x(k)} : x(l) = y(l)}
Caminho da Melhor Solução. Dado que em muitos casos uma boa solução é
parecida a uma ótima, outra estratégia usada é seguir o caminho da melhor solução obtida
até o momento na árvore de busca tentando encontrar antes o valor ótimo. Para aplicar esta
ideia é só necessário uma simples modificação no método de selecionar o nó, o algoritmo
3.10 mostra esta ideia.
3.4
Melhorando as Implementações com Programação
Paralela em GPUs
Nesta seção apresentam-se as ideias principais dos processos em paralelo usando
GPUs, que foram usados para melhorar o desempenho dos algoritmos.
Na Busca Tabu consideramos:
(a) no início do processo é copiada a matriz de preferências da memória da CPU para
a memória compartilhada das GPUs;
3.4 Melhorando as Implementações com Programação Paralela em GPUs
68
Algoritmo 3.9: Processo guloso para obter uma solução inicial viável para a busca
local
Dados: solução parcial
tabelas de preferências
1 início
2
para cada candidato x livre faça
3
y ← o candidato livre que x prefere
4
associe x com y na solução
5
fim
Algoritmo 3.10: Método modificado de seleção do nó a ser explorado
Dados: L: lista de nós
best: melhor solução até o momento
1 início
2
node ← primeiro nó em L
3
para cada nó no em L faça
4
if Height(no) > Height(node) ou (Height(no) = Height(node) e (best ∈
subproblem(no) ou (best 6∈ subproblem(node) e lb(no) < lb(node))))
then node ← no;
5 fim
(b) em cada iteração:
(i) o maior tempo computacional é dado pela avaliação da função objetivo na
vizinhança da solução atual, assim para cada vizinho é criado um thread que
calcula o valor da função objetivo. Isto requer copiar o vetor da solução atual
do espaço de memória da CPU para o das GPUs;
(ii) para selecionar o melhor vizinho dos O(n2 ) que existem, são criados n threads
cada um para selecionar o melhor vizinho de uma subvizinhança de O(n),
para isto não é necessário transferência de dados pois já estão na memória das
GPUs.
(iii) copiar da memória das GPUs para a da CPU os n vizinhos que foram
selecionados como melhores pelos threads em [(ii)].
Na busca local foram consideradas as ideias da Busca Tabu para melhorar o
desempenho da mesma com paralelismo.
No Branch-and-Bound consideramos:
(a) no início de processo é copiada a matriz de preferências da memória da CPU para
a memória compartilhada das GPUs;
(b) em cada iteração:
3.5 Experimentos Computacionais
69
(i) o maior tempo computacional é dado pelo cálculo do limite inferior de cada
novo nó, assim para cada candidato livre é criado um thread que procura o
candidato que ele prefere. Isto requer copiar o vetor com a informação de
quais candidatos estão livres do espaço de memória da CPU para o das GPUs;
(ii) é criado um thread para cada um dos novos nós que calcula em O(n) o
limitante inferior dos subproblemas. Copiando da memória das GPUs para
a da CPU um vetor com os valores dos limitantes.
3.5
Experimentos Computacionais
Não foram encontradas na literatura instâncias para o problema dos companheiros estáveis, por esta razão foram geradas 100 instâncias aleatórias divididas em dez
classes, cada classe com dez instâncias.
Para analisar o desempenho das variantes do Branch-and-Bound propostas comparamos com as soluções do ILOG CPLEX 9.0 usando o nosso LBP. As implementações
das variantes do Branch-and-Bound usam o compilar C++ Builder 6 da Borland, e os
testes foram feitos em um processador Intel Core 2 Duo com 2.8GHz e 4 GB de RAM
sob Windows Vista. Somente usamos o LBP porque o CPLEX foi projetado para solucionar em primeiro lugar problemas de otimização linear, portanto os algoritmos e teoria
que usa, em geral, dão vantagem aos modelos lineares. De fato, com o QBP o CPLEX
demorou horas sem encontrar boas soluções, o que indica que demoraria ainda mais para
encontrar soluções ótimas.
A tabela 3.1 mostra os resultados obtidos pelo CPLEX e o Branch-and-Bound
proposto para as cinco primeiras classes de instâncias. Não são apresentados resultados
para as maiores classes, porque tanto o CPLEX quanto as variantes do Branch-and-Bound
consumiram muito tempo sem chegar a soluções ótimas. As colunas Solução, Tempo e
Nós, representam, respectivamente, os valores de: solução obtida, tempo de execução em
segundos e número de nós na árvore de enumeração do CPLEX, o Branch-and-Bound e
o Branch-and-Bound com a estrategia de seguir o caminho da melhor solução.
Na tabela 3.1 se pode ver que, nas primeiras quatro classes, as nossas propostas
usam mais nós na árvore de enumeração do que o CPLEX; porém essa diferença diminui
à medida que aumenta o tamanho das instâncias, o que se reflete no fato de que para a
quinta classe (que tem as maiores instâncias) o número de nós requeridos por uma das
nossas propostas é menor que o do CPLEX. Por outro lado, o tempo de execução do
CPLEX é maior em todos os testes que os dos nossos algoritmos; e no caso da quinta
classe, após dias de execução, o CPLEX não conseguiu soluções ótimas para todas as
instâncias, enquanto os nossos algoritmos conseguiram em questão de horas. Também é
3.5 Experimentos Computacionais
Classe
1
2
3
4
5
Solução
0*
0.1 *
0.2 *
0*
0.3
70
CPLEX
Tempo
Nós
0.8
0
1
1.6
3
186
19.7
752
104750 4414040
Solução
0*
0.1*
0.2*
0*
0.2*
B&B
Tempo
0
0
1.8
13.9
7310
Nós
3
15
1567
5259
4760523
B&Bcaminho
Solução Tempo
Nós
0*
0
3
0.1*
0
15
0.2*
1
1034
0*
3
1175
0.2*
1015 1057894
Tabela 3.1: Soluções do CPLEX e das variantes do Branch-andBound. O (*) indica que todas as soluções da classe
foram ótimas.
evidente que, para estas instâncias, a estratégia de seguir o caminho da melhor solução
melhora o desempenho do Branch-and-Bound.
A implementação da Busca Tabu usou o compilador GNU C++ e os experimentos foram feitos em um PC Intel Core 2 Duo, 2.4GHz e 2GB de RAM sob Ubuntu 9.04 e
os testes em paralelo usaram uma placa NVIDIA GeForce GTS 250.
A tabela 3.2 mostra a média dos resultados para cada classe de instâncias, onde as
colunas Candidatos, Pares, Ótimo, Solução da TS, Tempo Sequencial e Tempos Paralelo
representam, respectivamente, os valores de: número de pessoas nas instâncias da classe,
número de possíveis pares, valor da solução ótima, valor da solução da Busca Tabu, e
tempos de execução em segundos para a implementação sequencial e a que usa processos
em paralelo.
Classe
1
2
3
4
5
6
7
8
9
10
Candidatos
10
20
30
40
50
60
70
80
90
100
Pares
45
190
435
780
1225
1770
2415
3160
4005
4950
Ótimo
0
0.1
0.2
0
0.2
-
Solução da TS
0*
0.1 *
0.2 *
0.1
0.3
1.4
3.2
3.6
6
20.2
Tempo Sequencial
0
1
6.8
13.8
116
834
1035
1571
2073
2787
Tempo Paralelo
0
1
5.1
6.4
61.6
120
229
430
503
641
Tabela 3.2: Soluções da Busca Tabu. O (*) indica que todas as
soluções da classe foram ótimas.
Na tabela 3.2 pode-se ver que os resultados obtidos pela Busca Tabu parecem ser
muito bons, dado que as soluções apresentam poucos blocking pairs e em vários casos
foram atingidos os valores ótimos.
Por outro lado, é notável que com o uso dos processos paralelos em GPUs
aumenta a velocidade de execução dos algoritmos. Neste caso vemos como à medida que
3.5 Experimentos Computacionais
71
aumenta o tamanho das instâncias o tempo de execução da implementação sequencial vai
sendo cada vez maior que o da implementação que usa paralelismo. Isto mostra que o
uso de processos em paralelo com GPUs para problemas de otimização pode melhorar
consideravelmente o desempenho dos algoritmos.
CAPÍTULO 4
Problema da Mochila Compartimentada
O problema da mochila compartimentada pode ser visto como uma generalização
do problema clássico da mochila (que tem somente um compartimento), onde se considera
um conjunto de itens agrupados em diferentes classes a serem alocados em uma mochila
e itens de classes diferentes devem estar em compartimentos diferentes da mochila.
Este problema foi modelado em [15], onde considerava a inclusão de no máximo um
compartimento para cada classe de itens, que é um caso particular do problema que foi
modelado por [14, 28, 30].
Em [28, 30] foram propostas diferentes heurísticas gulosas para solucionar esse
problema. Em [14] foram consideradas duas abordagens para o problema, uma restrita
e outra irrestrita, esta última considera uma quantidade ilimitada de itens. Em [17] foi
proposto um método baseado em geração de colunas.
A maioria dos modelos matemáticos para o problema da mochila compartimentada eram quadráticos, mas em [35] foi apresentada uma modelagem linear inteira para o
problema. Em [27] é proposta uma heurística que combina as ideias descritas em [28, 30]
e também foi implementada uma outra heurística que usa geração de colunas.
Este capítulo é organizado como segue. Na seção 4.1 é discutida uma modelagem
quadrática para o problema da mochila compartimentada. Na seção 4.2 se mostra como,
modificando o modelo quadrático, é obtido um modelo linear inteiro para o problema.
A seção 4.3 apresenta uma heurística gulosa e um algoritmo baseado no GRASP que
usa path-relinking. A seção 4.4 mostra os testes computacionais com instâncias geradas
aleatoriamente.
4.1
Modelo Quadrático do Problema da Mochila Compartimentada
Na continuação apresentamos o modelo que corresponde a um problema não
linear inteiro e foi tomado de [27].
4.1 Modelo Quadrático do Problema da Mochila Compartimentada
73
Dados:
•
•
•
•
•
•
•
•
•
•
•
•
L: capacidade da mochila;
N = {1, ..., n}: define o cojunto de tipos de itens;
li : peso do item i, i = 1, ..., n;
vi : valor utilidade do item tipo i, i = 1, ..., n;
σi : número máximo de itens tipo i permitido na mochila, i = 1, ..., n;
K: número total de classes;
Ak : conjunto dos itens pertencentes à classe k, k = 1, ..., K, N = A1 ∪ A2 ∪ ... ∪
Ak e Ai ∩ A j = φ para i 6= j;
ck : custo pela inclusão de um compartimento para itens da classe k, k = 1, ..., K;
k : capacidade mínima do compartimento para itens da classe k, k = 1, ..., K;
Lmin
k : capacidade máxima do compartimento para itens da classe k, k = 1, ..., K;
Lmax
Sk : perda na mochila devido à inclusão de um compartimento para itens da classe
k, k = 1, ..., K;
Nk : número total de possíveis compartimentos da classe k, k = 1, ..., K.
Variáveis:
• aisk : número de itens do tipo i da classe k no compartimento s, i = 1, ..., n, k =
1, ..., K e s = 1, ..., Nk ;
• βsk : número de vezes que o compartimento s para itens da classe k é repetido na
mochila, k = 1, ..., K e s = 1, ..., Nk .
Para evitar situações triviais, supomos que para k = 1, ..., K:
k ;
• ∑i∈Ak σi li > Lmax
k
• li < Lmax,
i∈Ak ;
k
k
• Lmin < Lmax ≤ L.
O modelo em programação quadrática é o seguinte:
K
max
∑ ∑ ∑ viaisk − ck
k=1 s=1
K
s.a :
!
Nk
!
Nk
∑ ∑ ∑ liaisk + Sk
k=1 s=1
K
βsk
i∈Ak
βsk ≤ L
i∈Ak
Nk
∑ ∑ aisk βsk ≤ σi,
k=1 s=1
k
Lmin
≤
i ∈ Ak
k
,
∑ liaisk + Sk ≤ Lmax
k = 1, ..., K, s = 1, ..., Nk
i∈Ak
aisk ≥ 0, inteiro,
i = 1, ..., n, k = 1, ..., K, s = 1, ...Nk
βsk ≥ 0, inteiro,
k = 1, ..., K, s = 1, ...Nk .
4.1 Modelo Quadrático do Problema da Mochila Compartimentada
4.1.1
74
Observações
No modelo quadrático são propostos os seguintes tipos de restrições:
k
Lmin
≤
k
,
∑ liaisk + Sk ≤ Lmax
k = 1, ..., K, s = 1, ..., Nk
i∈Ak
Mas o termo Sk não precisa estar nelas, pois indica a perda pela inclusão de um
compartimento para a classe k, e estas restrições impedem que um compartimento da
k , dado que as restrições dizem que o máximo
classe k tenha o máximo peso possível Lmax
k − S . Logo as restrições podem ser re-escritas como:
seria Lmax
k
k
Lmin
≤
k
,
∑ liaisk ≤ Lmax
k = 1, ..., K, s = 1, ..., Nk
i∈Ak
Também podemos ver que as variáveis βsk podem ser consideradas binárias, onde
βsk = 1 se o compartimento s da classe k é aberto na mochila e βsk = 0 caso contrário.
Sendo então Nk o máximo número de compartimentos que pode ter a classe k.
Outra observação é que nas restrições:
k
Lmin
≤
k
,
∑ liaisk ≤ Lmax
k = 1, ..., K, s = 1, ..., Nk
i∈Ak
Quando o compartimento s na classe k não é aberto, ela ainda exige que tenha
itens neste compartimento. Logo uma modificação seria:
k
βsk Lmin
≤ βsk
k
,
∑ liaisk ≤ βsk Lmax
k = 1, ..., K, s = 1, ..., Nk
i∈Ak
Levando em consideração estas observações, as restrições da forma:
K Nk
∑ ∑ aisk βsk ≤ σi, i ∈ Ak
k=1
ficam na forma:
K Nk
∑ ∑ aisk ≤ σi,
k=1
Assim, o modelo que consideramos é:
K
min
!
Nk
∑ ∑ ∑ viaisk − ck
k=1 s=1
i∈Ak
βsk
i ∈ Ak
4.1 Modelo Quadrático do Problema da Mochila Compartimentada
K
s.a :
75
!
Nk
∑ ∑ ∑ liaisk + Sk
k=1 s=1 i∈Ak
k
βsk Lmin
≤ βsk
βsk ≤ L
k
,
∑ liaisk ≤ βsk Lmax
k = 1, ..., K, s = 1, ..., Nk
i∈Ak
K
Nk
∑ ∑ aisk ≤ σi,
i ∈ Ak
aisk ≥ 0, inteiro,
i = 1, ..., n, k = 1, ..., K, s = 1, ..., Nk
k=1 s=1
βsk ∈ {0, 1},
4.1.2
k = 1, ..., K, s = 1, ..., Nk
Exemplo
Considere o exemplo exposto em [27]: tem-se uma mochila com tamanho igual
a 28mm e as informações dos itens que podem compor a mochila são dadas na tabela 4.1:
Classe 1
item
1 2 3
utilidade
7 8 4
largura (mm) 3 4 6
Classe 2
4 5 6
3 5 7
5 2 4
Classe 3
7 8 9
6 2 4
5 3 4
Tabela 4.1: Dados dos itens do exemplo
As classes são: A1 = {1, 2, 3}, A2 = {4, 5, 6} e A3 = {7, 8, 9}; os tamanhos
mínimo (Lmin ) e máximo (Lmax ), respectivamente, para os compartimentos da classe 1
são dados por 5 e 9, para a classe 2 são 5 e 10, e para a classe 3 são 3 e 10. A inclusão de
compartimentos com itens da classe 2 na mochila ocasiona perda de S2 = 4mm (2mm em
cada lateral), para a classe 1 e 3 não há perdas, S1 = S3 = 0.
Um possível padrão compartimentado é mostrado na Figura 4.1. Neste padrão
foram incluídos: dois itens do tipo 2 da classe 1; um item do tipo 5 e um do tipo 6 da
classe 2; dois itens do tipo 7 da classe 3. Sendo então o valor total de utilidade obtido de
40. Esta é uma possível solução, mas não é ótima.
Figura 4.1: Padrão compartimentado não ótimo
Na Figura 4.2 é mostrada uma solução ótima. Nesta solução foram feitos quatro
compartimentos da classe 1: o primeiro compartimento tem um item do tipo 1 e um item
do tipo 2, o segundo e o terceiro compartimentos têm, cada um deles, dois itens do tipo 1,
e o quarto compartimento tem três itens do tipo 1; sendo que a utilidade obtida neste caso
é de 64, que é bem maior que 40.
4.2 Modelo Linear Inteiro para o Problema da Mochila Compartimentada
76
Figura 4.2: Padrão compartimentado ótimo
4.2
Modelo Linear Inteiro para o Problema da Mochila
Compartimentada
Analisando o modelo quadrático se nota que a função objetivo é quadrática
devido ao produto das variáveis aisk com as βsk . Mas, temos que o objetivo é maximizar
a soma das utilidades dos itens incluídos menos a soma dos custos dos compartimentos
usados na solução:
K
max ∑
!
Nk
− ck βsk
∑ ∑ viaisk
k=1 s=1
i∈Ak
Sendo só necessário ter alguma restrição que garanta:
(
βsk =
0 se ∃i ∈ Ak tq aisk > 0
1 se ∀i ∈ Ak , aisk = 0
Ou seja, se um item é incluído, então tem que ser dentro de um compartimento da mesma
classe dele, e se um compartimento é aberto, então ele tem que ter pelo menos um item.
Uma restrição que garante isto é:
aisk = βsk aisk ,
i = 1, ..., n, k = 1, ..., K, s = 1, ...Nk
Com isto a restrição quadrática:
K
!
Nk
∑ ∑ ∑ liaisk + Sk
k=1 s=1
βsk ≤ L
i∈Ak
se torna:
K
!
Nk
∑ ∑ ∑ liaisk
k=1 s=1
+ Sk βsk ≤ L
i∈Ak
E as restrições da forma:
k
Lmin
βsk ≤ βsk
k
,
∑ liaisk ≤ βsk Lmax
i∈Ak
k = 1, ..., K, s = 1, ..., Nk
4.2 Modelo Linear Inteiro para o Problema da Mochila Compartimentada
77
se tornam:
k
Lmin
βsk ≤
k
,
∑ liaisk ≤ βsk Lmax
k = 1, ..., K, s = 1, ..., Nk
i∈Ak
Assim, é obtido o seguinte modelo para o problema da mochila compartimentada:
K
max
− ck βsk
∑ ∑ ∑ viaisk
k=1 s=1
K
s.a :
!
Nk
i∈Ak
!
Nk
li aisk
k=1 s=1 i∈Ak
k
Lmin
βsk ≤
li aisk
i∈Ak
∑∑ ∑
∑
aisk ≥ 0, inteiro,
K
+ Sk βsk ≤ L
k
≤ βsk Lmax
,
k = 1, ..., K, s = 1, ..., Nk
i = 1, ..., n, k = 1, ..., K, s = 1, ...Nk
Nk
∑ ∑ aisk ≤ σi,
i = 1, ..., n
k=1 s=1
aisk = βsk aisk ,
bsk ∈ {0, 1},
i = 1, ..., n, k = 1, ..., K, s = 1, ...Nk
k = 1, ..., K, s = 1, ...Nk
O modelo é “quase” linear inteiro, sendo somente quadráticas as restrições:
aisk = βsk aisk ,
i = 1, ..., n, k = 1, ..., K, s = 1, ...Nk
O objetivo destas restrições é garantir:
(
βsk =
0
1
se ∃i ∈ Ak tal que aisk > 0
se ∀i ∈ Ak , aisk = 0
Mas isto é garantido pelas restrições do tipo:
k
Lmin
βsk ≤
k
,
∑ liaisk ≤ βsk Lmax
k = 1, ..., K, s = 1, ..., Nk
i∈Ak
Elas também garantem que cada compartimento aberto esteja nos limites estabelecidos para ele. Assim, são desnecessárias as restrições quadráticas e é obtido o seguinte
modelo linear inteiro.
K
max
!
Nk
∑ ∑ ∑ viaisk
k=1 s=1
i∈Ak
− ck βsk
4.2 Modelo Linear Inteiro para o Problema da Mochila Compartimentada
K
s.a :
!
Nk
li aisk
k=1 s=1 i∈Ak
k
Lmin
βsk ≤
li aisk
i∈Ak
∑∑ ∑
∑
K
78
+ Sk βsk ≤ L
k
≤ βsk Lmax
,
k = 1, ..., K, s = 1, ..., Nk
Nk
∑ ∑ aisk ≤ σi,
i = 1, ..., n
aisk ≥ 0, inteiro,
i = 1, ..., n, k = 1, ..., K, s = 1, ...Nk
k=1 s=1
bsk ∈ {0, 1},
k = 1, ..., K, s = 1, ...Nk
O modelo linear obtido acima é parecido ao proposto em [35]:
K
max
Nk
∑ ∑ ∑ viaisk
k=1 s=1 i∈Ak
K
s.a :
Nk
li aisk ≤ L
k=1 s=1 i∈Ak
k
k
Lmin
βsk ≤
li aisk ≤ βsk Lmax
,
i∈Ak
(4-1)
∑∑∑
∑
K
k = 1, ..., K, s = 1, ..., Nk
(4-2)
Nk
∑ ∑ aisk ≤ σi,
i = 1, ..., n
(4-3)
k=1 s=1
K Nk
∑ ∑ βsk ≤ F1
(4-4)
∑ aisk ≤ F2, k = 1, ..., K, s = 1, ...Nk
∑ liaisk ≥ ∑ liai(s+1)k , k = 1, ..., K, s = 1, ..., Nk
(4-5)
k=1 s=1
i∈Ak
i∈Ak
(4-6)
i∈Ak
aisk ≥ 0, inteiro,
bsk ∈ {0, 1},
i = 1, ..., n, k = 1, ..., K, s = 1, ...Nk
k = 1, ..., K, s = 1, ...Nk
onde F1 e F2 , são constantes para limitar, respectivamente, o número de compartimentos
da mochila e o número de itens em um compartimento.
Note-se que as diferenças entre o modelo linear obtido e o apresentado em [35]
são pequenas:
• Tanto na função objetivo quanto nas restrições 4-1, o modelo descrito em [35]
desconsidera os custos e as perdas de espaço por inclusão de compartimentos na
mochila.
• As restrições 4-2 e 4-4 são exatamente as mesmas em ambos os modelos.
• O modelo dado em [35] considera as restrições 4-4 e 4-5 que expressam, respectivamente, limitantes para o número de compartimentos e o número de itens em um
4.3 Algoritmos
79
compartimento.
• As restrições 4-6 do modelo proposto em [35] fazem uma ordenação dos compartimentos para eliminar soluções simétricas.
4.3
Algoritmos
Nesta seção são apresentadas propostas algorítmicas para tentar solucionar o
problema da mochila compartimentada. A primeira delas é uma heurística gulosa baseada
na solução do problema clássico da mochila, enquanto a segunda é uma metaheurística
baseada no GRASP que ao invés de busca local usa path-relinking.
4.3.1
Heurística Gulosa
A heurística gulosa que propomos primeiramente soluciona para cada classe
de itens o problema clássico da mochila, com capacidades entre o tamanho mínimo e
máximo de cada compartimento. Depois adiciona na mochila o compartimento de maior
valor em proporção com o espaço ocupado por ele, e atualiza os dados para esta classe de
itens, solucionando novamente o problema clássico da mochila desta classe. O processo
é repetido até que não seja possível incluir mais compartimentos ou a inclusão deles não
produza ganhos. O algoritmo 4.1 mostra a ideia deste procedimento.
Algoritmo 4.1: Heurística Gulosa para o problema da Mochila Compartimentada
Dados: Instância do problema da mochila compartimentada
1 início
2
para cada classe de itens k faça
k e Lk
3
Solucione o problema clássico da mochila para os valores entre Lmin
max
repita
Valor(Compk )
Ck ← compartimento Compk que maximiza Tamanho(Comp
, onde k é a
k)
classe do compartimento e Valor(Compk ) > 0
se foi selecionado um compartimento Ck então
Adicione-o na mochila
Atualize as demandas da classe k e as soluções desta classe do
k e Lk
problema clássico da mochila para os valores entre Lmin
max
4
5
6
7
8
até não adicionar um novo compartimento na solução
9
10
fim
4.3.2
GRASP usando Path-Relinking
A forma geral do GRASP foi mostrada no capítulo 2, enquanto o algoritmo 4.2
mostra a forma geral do path-relinking. O path-relinking é uma heurística onde dadas
4.4 Experimentos Computacionais
80
duas soluções x1 e x2 , ela faz movimentos de x1 para x2 passando por diferentes soluções
que têm características de ambas as soluções x1 e x2 .
Algoritmo 4.2: Forma geral do Path-relinking
Dados: xdest : solução destino
xorig : solução origem
1 início
2
xmelhor ← xorig
3
repita
4
xorig ← vizinho de xorig que minimiza a diferença simétrica entre xorig e
xdest
5
se xorig é melhor que xmelhor então
6
xmelhor ← xorig
até xorig = xdest
retorne xmelhor
7
8
9
fim
Nossa proposta é utilizar o path-relinking nas iterações do GRASP ao invés de
usar uma busca local. O algoritmo 4.3 descreve esta ideia.
4.4
4.4.1
Experimentos Computacionais
Instâncias
As propostas algorítmicas foram testadas sobre instâncias aleatórias geradas
como descrito em [27, 31]. Como as instâncias de [27, 31] não estavam disponíveis
não foram comparados os nossos algoritmos com os da literatura. Foram fixados para
todas as intâncias: a capacidade da mochila, os tamanhos mínimo e máximo para cada
compartimento, e a perda de espaço na mochila quando um compartimento é incluído. A
tabela 4.2 mostra os valores para estes parâmetros.
Os parâmetros gerados aleatoriamente foram: o tamanho e o valor dos itens, e o
custo pela inclusão de um compartimento. A tabela 4.3 mostra os intervalos dos valores
destes parâmetros.
Foram geradas 200 instâncias agrupadas em 10 classes de 20 instâncias cada
uma. A descrição destas classes é dada na tabela 4.4.
4.4.2
Resultados Computacionais
As implementações usaram o compilador GNU C++ e todos os experimentos
foram feitos em um PC Intel Core 2 Duo, 2.4GHz e 2GB de RAM sob Ubuntu 9.04.
Para comparar as soluções obtidas com as dos modelos, o modelo linear foi solucionado
4.4 Experimentos Computacionais
Algoritmo 4.3: Algoritmos baseado no GRASP e no Path-relinking
Dados: Instância do problema da mochila compartimentada
1 início
2
xmelhor ← solução obtida aplicando a heurística gulosa descrita na seção
anterior
3
repita
4
x ← solução obtida aplicando a heurística gulosa descrita na seção anterior,
só que adicionando o melhor compartimento com uma probabilidade p
5
/*ideia similar ao path-relinking*/
6
repita
7
/*se x melhora a melhor solução, então atualize a melhor solução*/
8
se x melhora xmelhor então
9
x̄ ← x
10
x ← xmelhor
11
xmelhor ← x̄
k ← classe de itens onde é maior a diferença entre as utilidades dos
compartimentos entre xmelhor e x
x ← elimine os compartimentos da classe k em x e, se necessário, os
piores compartimentos de outras classes para alocar em x os
compartimentos da classe k de xmelhor
até x = xmelhor
até satisfazer as condições de parada
retorne xmelhor
12
13
14
15
16
17
fim
Parâmetro
Valor
Capacidade da Mochila
1200mm
Capacidade Mínima de um Compartimento 154mm
Capacidade Máxima de um Compartimento 456mm
Perda por Incluir um Compartimento
4mm
Tabela 4.2: Parâmetros fixos para todas as intâncias
Parâmetro
Valor Mínimo Valor Máximo
Tamanho de um Item
20mm
444mm
Valor de Utilidade de um Item
20
888
Custo de um Compartimento
1
100
Tabela 4.3: Parâmetros aleatórios para todas as intâncias
81
4.4 Experimentos Computacionais
Classe
1
2
3
4
5
6
7
8
9
10
82
Número de Classes de Itens
entre 3 e 10
entre 3 e 10
entre 11 e 20
entre 11 e 20
entre 11 e 20
entre 11 e 20
entre 11 e 20
entre 11 e 20
entre 11 e 20
entre 11 e 20
Número de Itens
entre 7 e 15
entre 7 e 15
entre 1 e 6
entre 1 e 6
entre 1 e 6
entre 1 e 6
entre 7 e 15
entre 7 e 15
entre 7 e 15
entre 7 e 15
Número de Itens Livres
entre 8 e 20
entre 8 e 20
entre 1 e 7
entre 1 e 7
entre 8 e 20
entre 8 e 20
entre 1 e 7
entre 1 e 7
entre 8 e 20
entre 8 e 20
Demanda dos Itens
entre 1 e 3
entre 4 e 15
entre 1 e 3
entre 4 e 15
entre 1 e 3
entre 4 e 15
entre 1 e 3
entre 4 e 15
entre 1 e 3
entre 4 e 15
Tabela 4.4: Descrição das classes de instâncias
utilizando o pacote GLPK (GNU Linear Programming Kit) que tem implementada uma
série de algoritmos que, de forma exata, soluciona problemas lineares inteiros.
A tabela 4.5 mostra a média dos resultados obtidos, dando um tempo limite de
600 segundos (10 minutos) ao processamento de cada instância pelo GLPK. A coluna
GAP é referente ao dado pelo GLPK para a solução encontrada pelo software, enquanto
as colunas Solução e Tempo, referem-se a média das soluções encontradas e dos tempos
de execução em segundos.
Classe
1
2
3
4
5
6
7
8
9
10
GAP
1.37
3.43
1.57
0.94
1.95
2.15
1.71
1.23
1.78
1.33
GLPK
Solução
2243
2211
2164
2216
2242
2267
2230
2268
2261
2300
Tempo
541
497
359
192
589
529
460
441
498
539
Heurística Gulosa
Solução Tempo
2271
0
2291
0
2177
0
2200
0
2291
0
2276
0
2228
0
2237
0
2264
0
2287
0
GRASP & Path-relinking
Solução
Tempo
2275
0
2291
0
2292
0
2221
0
2291
0
2315
0
2263
0
2298
0
2305
0
2341
0
Tabela 4.5: Soluções para o Problema da Mochila Compartimentada
A tabela 4.5 mostra como os resultados obtidos pelos nossos algoritmos são
melhores que os conseguidos pelo GLPK para as mesmas instâncias, sendo que o GRASP
usando path-relinking obtem as melhores soluções. Comparando estas soluções com as
do GLPK e o GAP dado por este software, podemos concluir que em geral as respostas
do GRASP são ótimas ou quase ótimas.
CAPÍTULO 5
Conclusões
Esta dissertação mostra resultados, teóricos e empíricos, gerados para três problemas de relativo interesse da comunidade de pesquisadores da área de otimização
combinatória. Vários dos resultados aqui mostrados são originais.
Para o problema de corte uni-dimensional de objetos com retalhos mostramos
dois novos modelos matemáticos, sendo que um deles superou, em todos os testes feitos,
os modelos existentes na literatura. Também projetamos uma heurística construtiva, um
algoritmo baseado no GRASP e uma matehaurística baseada em algoritmos evolutivos.
Os algoritmos propostos foram implementados e ainda melhorados usando processos em
paralelo com GPUs. Em todas as instâncias testadas, nossas propostas obtiveram soluções
de alta qualidade, principalmente a metaheurística baseada em algoritmos evolutivos.
Valendo ressaltar que os nossos algoritmos foram rápidos.
Para o problema dos companheiros estáveis, uma variante NP-difícil da classe
de problemas de emparelhamento estável, mostramos uma modelagem quadrática e outra
em programação linear inteira. Também projetamos uma Busca Tabu e versões de um
Branch-and-Bound, sendo seus desempenhos melhorados usando processos em paralelo
com GPUs. É importante destacar que os experimentos computacionais geraram bons
resultados para todas as instâncias testadas.
Para o problema da mochila compartimentada discutimos diferentes modelagens.
Tal como os outros dois primeiros problemas discutidos nesta dissertação, o problema
da mochila compartimentada é de difícil solução e tem numerosas aplicações. Para este
problema propomos uma nova heurística gulosa para solucioná-lo baseada em soluções
do problema clássico da mochila, e uma metaheurística baseada no GRASP que ao invés
de busca local usa path-relinking. Foram bons os resultados obtidos nos experimentos
computacionais, sendo particularmente muito boas as soluções obtidas pelo GRASP com
path-relinking.
Referências Bibliográficas
[1] A BUABARA , A.; M ORABITO, R. Cutting optimization of structural tubes to build
agricultural light aircrafts. Annals of Operation Research, 169:149–165, 2008.
[2] A RKIN , E. M.; B AE , S. W.; E FRAT, A.; O KAMOTO, K.; M ITCHELL , J. S.; P OLISHCHUK ,
V. Geometric stable roommates. Information Processing Letters, 109:219–222,
2009.
[3] B EASLEY, J. E. Heuristic Algorithms for the Unconstrained Binary Quadratic
Programming Problem. 1998.
[4] B ENNELL , J.; D OWSLAND, K. A tabu threasolding implementation for the irregular stock cutting problem. International Journal of Production Research, 37:4259–
4275, 1999.
[5] C HERRI , A.; A RENALES , M.; YANASSE , H. The one-dimensional cutting stock
problem with usable leftover - A heuirstic approach.
European Journal of
Operational Research, 196:897–908, 2009.
[6] C UI , Y.; YANG , Y. A Heuristic for the one-dimensional cutting stock problem
with usable leftover. European journal of operation research, 204:245–250, 2010.
[7] D IXIT, N.; K ERIVEN , R.; PARAGIOS , N.
GPU-Cuts: Combinatorial optimisa-
tion, graphic processing units and adaptative object extraction.
Centre
d’Enseignement et de Recherche en Technologies de l’Information et Systèmes,
2005.
[8] F EO, T. A.; R ESENDE , M. G. Greedy Randomized Adaptive Search Procedures.
Journal of Global Optimization, p. 109–133, 1995.
[9] F LEINER , T.; I RVING , R. W.; M ANLOVE , D. F. Efficient algorithms for generalized Stable Marriage and Roommates problems. Theoretical Computer Science,
381:162–176, 2007.
[10] G OLDBERG , D. E. Genetic Algorithms in Search, Optimization and Machine
Learning. Addison-Wesley, Berkeley, 1989.
Referências Bibliográficas
85
[11] G RADISAR , M.; J ESENCO, J.; R ESINOVIC, G.
Optimization of roll cutting in
clothing industry. Computers and Operational Research, 10:945–953, 1997.
[12] G RADISAR , M.; K LJAJIC, M.; R ESINOVIC, G.; J ESENCO, J. A sequential heuristic procedure for one-dimensional cutting. European Journal of Operational Research, 114:557–568, 1999.
[13] G RADISAR , M.; T RKMAN , P. A combined approach to the solution to the general
one-dimensional cutting stock problem. Computers and Operational Research,
32:1793–1807, 2005.
[14] H OTO, R.
O problema da mochila compartimentada aplicado no corte de
bobinas de aço. Tese de Doutorado, COPPE/UFRJ, 2001.
[15] H OTO, R.; A RENALES , M. N.; M ACULAN , N. O PROBLEMA DA MOCHILA COMPARTIMENTADA. Relatório Técnico, Universidade Estadual de Londrina, 1999.
[16] H OTO, R.; F ENATO, A.; YANNASSE , H.; M ACULAN , N. UMA NOVA ABORDAGEM
PARA O PROBLEMA DA MOCHILA COMPARTIMENTADA. XXXVIII SIMPÓSIO
BRASILEIRO DE PESQUISA OPERACIONAL, 2006.
[17] H OTO, R.; M ARQUES , F.; A RENALES , M. Uma proposta para resolver Mochilas
Compartimentadas Restritas por meio de Geração de Colunas. VII ON PCE –
Oficina Nacional de problemas de Corte e Empacotamento, 2003.
[18] I NARRA , E.; L ARREA , C.; M OLIS , E. The Stability of the Roommate Problem
Revisited. 2007.
[19] I RVING , R. W. An Efficient Algorithm for the Stable Roommates Problem. Journal
of Algorithms, 6:577–595, 1985.
[20] I RVING , R. W. The cycle roommates problem: a hard case of kidney exchange.
Information Processing Letters, 103:1–4, 2007.
[21] I RVING , R. W.; M ANLOVE , D. F.
The Stable Roommates Problem with Ties.
Journal of Algorithms, 43:85–105, 2002.
[22] I RVING , R. W.; S COTT, S. The stable fixtures problem - A many-to-many extension of stable roommates. Discrete Applied Mathematics, 155:2118–2129, 2007.
[23] I WAMA , K.; M IYAZAKI , S.
A Survey of the Stable Marriage Problem and Its
Variants. Proceedings of the International Conference on Informatics Education and
Research for Knowledge-Circulating Society, p. 131–136, 2008.
Referências Bibliográficas
86
[24] J ANIAK , A.; J ANIAK , W.; L ICHTENSTEIN , M. Tabu search on GPU. Journal of
Universal Computer Science, 14:2416–2427, 2008.
[25] K AZUO IWAMA, S. M.; OKAMOTO, K. Stable Roommates Problem with Triple
Rooms. 10th Korea–Japan Joint Workshop on Algorithms and Computation, p. 105–
112, 2007.
[26] KOCHENBERGER , G. A.; G LOVER , F.; A LIDAEE , B AHRAM ; R EGO, C. A Unified
Modeling and Solution Framework For Combinatorial Optimization Problems.
OR Spectrum, 26:237–250, 2002.
[27] L EÃO, A. A. D. S. Geração de Colunas para Problemas de Corte em Duas Fases.
Dissetação de Mestrado, ICMC/USP, 2009.
[28] M ARQUES , F. P.
O Problema da Mochila Compartimentada.
Dissetação de
Mestrado, ICMC/USP, 2000.
[29] M ARQUES , F. P. O Problema da Mochila Compartimentada e Aplicações. Dissetação de Doutorado, ICMC/USP, 2004.
[30] M ARQUES , F. P.; A RENALES , M. N. O Problema da mochila compartimentada e
aplicações. Pesquisa Operacional, 22, 2002.
[31] M ARQUES , F. P.; A RENALES , M. N. The compartmentalised knapsack problem.
Computers and Operations Research, 34:2109–2129, 2007.
[32] S ETHURAMAN , J.; T EO, C. A Polynomial-time Algorithm for the Bistable Roommates Problem. Journal of Computer and System Sciences, 63:486–497, 2001.
[33] V ELASCO, A.; DE PAULA , G.; V IEIRA , E. Um algoritmo baseado na GRASP para
o problema de corte bidimensional guilhotinado e restrito. Gestão da Produção,
Operações e Sistemas, 3:129–141, 2009.
[34] W EEMS , B. Bistable versions of the marriage and roommates problems. Journal
of Computer and System Sciences, 59:504–520, 1999.
[35] YANASSE , H.; H OTO, R.; S POLADOR , F.; A RENALES , M. Um modelo linear para
o problema da mochila compartimentada. IX ON PCE – Oficina Nacional de
problemas de Corte e Empacotamento, 2005.
APÊNDICE A
Funções para Trabalhar com Vetores Inteiros
na Memória das GPUs
Código
A.1
Funções para Trabalhar com Vetores
Inteiros na Memória das GPUs
1
#include <cutil_inline.h>
2
3
4
5
6
7
//Function that shows how to separate memory in the GPUs memory space
void Separate_GPU_Integer_Array(int** gpu_pointer, int size)
{
cutilSafeCall(cudaMalloc(gpu_pointer, size * sizeof(int)));
}
8
9
10
11
12
13
14
//Function that shows how to release the memory used in the GPUs memory
//space
void Release_GPU_Integer_Array(int* gpu_pointer)
{
cutilSafeCall(cudaFree(gpu_pointer));
}
15
16
17
18
19
20
21
22
23
//Functions that shows how to copy data from GPUs memory space to CPUs
//memory space
void Copy_Integer_Array_From_GPU_to_CPU(int* gpu_pointer
, int* cpu_pointer, int size)
{
cutilSafeCall(cudaMemcpy(cpu_pointer, gpu_pointer
, size * sizeof(int), cudaMemcpyDeviceToHost));
}
24
25
26
27
28
29
30
31
32
//Functions that shows how to copy data from CPUs memory space to GPUs
//memory space
void Copy_Integer_Array_From_CPU_to_GPU(int* cpu_pointer
, int* gpu_pointer, int size)
{
cutilSafeCall(cudaMemcpy(cpu_pointer, gpu_pointer
, size * sizeof(int), cudaMemcpyHostToDevice));
}
APÊNDICE B
Código dos Kernels Correspondêntes às
Implementações Parallelas das Heurísticas
Código B.1 Kernels da Heurística Construtiva para
o Problema de Corte com Retalhos
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
//Kernel for similar process to FFD, it is applied in parallel for each
//type of object
/*Parameters of the function:
object_size: array with the information of the sizes of the objects
object_number: array with the information of number of objects in stock
object_count: number of types of objects
piece_size: array with information of sizes of the items
piece_demand: array with information of the items demand
piece_count: number of type of items
patterns_pk: array with the result patterns created by the process*/
__global__ void Similar_FFD(int* object_size, int* object_number
, int object_count, int* piece_size
, int* piece_demand, int piece_count
, int* patterns_pk)
{
int i, count;
//gets type of the current object
int object_type = threadIdx.x;
//gets possition in vector of patterns, for current object
int pos = object_type * (piece_Count + 1);
//verify if the object type is valid and if there are objects
//of that type in stock
if(object_type >= 0 && object_type < object_count
&& object_number[object_type] > 0)
{
patterns_pk[pos + piece_count] = object_size[object_type];
for(i = 0; i < piece_count; i++)
{
count = patterns_pk[pos + piece_count]/ piece_size[i];
if(count > piece_demand[i])
count = piece_demand[i];
patterns_pk[pos + i] = count;
patterns_pk[pos + piece_count] -= count * piece_size[i];
}
}
36
37
}
Apêndice B
89
Código B.2 Kernels do Algoritmo Baseado em GRASP
para o Problema de Corte com Retalhos
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
//Kernel for process that calculates de data to solve the Knapsack problem
//via dynamic programming, it is applied for each type of item and executes
//a thread for each value between zero and the size of the item
/*
Parameters of the function:
table_items_type: in each position i has the type of item that reach the
value i in a linear combination
table_items_number: in each position i has the number of items of type
table_items_type[i] used to reach the value i in a linear combination
table_size: maximum size of the tables (capacity of the knapsack)
item_size: size of the current type of item
item_demand: demand of the current type of item
item_type: current type of item
*/
__global__ void Dynamic_Knapsack_Preparation(int* table_items_type
, int* table_items_number, int table_size
, int item_size, int item_demand, int item_type)
{
int i;
//gets value between 0 and the size of the current item
int position = threadIdx.x;
//if the demand of the item is zero, it is not used
if(item_demand > 0)
{
for(i = position; i < table_size - item_size; i += item_size)
if(table_items_type[i + item_size] < 0
&& table_items_type[i] >= 0
&& (table_items_type[i] != item_type
|| table_items_number[i] < item_demand))
{
table_items_type[i + item_size] = item_type;
table_items_number[i + item_size] = 1;
if(table_items_type[i] == item_type)
table_items_number[i + item_size]
+= table_items_number[i];
}
}
}
Apêndice B
90
Código B.3 Kernels do Algoritmo Baseado em GRASP
para o Problema de Corte com Retalhos
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
//Kernel for process that calculates in parallel for each object the
//solution of the Knapsack problem via dynamic programming
/*
Parameters of the function:
leftovers: array which has at each position i the leftover associtaed
to the solution of the Knapsack problem of object i
table_items_type: in each position i has the type of item that reach
the value i in a linear combination
object_size: array with object sizes
object_number: array with the number of object of each type in stock
object_count: number of type of objects
upper_value: value large enough
*/
__global__ void Dynamic_Knapsack_Solution(int* leftovers, int* table_items_type
, int* object_size, int* object_number
, int object_count, int upper_value
, int object_type)
{
int i;
//gets type of the current object
int object_type = threadIdx.x;
//the value of obect_type must be valid and there must be objects
//of that type in stock
if(object_type >= 0 && object_type < object_count
&& object_number[object_type] > 0)
{
i = object_size[object_type];
while(i > 0 && table_items_type[i] < 0)
i--;
leftovers[object_type] = object_size[object_type] - i;
if(i == 0)
leftovers[object_type] = upper_value;
}
}
Apêndice B
91
Código
B.4
Kernel do Algoritmo Baseado em
Processos Evolutivos para o Problema de Corte
com Retalhos
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
//Kernel for process that calculates in parallel for each type of object
//the rank value of the solution of the Knapsack problem calculated via
//dynamic programming
/*
Parameters of the function:
rank: array of rank values
table_items_type: in each position i has the type of item that reach the
value i in a linear combination
table_items_number: in each position i has the number of items of type
table_items_type[i] used to reach the value i in a linear combination
object_size: array with object sizes
object_number: array with the number of object of each type in stock
piece_size: array of sizes of type of items
object_count: number of type of objects
less_standard: minimum size of a standard object
fraction: used to determine if the item is a small item or a large item
*/
__global__ void Dynamic_Knapsack_Ranking(int* rank, int* table_items_type
, int* table_items_number, int* object_size
, int* object_number, int* piece_size, int object_count
, int less_standard, float fraction)
{
int i;
//gets type of the current object
int object_type = threadIdx.x;
//the value of obect_type must be valid and there must be objects
//of that type in stock
if(object_type >= 0 && object_type < object_count
&& object_number[object_type] > 0)
{
rank[object_type] = 0;
i = object_size[object_type];
while(i > 0 && table_items_type[i] < 0)
i--;
while(i > 0)
{
if(piece_size[table_items_type[i]]
>= (fraction * less_standard))
rank[object_type] += table_items_number[i];
i -= piece_size[table_items_type[i]] * table_items_number[i];
}
}
}
APÊNDICE C
Código para Executar os Kernels
Código C.1 Código para Executar os Kernels
1
#include <cutil_inline.h>
2
3
4
5
//Notice that for calling the kernels the arrays of memory must be in
//the GPUs memory space, and the results, if necessary are copied to the
//CPUs memomry space
6
7
//Calling kernels of Constructive Heuristic for Cut Problem
8
9
10
11
12
13
14
15
16
void Call_Similar_FFD(int* object_size, int* object_number, int object_count
, int* piece_size, int* piece_demand, int piece_count
, int* patterns_pk)
{
Similar_FFD<<<0, object_count>>>(object_size, object_number
, object_count, piece_size, piece_demand, piece_count
, patterns_pk);
}
17
18
19
20
21
22
23
24
25
26
27
28
29
30
void Call_Improve_FFD(int* object_size, int* object_number, int object_count
, int* piece_size, int* piece_demand, int piece_count
, int* patterns_pk, int* patterns_pk_bar
, int* patterns_pk_hat, int delta, float beta
, float ganma, int less_standard)
{
Improve_FFD<<<0, object_count>>>(object_size, object_number
, object_count, piece_size, piece_demand, piece_count
, patterns_pk, patterns_pk_bar, patterns_pk_hat, delta
, beta, ganma, less_standard);
}
Apêndice C
93
Código C.2 Código para Executar os Kernels
1
#include <cutil_inline.h>
2
3
4
5
//Notice that for calling the kernels the arrays of memory must be in
//the GPUs memory space, and the results, if necessary are copied to the
//CPUs memomry space
6
7
//Calling kernels of GRASP Based Algorithm for Cut Problem
8
9
10
11
12
13
14
15
16
17
//This process must be called for each type of item
void Call_Dynamic_Knapsack_Preparation(int* table_items_type
, int* table_items_number, int table_size, int item_size
, int item_demand, int item_type)
{
Dynamic_Knapsack_Preparation<<<0, item_size>>>(table_items_type
, table_items_number, table_size, item_size
, item_demand, item_type);
}
18
19
20
21
22
23
24
25
26
27
28
//This process is called for each type of item after call the dynamic
//preparation process
void Call_Dynamic_Knapsack_Solution(int* leftovers, int* table_items_type
, int* object_size, int* object_number, int object_count
, int upper_value, int object_type)
{
Dynamic_Knapsack_Solution<<<0, object_count>>>(leftovers
, table_items_type, object_size, object_number, object_count
, upper_value, object_type);
}
29
30
//Calling kernel of Evolutive Based Algorithm for Cut Problem
31
32
33
34
35
36
37
38
39
40
41
42
43
//This process is called after the Dynamic_Knapsack_Preparation process
//for each type of item
void Call_Dynamic_Knapsack_Ranking(int* rank, int* table_items_type
, int* table_items_number, int* object_size
, int* object_number, int* piece_size, int object_count
, int less_standard, float fraction)
{
Dynamic_Knapsack_Ranking<<<0, object_count>>>(rank, table_items_type
, table_items_number, object_size, object_number, piece_size
, object_count, less_standard, fraction);
}
Apêndice C
94
Código C.3 Código para Executar os Kernels
1
#include <cutil_inline.h>
2
3
4
5
//Notice that for calling the kernels the arrays of memory must be in
//the GPUs memory space, and the results, if necessary are copied to the
//CPUs memomry space
6
7
8
//Calling kernells of Tabu Search for Stable Roommates Problem
9
10
11
12
13
14
15
void Call_Objective_Value(int* neighbors_value, int* x, int n, int* m
, int current_value, int* tabu_list, int local)
{
Objective_Value<<<0, n * n>>>(neighbors_value, x, n, m
, current_value, tabu_list, local);
}
16
17
18
19
20
21
22
23
//This process is called after the process Objective_Value
void Call_Best_Neighbors(int* neighbors, int* values, int* objective_values
, int n, int* tabu_list, int local)
{
Best_Neighbors<<<0, n>>>(neighbors, values, objective_values, n
, tabu_list, local);
}
24
25
26
27
28
void Call_Update_Tabu_List(int* tabu_list, int p1, int p2, int val, int n)
{
Update_Tabu_List<<<0, n * n>>>(tabu_list, p1, p2, val, n);
}