Evolutionary algorithms for some problems in telecommunications

• Grant number: 10/05233-5
• Support Opportunities: Scholarships in Brazil - Doctorate
• Start date: July 01, 2010
• End date: February 28, 2015
• Field of knowledge: Physical Sciences and Mathematics - Computer Science - Theory of Computation
• Principal Investigator: Flávio Keidi Miyazawa
• Grantee: Carlos Eduardo de Andrade
• Host Institution: Instituto de Computação (IC). Universidade Estadual de Campinas (UNICAMP). Campinas , SP, Brazil
• Associated scholarship(s): 12/08222-0 - Algorithms for Winner determination and Precification problems in combinatorial Auctions, BE.EP.DR

Abstract

In last twenty years, telecommunication networks have experienced a huge increase in data utilization. From massive on-demand video to uncountable mobile devices exchanging text and video, traffic reached scales that overcame the network capacities. Therefore, telecommunication companies around the world have been forced to increase their capacity to serve this increasing demand. As the cost to deploy network infrastructure is usually very large, the design of a network heavily uses optimization tools to keep costs as low as possible. In this thesis, we analyze several aspects of the design and deployment of communication networks.First, we present a new network design problem used to serve wireless demands from mobile devices and route the traffic to the core network. Such access networks are based on modern wireless access technologies such as Wi-Fi, LTE, and HSPA. This problem has several real world constraints and it is hard to solve. We study real cases of the vicinity of a large city in the United States.Following, we present a variation of the hub-location problem used to model these core networks. Such problem is also suitable to model transportation networks.We also study the overlapping correlation clustering problem used to model the user's behavior when using their mobile devices. In such problem, one can label an object with multiple labels and analyzes the connections between them. Although this problem is very generic, it is suitable to analyze device mobility which can be used to estimate traffic in geographical regions.Finally, we analyze spectrum licensing from a governmental perspective. In these cases, a governmental agency wants to sell rights for telecommunication companies to operate over a given spectrum range. This process usually is conducted using combinatorial auctions. For all problems we propose biased random-key genetic algorithms and mixed integer linear programming models (except in the case of the overlapping correlation clustering problem due its non-linear nature). Our algorithms were able to overcome the state of the art algorithms for all problems. (AU)

Scientific publications

(References retrieved automatically from Web of Science and SciELO through information on FAPESP grants and their corresponding numbers as mentioned in the publications by the authors)

DE ANDRADE, CARLOS EDUARDO; TOSO, RODRIGO FRANCO; RESENDE, MAURICIO G. C.; MIYAZAWA, FLAVIO KEIDI. Biased Random-Key Genetic Algorithms for theWinner Determination Problem in Combinatorial Auctions. EVOLUTIONARY COMPUTATION, v. 23, n. 2, p. 279-307, SUM 2015. (12/08222-0, 10/05233-5)

ANDRADE, CARLOS E.; RESENDE, MAURICIO G. C.; ZHANG, WEIYI; SINHA, RAKESH K.; REICHMANN, KENNETH C.; DOVERSPIKE, ROBERT D.; MIYAZAWA, FLAVIO K.. A biased random-key genetic algorithm for wireless backhaul network design. APPLIED SOFT COMPUTING, v. 33, p. 150-169, AUG 2015. (12/08222-0, 10/05233-5)

ANDRADE, CARLOS E.; MIYAZAWA, FLAVIO K.; RESENDE, MAURICIO G. C.; BLUM, C. Evolutionary Algorithm for the k-Interconnected Multi-Depot Multi-Traveling Salesmen Problem. GECCO'13: PROCEEDINGS OF THE 2013 GENETIC AND EVOLUTIONARY COMPUTATION CONFERENCE, v. N/A, p. 8-pg., 2013-01-01. (10/05233-5)

Academic Publications

(References retrieved automatically from State of São Paulo Research Institutions)

ANDRADE, Carlos Eduardo de. Algoritmos evolutivos para alguns problemas em telecomunicações. 2015. Doctoral Thesis - Universidade Estadual de Campinas (UNICAMP). Instituto de Computação Campinas, SP.