EMIGO – Efficient Metaheuristics for Graph Optimization

Principal investigator: Abraham Duarte y José Manuel Colmenar Verdugo. Funding entities: Ministerio de Ciencia Innovación y Universidades. (Ref. PGC2018-095322-B-C22). Duration: 01/01/2019 – 31/12/2021.

Abstract:

Information systems are nowadays commonly represented with a graph, which makes them easier to interpret and understand. A graph is an abstract data structure consisting of nodes and edges, where the nodes, sometimes also referred to as vertices, represent entities, and the edges are links that connect the nodes representing relationships among them. From a theoretical perspective a graph is an ordered pair G = (V, E), where V is the set of vertices and E a set of edges, where each edge associates two vertices in V. This type of graphs is usually referred to as undirected and unweighted graphs. Those graphs where edges have orientation (i.e., given to vertices u, v in V there exist an arc between u and v but not the reverse one) are known as directed graphs. Finally, weighted graphs are those where a number (weight) is assigned to each edge. These weights might represent costs, lengths or capacities, depending on the problem at hand. Some authors call such a graph a network.

Graphs are the basic modeling unit in a wide variety of areas within CS and OR, like project management, production scheduling, line balancing, business plans, or software visualization. Graph theory offers a rich source of problems and techniques for optimization, programming and data structure development. The design of good heuristics or approximation algorithms for optimization problems often requires significant specialized knowledge and trial-and-error over a graph. In many real-world applications, it is typically the case that the same optimization problem is solved again and again on a regular basis, maintaining the same problem structure but differing in the data. This provides an opportunity for learning heuristic algorithms that exploit the structure of such recurring problems. We study the reinforcement learning and graph embedding to address this challenge. The learned greedy policy behaves like a meta-algorithm that incrementally constructs a solution, and the action is determined by the output of a graph embedding network capturing the current state of the solution.

The main objective of this project is to solve difficult optimization problems, NP-hard in scientific terms, see Garey and Johnson, (1990), on a graph modeling a real situation. A difficult optimization problem is one for which it is not possible to guarantee that the optimal solution will be found within a “reasonable” computational time. There are many difficult problems in practice which trigger the development of efficient procedures capable of finding “good” solutions even when these solutions could not be proven optimal. These methods, for which solution quality is as important as the computing time needed to find it, are known as heuristics. Nowadays, a family of modern and intelligent heuristics, usually known as metaheuristics (Glover, 1986), are master strategies that guide subordinate algorithms to produce solutions beyond those that are normally obtained in a quest for local optimality. Metaheuristics are among the most prominent and successful techniques to solve a large amount of complex and computationally hard combinatorial and numerical optimization problems. Both research groups have a long experience on the development and application of these methodologies. In this project, we propose the application of the metaheuristic methodologies to solve difficult graph-based problems arising in business and industry.