Network optimization with several sources and one sink

• Grant number: 11/23288-4
• Support Opportunities: Scholarships in Brazil - Scientific Initiation
• Start date: March 01, 2012
• End date: February 28, 2013
• Field of knowledge: Physical Sciences and Mathematics - Mathematics - Applied Mathematics
• Principal Investigator: Francisco de Assis Magalhães Gomes Neto
• Grantee: José Henrique Costa Monteiro da Silva
• Host Institution: Instituto de Matemática, Estatística e Computação Científica (IMECC). Universidade Estadual de Campinas (UNICAMP). Campinas , SP, Brazil

Abstract

In this project, we will study how to obtain the minimal cost network that connects several sources to one sink, a problem related to the computation of the Euclidean Steiner minimum tree in the plane. We will pay special attention to the optimization of a network of pipes that transport sewage to a treatment site. We will study the mathematical aspects of the problem, as well as some methods for its solution. We will also code a heuristic algorithm for determining a near optimal network. Finally, we will perform some numerical tests, to check the efficiency of the algorithm for the solution of real and randomly generated problems. (AU)