The Graph Edit Distance Problem treated by the Local Branching Heuristic

International audienceThe Graph Edit Distance (GED) is a well-known problem to match graphs. Solving the GED problem allows computing a dissimilarity measure between graphs that normally represent objects and patterns. It is known to be very flexible and can work on any type of graphs. GED EnA (Edges no Attributes) is a sub-problem of GED that deals with a special type of graphs where edges do not carry attributes. Both are modeled as minimization problems and proven to be NP-Hard, they are exponential in the number of vertices of graphs. A great effort has been made to provide heuristic approaches with a compromise between the execution time and the solution quality. In addition, GED EnA can be expressed efficiently by means of mathematical programming tools to generate Mixed Integer Linear Program (MILP) models. The present work takes advantage of a powerful MILP model and proposes a heuristic called Local Branching to solve the GED EnA problem. Mainly, a MILP model is iteratively modified by adding additional constraints to define neighborhoods in the solution space which are explored using a black-box solver. A problem-dependent exploration is performed to find efficient solutions. Lastly, the proposed heuristic is evaluated considering two factors: its computational time and solution quality against literature heuristics and exact methods