lorena@lac.inpe.br

http://www.lac.inpe.br/~lorena

• Período: 18-12-2001 a 18-12-2003

Os resultados obtidos com a pesquisa foram:

1. Estudou-se o uso da relaxação Lagrangean/surrogate (lagsur) no processo de geração de colunas, visando estabilizar e acelerar o método tradicional de geração de colunas. Um trabalho inicial foi produzido, aplicando o processo ao problema de p-medianas (trabalho conjunto de Luiz A. N. Lorena e Edson L. F. Senne). A aplicação ao problema de p-medianas capacitado foi apresentada em congresso internacional específico da área de localização, o IX ISOLDE, realizado no Canadá em junho/2002. A estabilização lagsur foi ainda testada com sucesso para o problema de p-medians não capacitado, sendo integrada pela primeira vez a um método exato tipo branch-and-price. Um trabalho em congresso internacional foi apresentado no EURO/INFORMS - Istambul (julho/2003). Um artigo foi publicado na revista Computers and Operations Research e outro foi aceito para publicação na mesma revista.
2. O bolsista Marcos A. Pereira (orientação conjunta de Luiz A. N. Lorena e Édson L. F. Senne) está aplicando o método de estabilização lagsur para resolver problemas de máxima cobertura por geração de colunas. Os resultados da aplicação da estabilização lagsur com o método subgradientes saíram publicados em revista internacional em 2002. A aluna de doutorado Silvely N. Salomão (orientação conjunta de Luiz A. N. Lorena e Édson Luiz F. Senne) iniciou a implementação da estabilização lagsur para o Problema Generalizado de Atribuição (PGA). Os dois alunos desenvolverão algoritmos branch-and-price estabilizados pela relaxação lagsur. Um artigo conjunto divulgando e colocando de forma geral a estabilização lagsur, foi publicado em 2003 na revista Pesquisa Operacional (edição especial de aniversário do Prof. Nelson Maculan). Outros problemas relacionados, como os que envolvem a programação de horários para empregados (crews), estão sendo pesquisados por outros alunos (mestrado e doutorado).
3. O trabalho "School Location Methodology in Urban Areas of Developing Countries" realizado em conjunto com Nélio Pizzolato (PUC – Rio de Janeiro) e Fabrício Barcelos foi premiado com a terceira colocação no concurso OR for Development Prize Competition realizado durante o congresso IFORS2002 - The sixteenth triennial conference of the International Federation of Operational Research Societies, em julho 2002. Uma publicação internacional e uma ncional devem sair como resultados de divulgação.
4. Foi publicado no European Journal of Operational Research (autores Luiz A. N. Lorena e Marcelo G. Narciso) o trabalho desenvolvido na tese de doutorado de Marcelo G. Narciso: "Uma aplicação da relaxação Lagrangeana/surrogate ao problema simétrico do Caixeiro Viajante". Neste trabalho o método usual de subgradientes é melhorado usando as informações locais da relaxação surrogate. Na mesma linha foi publicada em revista internacional pesquisa sobre a estabilização lagsur combinada a algoritmos de busca local para problemas de p-medianas com capacidades (autores Luiz A. N. Lorena e Edson L. F. Senne).
5. A aluna Missae Yamamoto defendeu sua tese de doutorado (em setembro de 2003) em uma linha de pesquisa iniciada em sua dissertação de mestrado (orientação de Luiz A. N. Lorena). O problema estudado surge na confecção automática de mapas usando Sistemas de Informações Geográficas (SIGs), e é conhecido como rotulação de pontos. Basicamente o problema é o de escrever rótulos em pontos (nomes de cidades) de forma clara e evitando conflitos entre rótulos (não podem ocupar o mesmo espaço). O problema foi modelado e resolvido de forma aproximada como uma aplicação do Algoritmo Genético Construtivo (AGC). Também foi aplicado para problemas pequenos um algoritmo exato do tipo branch and bound. Os resultados de sua dissertação de mestrado foram publicados em 2003 em revista de circulação internacional, e os novos resultados da tese de doutorado foram apresentados em congresso internacional (MIC´2003) e nacional, e submetidos para publicação em revista internacional.
6. Os resultados da aplicação do AGC a problemas de localização foram melhorados com a introdução do algoritmo de localização-alocação alternada como heurística de mutação no processo evolutivo. O problema das p-medianas foi focalizado em trabalhos conjuntos de L. A. N. Lorena, M. G. Narciso para aplicações em agricultura. O aluno Reinaldo G. Arakaki (orientação de Luiz A. N. Lorena) defendeu sua tese de doutorado (em abril de 2002) onde foram abordados os problemas de p-medianas capacitado e de máxima cobertura como aplicações do AGC. Trabalhos foram apresentados em congressos internacional e nacional.
7. Um trabalho foi desenvolvido com o aluno de doutorado Alexandre César M. Oliveira (orientação de Luiz A. N. Lorena), aplicando o AGC ao problema de Gate Matrix Layout (para VLSI), onde os melhores resultados foram reproduzidos com maior freqüência que os obtidos por outras abordagens heurísticas, e com tempos computacionais competitivos. O trabalho foi publicado em revista de circulação internacional. Recentemente um problema relacionado (o problema MOSP que visa a minimização do número máximo de pilhas abertas no processo de cortes de padrões em estoque) foi analisado usando o AGC com resultados muito bons. O AGC realizou um treinamento populacional com a heurística 2-opt, a mesma usada para o problema de VLSI. Um trabalho apresentado no congresso SBIA foi publicado na série Lecture Notes in Artificial Intelligence. Um trabalho em congresso internacional foi apresentado no EURO/INFORMS - Istambul (julho/2003).

International Journal of Industrial Engineering 9(1), 57-67, 2002

European Journal of Operational Research, 138 (3): 473-483, 2002.

Tabu search heuristic for point-feature cartographic label placement.

GeoInformatica - An International Journal on Advances of Computer Science for Geographic Information Systems, 6 (1): 77-90, 2002.

Oliveira A. C. M. and Lorena, L. A. N.
A Constructive Genetic Algorithm for Gate Matrix Layout Problems.
IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems. Vol. 21, no. 8, pp 969-974, 2002

Oliveira A. C. M. and Lorena, L. A. N.
2-opt population training for minimization of open stack problem
In: Advances in Artificial Intelligence, G. Bittencourt and G. L. Ramalho (eds.), Springer Lecture Notes in Artificial Intelligence Series – Vol. 2507 , pp. 313-323, 2002

Narciso, M. G. ; Lorena, L.A.N.
Uso de algoritmos genéticos em sistemas de apoio a decisão para alocação de recursos no campo e na cidade
Revista Brasileira de AgroInformatica, vol. 4 , n. 2, p. 90-101, 2002

Lorena, L. A. N.; Pereira. M. A. e S. N. A. Salomão
A relaxação Lagrangeana/surrogate e o método de geração de colunas: novos limitantes e novas colunas
Pesquisa Operacional 23 (1): 29-47 - 2003

Edição Especial - 60 anos Prof. Nelson Maculan

Lorena, L.A.N.
Analise espacial de redes com aplicações em sistemas de informações geográficas
Revista Produção (on-line) – 2003

Senne. E.L.F. and Lorena, L.A.N.
Abordagens Complementares para problemas de p-medianas
Revista Produção 13(3) - 2003

Lorena, L. A. N. and Senne, E. L. F.
Local search heuristics for capacitated p-median problems
Networks and Spatial Economics 3: 407-419, 2003

Lorena, L.A.N. and Senne, E. L. F.
A Column Generation Approach to Capacitated p-median Problems
Computers & Operations Research 31: 863-876, 2004

A constructive genetic algorithm for the generalized assignment problem.

Evolutionary Optimization.

Senne. E.L.F. ; Lorena, L.A.N. and Pereira, M. A.
A branch-and-price approach to p-median location problems
Computers & Operations Research - 2003

School Location Methodology in Urban Areas of Developing Countries

International Transactions in Operational Research – 2002.

Barcelos, F. B.; Pizzolato, N. D. and Lorena, L. A. N.
Localização de escolas do ensino fundamental com modelos capacitado e não-capacitado: caso de Vitoria/ES
Pesquisa Operacional - 2003

Edição Especial - 60 anos Prof. Roberto Galvão

Oliveira A. C. M. and Lorena, L. A. N.
Sequencing cutting patterns and VLSI gates by population training algorithms
INFORMS journal on Computing -2003

Yamamoto, M. and Lorena, L. A. N.
A Constructive Genetic Approach to Point-Feature Cartographic Label Placement
book "Progress as Real Problem Solvers - Kluwer - 2003

Lagrangean/surrogate relaxation and column generation: new bounds and new columns

CO2002 - International Symposium on Combinatorial Optimization, Paris, April, 2002.

A column generation approach to capacitated p-median problems

ISOLDE – 9th International Symposium on Locational Decisions, Fredericton, New Brunswick, Canada, June, 2002.

Anais do III Congresso da SBI-Agro. Sociedade Brasileira de Informática Aplicada à Agropecuária e Agroindústria, 2002. p.172 – 176.

School Location Methodology in Urban Areas of Developing Countries

IFORS2002 - The sixteenth triennial conference of the International Federation of Operational Research Societies, hosted by the UK Operational Research Society, july, 2002.

Trabalho finalista: OR for Development Prize Competition (3^º colocado).

Oliveira A. C. M. and Lorena, L. A. N.

SBIA'02 - XVI Brazilian Symposium on Artificial Intelligence - Porto de Galinhas/Recife - 11 a 14 de novembro de 2002

II Workshop dos Cursos de Computação Aplicada do INPE (II Worcap). São José dos Campos SP. 20 e 21 de Novembro de 2002.

Lorena, L.A.N. and Senne. E.L.F.
Abordagens de Geração de Colunas para um Problema de p-medianas  Capacitado
XXXIV SBPO - Rio de Janeiro - 2002 

Barcelos, F. B. , Pizzolato, N. D. and Lorena, L. A. N.
Avaliação da localização de escolas com modelos capacitado e não-capacitado e uso de uma ferramenta GIS: estudo de caso de Vitória/ES
XXXIV SBPO - Rio de Janeiro - 2002 

Oliveira A. C. M.  and Lorena, L. A. N.
Algoritmo de treinamento populacional: uma aplicação ao MOSP
VI Oficina de Problemas de Cortes e Empacotamento - UNICAMP - 9-10 dez. 2002

Senne. E.L.F. and Lorena, L.A.N.
A branch-and-price approach to p-median location problems
EURO/INFORMS - Istambul - 2003

Lorena, L. A. N. and Oliveira A. C. M.
A population Training Approach to Permutation Problems
EURO/INFORMS - Istambul - 2003

Yamamoto, M. and Lorena, L. A. N.
A Constructive Genetic Approach to Point-Feature Cartographic Label Placement
MIC2003 - The Fifth Metaheuristics International Conference - Kyoto, Japan, August 25-28, 2003

Narciso, M. G. and Lorena, L. A. N.
Modelos de localização na seleção de reservas para conservação de espécies
IV Congresso da SBI-Agro - Porto Seguro, 17-19 setembro 2003

Yamamoto, M. and Lorena, L. A. N.
A Constructive Genetic Approach to Point-Feature Map Labeling
XXXV - SBPO - Natal - 04 a 07/11/2003

Senne. E.L.F. ; Lorena, L.A.N. and Pereira, M. A.
Um algoritmo Branch-and-Price para problemas de localizacao de p-medianas
XXXV - SBPO - Natal - 04 a 07/11/2003

Oliveira A. C. M. ; Lorena, L. A. N. ; Stephani, S. and Preto, A. J.
An Hierarchical Fair Competition Genetic Algorithm for Numerical Optimization
III WORCAP - INPE - São José dos Campos - 2003

Figueiredo, A. P. S.; Lorena, L. A. N. and Carvalho, S. V.
Modelos de localização de ambulâncias
III WORCAP - INPE - São José dos Campos - 2003

LAPTEC2002 - Terceiro Congresso de Lógica Aplicada a Tecnologia - São Paulo - 11 a 13 de novembro de 2002

INFORMS Annual Meeting 2002 San Jose - November 17 -20, 2002

11^o. CLAIO - Latin-American Conference on Operations Research - Concepcion - Chile - October 27 - 30, 2002

Narciso, M. G. ; Lorena, L.A.N.
Uma abordagem de geração de colunas para o problema do caixeiro viajante
XXV CNMAC - Congresso Nacional de Matemática Aplicada e Computacional - Nova Friburgo, 16 a 19 de setembro de 2002 

Doutorado em Computação Aplicada no INPE

Orientador: Luiz Antonio Nogueira Lorena

Data da defesa: abril de 2002.

Novos algoritmos para o problema de rotulação cartográfica de pontos
Doutorado em Computação Aplicada no INPE

Orientador: Luiz Antonio Nogueira Lorena

Data da defesa: setembro de 2003.

http://www.lac.inpe.br/~lorena/ArsigIndex.html

Dr. Luiz Antonio Nogueira Lorena

Pesquisador Titular - LAC/INPE

Dr. Luiz Antonio Nogueira Lorena

Dr. Horácio Hideki Yanasse

Dr. João Argemiro C. Paiva

Marcos A. Pereira – bolsista PCI – CNPq

Prof. Dr. Edson Luiz França Senne

Prof. Dr. Edgard Dias Batista Júnior

Prof. Dr. José Celso Freire Júnior

Dr. Marcelo Gonçalves Narciso

Bolsa Pesquisa – CNPq proc. 300837/89-5

Auxílio Pesquisa – CNPq proc. 470858/03-6

Otimização Combinatória - 3° período 2002

Otimização Combinatória - 3° período 2003

Marcelo Seido Nagano

Reinaldo G. I. Arakaki

Missae Yamamoto

Alexandre César Muniz de Oliveira

FAPESP: Assessor para pedidos de bolsas e auxílios.

CNPq: Assessor para pedidos de bolsas, cooperação internacional e auxílios.

CAPES: Assessor para pedido de auxílio.

Revistas internacionais: European Journal of Operational Research, Networks, International Journal of Industrial Engineering, Journal of Combinatorial Optimization, Annals of Operations Research

Revistas nacionais: Produção (Membro do Conselho Científico), Pesquisa Operacional, Boletim SBMAC

Editor Associado das Revistas Produção, Produção on-line e Pesquisa Operacional.