When Operations Research meets Structural Pattern Recognition:

on the solution of Error-Tolerant Graph Matching problems

Introduction

This site provides access to all materials (source code, list of publications, etc.) produced during the Ph.D. of Mostafa Darwiche, which is entitled:

When Operations Research meets Structural Pattern Recognition:

on the solution of Error-Tolerant Graph Matching problems

The thesis took place at the LIFAT lab, university of Tours, France.

Main actors:

Mostafa Darwiche^1,2
Dr. Romain Raveaux¹
Dr. Donatello Conte¹
Pr. Vincent T'Kindt²

¹ Laboratoire d’Informatique Fondamentale et Appliquée de Tours (EA 6300), University of Tours, France

² Laboratoire d'Informatique Fondamentale et Appliquée de Tours (EA 6300), ERL-CNRS 6305, University of Tours, France

Synopsis

This thesis is at the intersection of two research fields: Operations Research (OR) and Structural Pattern Recognition SPR). The ultimate objective is to develop new efficient techniques for solving Graph Matching (GM) problems, and in particular the Graph Edit Distance (GED) problem. The selected techniques to tackle the GED problem are mainly adopted from the OR field such as mathematical programming, matheuristics, among others. Finally, the contributions accomplished during the thesis are split into two main categories:

Exact methods: which are Mixed Integer Linear Programs (MILP) modeling the GED problem mathematically. Later, these models can be solved by any commercial solver (such as CPLEX) to compute the optimal solution of a given instance. One MILP model that has proven to perform better than existing ones is the F3 model.
Matheuristic methods: which are heuristic approaches incorporating famous techniques (such as neighborhood exploration, intensification and diversification) into solving a MILP model. Two matheuristics are developed that have outperformed the existing heuristics are Local Branching and Variable Partitioning Local Search denoted, respectively, by LocBra and VPLS.

For more details about the methods, the algorithms and the numerical results, kindly check the manuscript of the thesis.

List of publications

Publications in scientific journals:

Darwiche, M., Conte, D., Raveaux, R., & T’Kindt, V. (2018). Graph Edit Distance: Accuracy of Local Branching from an application point of view. Pattern Recognition Letters.
Darwiche, M., Conte, D., Raveaux, R., & T’Kindt, V. (2019). A local branching heuristic for solving a graph edit distance problem. Computers & Operations Research, 106, 225-235.

Publications in international conferences:

Darwiche, M., Raveaux, R., Conte, D., & T’Kindt, V. (2019, June). Solving the graph edit distance problem with variable partitioning local search. In IAPR International workshop on Graph-Based Representation in Pattern Recognition (GbR19).
Darwiche, M., Raveaux, R., Conte, D., & T’Kindt, V. (2018, August). Graph Edit Distance in the exact context. In Joint IAPR International Workshops on Statistical Techniques in Pattern Recognition (SPR) and Structural and Syntactic Pattern Recognition (SSPR) (pp. 304-314). Springer, Cham.
Darwiche, M., Raveaux, R., Conte, D., & T'Kindt, V. (2018, June). Solving a special case of the Graph Edit Distance Problem with Local Branching. In Matheuristics 2018.
Darwiche, M., Raveaux, R., Conte, D., & T'Kindt, V. (2018, April). A New Mixed Integer Linear Program for the Graph Edit Distance Problem. In ISCO18 (Vol. 72, pp. 254-265).
Darwiche, M., Raveaux, R., Conte, D., & T’Kindt, V. (2017, November). A Local Branching Heuristic for the Graph Edit Distance Problem. In Iberoamerican Congress on Pattern Recognition (Vol. 10657, pp. 194-202). Springer, Cham.
Darwiche, M., Conte, D., Raveaux, R., & T'Kindt, V. (2017, July). The Graph Edit Distance Problem treated by the Local Branching Heuristic. In MIC17 12th Metaheuristics International Conference.

Publications in national conferences:

Darwiche, M., Conte, D., Raveaux, R., & T'Kindt, V. (2019, February). Résoudre le problème de la distance d'édition entre graphes avec les matheuristiques. In ROADEF19.
Darwiche, M., Conte, D., Raveaux, R., & T'Kindt, V. (2018, February). Formulation linéaire en nombres entiers pour le problème de la distance d'édition entre graphes. In ROADEF18.
Darwiche, M., Conte, D., Raveaux, R., & T'Kindt, V. (2017, February). Evaluation de modèles mathématiques pour le problème de la distance d'édition entre graphes. In ROADEF2017.

Google Sites

Report abuse