When operations research meets structural pattern recognition : on the solution of error-tolerant graph matching problems / Mostafa Darwiche ; sous la direction de Donatello Conte et de Vincent T'Kindt

Date :

Type : Livre / Book

Type : Thèse / Thesis

Langue / Language : anglais / English

Reconnaissance d'objets (informatique)

Recherche opérationnelle

Explorations de graphes

Métaheuristiques

Modèles linéaires (statistique)

Appariement (statistique)

Partitionnement de graphes

Programmation linéaire

Recherche linéaire (optimisation mathématique)

Conte, Donatello (1976-.... ; chercheur en informatique) (Directeur de thèse / thesis advisor)

T'kindt, Vincent (1973-.... ; chercheur en informatique) (Directeur de thèse / thesis advisor)

Adam, Sébastien (1975-.... ; enseignant-chercheur en génie informatique) (Président du jury de soutenance / praeses)

Della Croce, Federico (Rapporteur de la thèse / thesis reporter)

Solnon, Christine (19..-.... ; chercheuse en informatique) (Rapporteur de la thèse / thesis reporter)

Raveaux, Romain (1981-....) (Membre du jury / opponent)

Habib, Michel (19..-.... ; informaticien) (Membre du jury / opponent)

Université de Tours (1971-....) (Organisme de soutenance / degree-grantor)

École doctorale Mathématiques, Informatique, Physique Théorique et Ingénierie des Systèmes (Centre-Val de Loire) (Ecole doctorale associée à la thèse / doctoral school)

Laboratoire d'Informatique Fondamentale et Appliquée de Tours (2012-...) (Equipe de recherche associée à la thèse / thesis associated research team)

École polytechnique universitaire (Tours) (Laboratoire associé à la thèse / thesis associated laboratory)

Résumé / Abstract : Cette thèse se situe à l’intersection de deux domaines de recherche scientifique la Reconnaissance d’Objets Structurels (ROS) et la Recherche Opérationnelle (RO). Le premier consiste à rendre la machine plus intelligente et à reconnaître les objets, en particulier ceux basés sur les graphes. Alors que le second se focalise sur la résolution de problèmes d’optimisation combinatoire difficiles. L’idée principale de cette thèse est de combiner les connaissances de ces deux domaines. Parmi les problèmes difficiles existants en ROS, le problème de la distance d’édition entre graphes (DEG) a été sélectionné comme le cœur de ce travail. Les contributions portent sur la conception de méthodes adoptées du domaine RO pour la résolution du problème de DEG. Explicitement, des nouveaux modèles linéaires en nombre entiers et des matheuristiques ont été développé à cet effet et de très bons résultats ont été obtenus par rapport à des approches existantes.

Résumé / Abstract : This thesis is focused on Graph Matching (GM) problems and in particular the Graph Edit Distance (GED) problems. There is a growing interest in these problems due to their numerous applications in different research domains, e.g. biology, chemistry, computer vision, etc. However, these problems are known to be complex and hard to solve, as the GED is a NP-hard problem. The main objectives sought in this thesis, are to develop methods for solving GED problems to optimality and/or heuristically. Operations Research (OR) field offers a wide range of exact and heuristic algorithms that have accomplished very good results when solving optimization problems. So, basically all the contributions presented in thesis are methods inspired from OR field. The exact methods are designed based on deep analysis and understanding of the problem, and are presented as Mixed Integer Linear Program (MILP) formulations. The proposed heuristic approaches are adapted versions of existing MILP-based heuristics (also known as matheuristics), by considering problem-dependent information to improve their performances and accuracy.