Dois problemas de otimização em grafos: Transporte em redes de dutos e Busca com custos de acesso
Resumo
Consideramos dois problemas de otimização combinatória bastante distintos: o problema de transporte em redes de dutos (PTD) e o problema de busca com custos de acesso (PBC). O PTD utiliza um novo modelo simplificado, baseado nas operações dos oleodutos da Petrobras. Também definimos diversas variações deste problema. Para a variação mais genérica, provamos que encontrar uma solução viável é NP-difícil. Para outra, mostramos que a minimização dos custos de transporte dutoviário, pode ser resolvida em tempo polinomial. Neste caso, também provamos que a minimização do makespan é difícil de aproximar. O PBC considera a busca por um elemento num vetor ordenado com custos de acesso variados. Apresentamos algoritmos lineares (2 + e + o(1)) -aproximados para minimizar o custo da pior busca ou o custo médio de uma busca. Também apresentamos um algoritmo O(log n) -aproximado para o custo médio que apresenta um desempenho muito bom para alguns casos práticos testados, onde é o tamanho da entrada.Referências
Ahuja, R., Magnanti, T., and Orlin, J. (1993). Network Flows: Theory, Algorithms and Applications, pages 357–401. Prentice Hall, New Jersey. Chapter 10: Minimum Cost Flows: Polynomial Algorithms.
Charikar, Fagin, Guruswami, Kleinberg, Raghavan, and Sahai (2002). Query strategies for priced information. JCSS: Journal of Computer and System Sciences, 64.
da Silva, A. C. (1999). Otimização do transporte em oleodutos utilizando algoritmos genéticos e programação linear. Master’s thesis, Departamento de Engenharia de Sistemas, UNICAMP.
Hane, C. A. and Ratliff, H. D. (1995). Sequencing inputs to multi-commodity pipelines. Annals of Operations Research, 57. Mathematics of Industrial Systems I.
Knight, W. J. (1988). Search in an ordered array having variable probe cost. SIAM Journal on Computing, 17(6):1203–1214.
Laber, E. S., Milidiú, R. L., and Pessoa, A. A. (2001). On binary searching with non-uniform costs. In Proceedings of SODA’2001, pages 855–864, Washington, DC, USA.
Laber, E. S., Milidiú, R. L., and Pessoa, A. A. (2002a). On binary searching with nonuniform costs. Siam Journal on Computing, 31(4):1022–1047.
Laber, E. S., Milidiú, R. L., and Pessoa, A. A. (2002b). A strategy for searching with different access costs. Theoretical Computer Science, 287:571–584. Issue 2.
Laber, E. S., Pessoa, A. A., and Milidiú, R. L. (1999). Strategies for searching with different access costs. In Nezestrill, J., editor, Seventh European Symposium on Algorithms, Lecture Notes in Computer Science, pages 236–247, Prague, Czech Republic. Springer.
Más, R. (2001). Técnicas de otimização no suprimento de petróleo em complexos de distribuição. Master’s thesis, Departamento de Engenharia Química, Universidade de São Paulo.
Milidiú, R. L., Liporace, F., and de Lucena, C. J. P. (2003). Pipesworld: Planning pipeline transportation of petroleum derivatives. In Workshop on the Competition, Trento, Italy.
Milidiú, R. L., Laber, E. S., Pessoa, A. A., and Rey, P. A. (1999). Petroleum products scheduling in pipelines. In The International Workshop on Harbour, Maritime & Industrial Logistics Modeling and Simulation.
Milidiú, R. L., Pessoa, A. A., Braconi, V., Laber, E. S., and Rey, P. A. (2001). Um algoritmo grasp para o problema de transporte de derivados de petróleo em oleodutos. In Anais do XXXIII SBPO, pages 237–246, Campos do Jordão, SP, Brazil.
Milidiú, R. L., Pessoa, A. A., and Laber, E. S. (2000). Transporting petroleum products in pipelines (abstract). In ISMP 2000 – 17th International Symposium on Mathematical Programming, pages 134–135, Atlanta, Georgia, USA.
Milidiú, R. L., Pessoa, A. A., and Laber, E. S. (2002). Pipeline transportation of petroleum products with no due dates. In Proceedings of the LATIN’2002, pages 248–262, Canún, Mexico.
Milidiú, R. L., Pessoa, A. A., and Laber, E. S. (2003). The complexity of makespan minimization for pipeline transportation. Theoretical Computer Science, 306(1-3):339–351. presented in the APPROX’2002, Rome, Italy.
Navarro, G., Barbosa, E., Baeza-Yates, R., Cunto, W., and Ziviani, N. (2000). Binary searching with non-uniform costs and its application to text retrieval. Algorithmica, 27(2):145–169.
Pinedo, M. (1994). Prentice Hall. Scheduling: Theory, Algorithms, and Systems.
Charikar, Fagin, Guruswami, Kleinberg, Raghavan, and Sahai (2002). Query strategies for priced information. JCSS: Journal of Computer and System Sciences, 64.
da Silva, A. C. (1999). Otimização do transporte em oleodutos utilizando algoritmos genéticos e programação linear. Master’s thesis, Departamento de Engenharia de Sistemas, UNICAMP.
Hane, C. A. and Ratliff, H. D. (1995). Sequencing inputs to multi-commodity pipelines. Annals of Operations Research, 57. Mathematics of Industrial Systems I.
Knight, W. J. (1988). Search in an ordered array having variable probe cost. SIAM Journal on Computing, 17(6):1203–1214.
Laber, E. S., Milidiú, R. L., and Pessoa, A. A. (2001). On binary searching with non-uniform costs. In Proceedings of SODA’2001, pages 855–864, Washington, DC, USA.
Laber, E. S., Milidiú, R. L., and Pessoa, A. A. (2002a). On binary searching with nonuniform costs. Siam Journal on Computing, 31(4):1022–1047.
Laber, E. S., Milidiú, R. L., and Pessoa, A. A. (2002b). A strategy for searching with different access costs. Theoretical Computer Science, 287:571–584. Issue 2.
Laber, E. S., Pessoa, A. A., and Milidiú, R. L. (1999). Strategies for searching with different access costs. In Nezestrill, J., editor, Seventh European Symposium on Algorithms, Lecture Notes in Computer Science, pages 236–247, Prague, Czech Republic. Springer.
Más, R. (2001). Técnicas de otimização no suprimento de petróleo em complexos de distribuição. Master’s thesis, Departamento de Engenharia Química, Universidade de São Paulo.
Milidiú, R. L., Liporace, F., and de Lucena, C. J. P. (2003). Pipesworld: Planning pipeline transportation of petroleum derivatives. In Workshop on the Competition, Trento, Italy.
Milidiú, R. L., Laber, E. S., Pessoa, A. A., and Rey, P. A. (1999). Petroleum products scheduling in pipelines. In The International Workshop on Harbour, Maritime & Industrial Logistics Modeling and Simulation.
Milidiú, R. L., Pessoa, A. A., Braconi, V., Laber, E. S., and Rey, P. A. (2001). Um algoritmo grasp para o problema de transporte de derivados de petróleo em oleodutos. In Anais do XXXIII SBPO, pages 237–246, Campos do Jordão, SP, Brazil.
Milidiú, R. L., Pessoa, A. A., and Laber, E. S. (2000). Transporting petroleum products in pipelines (abstract). In ISMP 2000 – 17th International Symposium on Mathematical Programming, pages 134–135, Atlanta, Georgia, USA.
Milidiú, R. L., Pessoa, A. A., and Laber, E. S. (2002). Pipeline transportation of petroleum products with no due dates. In Proceedings of the LATIN’2002, pages 248–262, Canún, Mexico.
Milidiú, R. L., Pessoa, A. A., and Laber, E. S. (2003). The complexity of makespan minimization for pipeline transportation. Theoretical Computer Science, 306(1-3):339–351. presented in the APPROX’2002, Rome, Italy.
Navarro, G., Barbosa, E., Baeza-Yates, R., Cunto, W., and Ziviani, N. (2000). Binary searching with non-uniform costs and its application to text retrieval. Algorithmica, 27(2):145–169.
Pinedo, M. (1994). Prentice Hall. Scheduling: Theory, Algorithms, and Systems.
Publicado
31/07/2004
Como Citar
PESSOA, Artur Alves; MILIDIÚ, Ruy Luiz; LABER, Eduardo Sany.
Dois problemas de otimização em grafos: Transporte em redes de dutos e Busca com custos de acesso. In: CONCURSO DE TESES E DISSERTAÇÕES (CTD), 17. , 2004, Salvador/BA.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2004
.
p. 9-16.
ISSN 2763-8820.
