Solving a special case of the Graph Edit Distance Problem with Local Branching

International audienceThe Graph Edit Distance (GED) problem is a well-known graph matching problem. Solving the GED problem implies minimizing 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. Many heuristics are defined in the literature to give approximated solutions in a reasonable CPU time. Some other work have used mathematical programming to come up with Mixed Integer Linear Program (MILP) models. The present work proposes the use of Local Branching heuristic over a powerful MILP model 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 w.r.t literature heuristics