Mémoire numérisé par la Direction des bibliothèques de l'Université de Montréal.

Ce travail porte sur un problème inverse de sources dipolaires et son application à l'identification des sources de l'activité cérébrale telle qu'elle peut être mesurée par l'Electro-Encéphalo-Graphie (EEG). Des résultats d'identifiabilité et de stabilité ont été établis. Par ailleurs, une étude du problème de Cauchy en 3D, motivée par l'application de la méthode d'identification dite "algébrique", a été faite à l'aide de la méthode itérative introduite par Kozlov, Maz'ya et Fomin et au moyen des équations intégrales de frontières. En outre, une autre méthode basée sur une fonctionnelle coût de type Kohn et Vogelius a été considérée pour l'identification des sources et dont les résultats numériques sont avérés plus performants que ceux donnés par la méthode des moindres carrés.

La première partie de la thèse porte sur les graphes de Steinhaus réguliers. On commence par obtenir une nouvelle preuve du théorème de Dymacek, selon lequel toute matrice de Steinhaus associée à un graphe pair est bisymétrique, en exhibant une relation entre les éléments de l'antidiagonale d'une matrice de Steinhaus et les degrés des sommets du graphe associé. Ce théorème est ensuite utilisé pour montrer que toute matrice de Steinhaus associée à un graphe régulier de degré impair admet une grande sous-matrice multisymétrique. On étudie alors les matrices de Steinhaus multisymétriques, en particulier celles dont le graphe associé admet une certaine régularité. Cette étude permet enfin de vérifier jusqu'à 1500 sommets une conjecture de Dymacek, qui annonce que le graphe complet à deux sommets K2 est le seul graphe de Steinhaus régulier de degré impair, améliorant ainsi d'un facteur 12 la borne précédemment connue (117 sommets).<br />La seconde partie porte sur les triangles de Steinhaus dans Z/nZ. En 1978 Molluzzo pose le problème de savoir si, pour tout n≥1 et pour toute longueur admissible m, il existe une suite balancée de longueur m dans Z/nZ, c'est-à-dire une suite dont le triangle de Steinhaus associé contienne chaque élément de Z/nZ avec la même multiplicité. On donne ici une réponse complète et positive au Problème de Molluzzo dans tout groupe cyclique d'ordre une puissance de 3. Plus généralement, on construit une infinité de suites balancées dans tout groupe cyclique d'ordre impair. Ces résultats, qui sont les premiers obtenus sur ce problème dans Z/nZ avec n>3, proviennent de l'étude des triangles de Steinhaus des suites arithmétiques dans les groupes cycliques.

Ce travail s'intéresse à l'utilisation de la méthode de quasi-réversibilité pour la résolution de problèmes inverses, un exemple typique étant le problème inverse de l'obstacle. Nous proposons pour ce dernier une nouvelle approche couplant la méthode de quasi-réversibilité et une méthode de lignes de niveau. Plus précisément, à partir d'un ouvert candidat C, nous résolvons un problème de Cauchy à l'extérieur de C, puis nous mettons à jour cet ouvert par la méthode de lignes de niveau. La solution approchée du problème de Cauchy est obtenue en utilisant la méthode de quasi-réversibilité, introduite par J.L. Lions et R. Lattès dans les années soixante. Nous proposons différentes formulations de cette méthode, ainsi que sa discrétisation par éléments finis non conformes adaptés à l'espace de Sobolev H2, et nous prouvons la convergence des éléments finis. En présence d'une donnée bruitée, nous introduisons une nouvelle méthode basée sur la dualité en optimisation et le principe de Morozov. Nous montrons que cette méthode fournit des données régularisées et un choix de paramètre de régularisation pertinent pour la quasi-réversibilité. En ce qui concerne la mise à jour de l'ouvert C, nous proposons deux méthodes de lignes de niveau très différentes : la première est basée sur une équation eikonale, la seconde sur une équation de Poisson. Nous prouvons que ces deux approches assurent la convergence vers l'obstacle. Finalement, nous présentons des résultats numériques pour cette approche couplant quasi-réversibilité/lignes de niveau dans différentes situations : problème inverse de l'obstacle avec condition de Dirichlet, détection de défauts dans une structure élasto-plastique...

Aujourd'hui, l'alimentation représente plus de 70% du coût de production en engraissement porcin et dans le contexte économique actuel, il est important de parvenir à réduire ce coût. L'alimentation utilisée actuellement utilise des phases et est représentée par un modèle linéaire. L'alimentation par mélanges introduite récemment est représentée par un modèle bilinéaire. Nous introduisons ici une nouvelle formulation qui est une combinaison des alimentations traditionnelle par mélanges: la méthode hybride. Nous montrons qu'elle permet de réduire le coût de plus de 5%. L'étude principale porte sur l'optimisation globale du problème bilinéaire, non convexe, modélisant l'alimentation par mélanges. La bilinéarité apparaît dans la fonction objectif et dans les contraintes. Ce problème peut posséder plusieurs minima, mais nous souhaitons obtenir un minimum global. Il est équivalent à un problème de pooling et nous montrons qu'il est fortement NP-difficile. Après de premiers résultats, nous énonçons la conjecture que tout minimum local est global pour ce problème bilinéaire appliqué à l'industrie porcine. Nous la prouvons sur un exemple de dimension réduite. Notre problème ne pouvant pas être résolu avec des solveurs globaux à cause de sa dimension, nous utilisons des approches telle que la pénalisation, la discrétisation, et techniques de relaxation lagrangienne ou convexe. Toutes ces approches supportent notre conjecture. Nous faisons également une étude de la robustesse des modèles à la variation des prix des ingrédients ainsi qu'une étude multicritère nous permettant d'obtenir des résultats numériques réduisant considérablement les rejets, autres enjeux importants. / Today, feed represents more than 70% of the production cost in growing-finishing pig industry and in the current economic context, it is important to reduce it. The feeding system currently used uses phases and is expressed as a linear model. The feeding system using feeds introduced more recently is represented by a bilinear model. We introduced here new feeding system which is a combination offeeding systems using phases and feeds: the hybrid method. We show that it can reduce the feed cost by more than 5%. The main part of this manuscript is about global optimization of the bilinear problem, and non convex, problem modeling feeding system using feeds. The objective function and some constraints are bilinear. This problem can have several local minima but we would like to have a global one. It is equivalent to a pooling problem and we prove that it is a strongly NP-hard problem. After a study of first results, we enounce the conjecture that any local minimum is a global minimum for that problem applied in the pig industry. We prove it for a small size example. Our problem cannot be solved by using global solver due to its size, then we applied some relaxation methods such as penalization of bilinear terms, their discretization and Langrangian and convex relaxations. All these approaches support our conjecture. Then we study the robustness of the models on the ingredient price variations and a multicriteria study reducing phosphorus and nitrogen excretion.

Doctorat en sciences psychologiques / info:eu-repo/semantics/nonPublished

La modélisation et la résolution de problèmes sous contraintes constituent un domaine majeur enIA. Par la nature diverse des contraintes, différents formalismes de représentation ont été proposés pour les exprimer de manière simple et compacte tout en garantissant une efficacité des outils de résolutions associés. Les formules propositionnelles, les réseaux de contraintes discrets (RCD) et qualitatives (RCQ) sont des cadres de modélisation répondant à ces critères. Pour les informations temporelles ou spatiales, les RCQ constituent un modèle de choix avec de nombreuses applications comme l’ordonnancement de tâches, la planification temporelle ou spatiale, les systèmes d’informations géographiques. Nos contributions visent à étudier les liens des RCQ vers les RCD et les formules propositionnelles, afin d’adapter les outils issus des divers domaines et de proposer de nouvelles approches. Tout d’abord, nous nous concentrons sur l’aspect structurel des RCQ, en adaptant la méthode de la composition faible dans les différents cadres. Nous exploitons ensuite les propriétés des classes traitables de certains formalismes qualitatifs, afin de définir une transformation vers la logique propositionnelle. En exploitant la transformation vers les RCD, nous proposons une méthode incomplète facilitant la preuve de l’incohérence des RCQ par la relaxation de la propriété de composition faible, puis nous complétons l’approche en exploitant les classes traitables. Enfin, ces études nous conduisent à proposer une nouvelle forme de substituabilité locale, dont les détections statique et dynamique permettent d’obtenir une amélioration algorithmique dans le cadre des RCD. / Modelling and solving constraints problems is a major domain in Artificial Intelligence. By the various natures of the constraints, different formalisms were proposed to express them in a simple andcompact way while guaranteeing the effectiveness of the associated solution tools. Propositional formulae, discrete constraint networks (DCNs), and qualitative constraint networks (QCNs) are the well known frameworks that guaranty these requirements. For temporal or space information, QCNs constitute a model of choice with many real world applications such as scheduling, temporal or spatial planning and geographic information systems. Our contributions aim at studying the links between QCNs, DCNs and propositional formulas, in order to adapt the tools developed in these fields and to propose new approaches. First of all, we focus on the structural aspects of QCNs, by transforming weak composition within the various frameworks. In order to define a transformation towards propositional logic we then exploit the properties of tractable classes of some qualitative formalism. Exploiting the transformation towards DCNs, we propose an incomplete method simplifying the proof of the inconsistency for QCNs by relaxing the weak composition property. Then, we propose a complete approach thanks to tractable classes. Finally, these studies lead us to propose a new form of local substitutability, whose static and dynamic detections significantly improve search algorithms for DCNs.

Le problème de tournées de véhicules est un des problèmes d'optimisation combinatoire les plus connus et les plus difficiles. Il s'agit de déterminer les tournées optimales pour une flotte de véhicules afin de servir un ensemble donné de clients. Dans les problèmes classiques de transport, chaque client est normalement servi à partir d'un seul nœud (ou arc). Pour cela, on définit toujours un ensemble donné de nœuds (ou arcs) obligatoires à visiter ou traverser, et on recherche la solution à partir de cet ensemble de nœuds (ou arcs). Mais dans plusieurs applications réelles où un client peut être servi à partir de plus d'un nœud, (ou arc), les problèmes généralisés qui en résultent sont plus complexes. Le but principal de cette thèse est d'étudier trois problèmes généralisés de tournées de véhicules. Le premier problème de la tournée sur arcs suffisamment proche (CEARP), comporte une application réelle intéressante en routage pour le relevé des compteurs à distance ; les deux autres problèmes, problème de tournées couvrantes multi-véhicules (mCTP) et problème généralisé de tournées sur nœuds (GVRP), permettent de modéliser des problèmes de conception des réseaux de transport à deux niveaux. Pour résoudre ces problèmes, nous proposons une approche exacte ainsi que des métaheuristiques. Pour développer la méthode exacte, nous formulons chaque problème comme un programme mathématique, puis nous construisons des algorithmes de type branchement et coupes. Les métaheuristiques sont basées sur le ELS (ou Evolutionary Local Search) et sur le GRASP (ou Greedy Randomized Adaptive Search Procedure). De nombreuses expérimentations montrent la performance de nos méthodes.

Qu'est-ce qu'un problème informationnel ? Comment et par qui est-il défini ? Celui-ci n'existerait jamais seul... Il s'enchâsserait dans une dynamique décisionnelle à laquelle il emprunterait une histoire, une culture et une mémoire. Ainsi, pour être en mesure de le cerner, il faudrait alors se référer à son origine, c'est-à-dire au problème décisionnel, dont il ne serait qu'une traduction partielle, et à son géniteur, le décideur, qui est aussi son interprète. <br />Dans le contexte de cette étude, nous porterons notre attention sur l'intelligence économique que nous définirons comme étant une démarche collaborative de compréhension et de résolution de problèmes décisionnels et informationnels. Tout en considérant cette démarche, à la fois sur ses aspects informationnels et médiationnels, nous circonscrirons l'intelligence économique à travers une méthodologie collective de résolution, composée de huit étapes s'étendant de l'identification d'un problème décisionnel à la prise de décision. Nous verrons que cette démarche s'appuie, au niveau de l'entreprise, sur une harmonisation de processus et de médiations, structurée autour de deux acteurs et d'une composante : le décideur, le veilleur et l'information. Cette représentation triangulaire des différentes relations entre acteurs et composante, prises deux à deux, constituera l'originalité de notre approche. En nous plaçant du point de vue du veilleur, acteur pivot de ce trinôme décisionnel, notre réflexion se portera sur la modélisation des activités de recherche d'information engendrées par la demande et plus particulièrement sur la deuxième étape de cette démarche : la traduction du problème décisionnel en problème informationnel. Cette thèse a été structurée de manière à présenter la dualité de ces relations entre ces trois protagonistes.<br />Dans ce contexte décisio-informationnel, cette problématique de traduction serait alors bien plus qu'un rapport de langue à langue : elle serait une concordance de problème à problème. Elle demanderait de créer une congruence entre les systèmes de préférences et de pertinence de nos deux acteurs, l'interprétation de la demande informationnelle se devant être dans cette situation, affaire de consensus et de compromis. Pour ce faire, le veilleur aura pour tâche de représenter le plus fidèlement possible les relations entre les données de l'environnement et les enjeux du problème décisionnel afin de les traduire en indicateurs informationnels, c'est-à-dire de trouver une illustration adaptée permettant de les rendre sensibles au cœur et familiers à la raison du décideur. Ainsi, pour répondre dans les meilleures conditions de délais, qualité et coûts à cette demande, nous prendrons pour hypothèse qu'il faut agir sur trois processus à travers les info-, inter- et cogito- médiations des relations entre le décideur, le veilleur et l'information.<br />Notre état de la littérature présentera tout au long des quatre premiers chapitres les processus décider, rechercher et coopérer que nous projetterons dans chacun des espaces des problèmes décisionnel et informationnel. Nous étayerons chacun de ces chapitres de propositions, tantôt pour caractériser les processus, les médiations, les acteurs et composantes, tantôt pour définir des protocoles pour asseoir la collaboration des acteurs ou pour la réutilisation des informations et des connaissances. Les deux derniers chapitres seront, quant à eux, consacrés à la description du modèle WISP et du prototype METIORE qui l'instancie. Ils constitueront, avec les propositions des précédents chapitres, l'apport de nos travaux dans les domaines de la recherche d'information et de l'intelligence économique. Ils ont été conçus tout deux pour servir d'appui cognitif pour la résolution du problème informationnel du veilleur et pour être une interface de communication entre ce dernier et le décideur afin de développer les échanges au sein de la collaboration de résolution de ce, ou de ces problèmes...

Le problème de la clique maximum (MCP) est un problème d'optimisation combinatoire important avec un large éventail d'applications pratiques dans de nombreux domaines, y compris la recherche d'information, l'analyse de la transmission du signal, la théorie de la classification, l'économie, la planification et l'ingénierie biomédicale. En outre, un certain nombre de problèmes d'optimisation combinatoire sont étroitement liés au MCP, tels que la coloration de graphe, la somme coloration, réglez détermination du gagnant emballage et optimale. Cette thèse est consacrée à l'élaboration d'approches heuristiques efficaces pour s'attaquer au problème de la clique maximum et ses généralisations. Pour atteindre cet objectif, nous avons développé une approche de recherche tabou adaptative multistart pour le problème de clique maximum classique, un algorithme recherche tabou multi-voisinage pour la clique maximum de sommets pondérés, et une méthode métaheuristique hybride pour le problème de la clique maximum d'arêtes pondérés. En outre, nous appliquons ces méthodes heuristiques développées pour résoudre ces problèmes difficiles qui sont étroitement liés au problème de la clique maximum. Tous les algorithmes sont mis en oeuvre et testés avec succès sur un certain nombre de cas de référence provenant de divers domaines d'application. Les méthodes proposées concurrencent favorablement les autres approches de l'état de l'art.