DIETHA – Design, Implementation and Exploitation of Advanced Heuristic Techniques

Principal investigator: Abraham Duarte Funding entities: Ministerio de Economía y Competitividad (TIN2012-35632-C02-02). Duration: 01/01/2013 – 31/12/2015,

Abstract:

There are a large amount of problems that are framed within the context of combinatorial optimization characterized by the high interest associated with their practical resolution. This project deals with five distinct families of combinatorial problems. These are:

Ordering problems: with applications in VLSI design or in the efficient resolution of systems of equations. Location problems: with interest in telecommunication applications such as distribution of signal regenerators or network design. Graph-based problems: with applications in the distribution of electronic devices in electronic boards or in image segmentation. Routing problems: by focusing on multi-objective problems with applications in the transport of hazardous materials or in recommendation systems. Selection problems: with applications in the construction of diverse groups or clustering of documents. The methodology to solve the problems described above are metaheuristics procedures, among which we can highlight evolutionary algorithms, tabu search, variable neighborhood search or GRASP, to name some of the best known. For each combinatorial problem, we will propose the most suitable metaheuristic according to their mathematical structure or model. We will mainly focus on design of novel strategies to obtain high quality solutions. Besides, it is expected to figure out general strategies that can be easily applied to other related problems. We will also focus on the efficient and flexible implementation of those strategies, taking advantage of new language programming features and multi-core microprocessors. Finally we will focus on exploitation through a management platform, which integrates the problems addressed above. Simultaneously, we will develop an application to put into production (in the companies interested in our research project) the algorithms developed during the project.

In addition to solve the problems presented above, a second objective of the project is to develop the metaheuristic methodologies themselves. To successfully meet this challenge the research team has researcher Nenad Mladenovic, which developed in conjunction with Pierre Hansen the variable neighborhood search methodology.

All these problems will be integrated into Optsicom, a software tool that allow the execution of algorithms devoted to solve optimization problems and analyze the associated results. Optsicom can be used at two levels: as an end-user or as a researcher on heuristic methods. In this line, the problems integrated in Optsicom will also be available via the Web at Optsicom Repository, a web platform for comprehensive management of optimization problems. This platform will post all the information associated with an optimization problem. For each problem, it is expected to store the description, algorithms, instances, experimental results and relevant references. Furthermore, the results obtained by executing the algorithms can be compared using different statistical tests that are available as part of the software tool.