Les problèmes d'optimisation issus du monde réel sont souvent complexes et NP-difficiles. Leur modélisation est en constante évolution en termes de contraintes et d'objectifs, et leur résolution est coûteuse en temps de calcul. Bien que des algorithmes approchés telles que les métaheuristiques (heuristiques génériques) permettent de réduire la complexité de leur résolution, ces méthodes restent insuffisantes pour traiter des problèmes de grande taille. Au cours des dernières décennies, le calcul parallèle s'est révélé comme un moyen incontournable pour faire face à de grandes instances de problèmes difficiles d'optimisation. La conception et l'implémentation de métaheuristiques parallèles sont ainsi fortement influencées par l'architecture parallèle considérée. De nos jours, le calcul sur GPU s'est récemment révélé efficace pour traiter des problèmes coûteux en temps de calcul. Cette nouvelle technologie émergente est considérée comme extrêmement utile pour accélérer de nombreux algorithmes complexes. Un des enjeux majeurs pour les métaheuristiques est de repenser les modèles existants et les paradigmes de programmation parallèle pour permettre leurdéploiement sur les accélérateurs GPU. De manière générale, les problèmes qui se posent sont la répartition des tâches entre le CPU et le GPU, la synchronisation des threads, l'optimisation des transferts de données entre les différentes mémoires, les contraintes de capacité mémoire, etc. La contribution de cette thèse est de faire face à ces problèmes pour la reconception des modèles parallèles des métaheuristiques pour permettre la résolution des problèmes d'optimisation à large échelle sur les architectures GPU. Notre objectif est de repenser les modèles parallèles existants et de permettre leur déploiement sur GPU. Ainsi, nous proposons dans ce document une nouvelle ligne directrice pour la construction de métaheuristiques parallèles efficaces sur GPU. Le défi de cette thèse porte sur la conception de toute la hiérarchie des modèles parallèles sur GPU. Pour cela, des approches très efficaces ont été proposées pour l'optimisation des transferts de données entre le CPU et le GPU, le contrôle de threads, l'association entre les solutions et les threads, ou encore la gestion de la mémoire. Les approches proposées ont été expérimentées de façon exhaustive en utilisant cinq problèmes d'optimisation et quatre configurations GPU. En comparaison avec une exécution sur CPU, les accélérations obtenues vont jusqu'à 80 fois plus vite pour des grands problèmes d'optimisation combinatoire et jusqu'à 2000 fois plus vite pour un problème d'optimisation continue. Les différents travaux liés à cette thèse ont fait l'objet d'une douzaine publications comprenant la revue IEEE Transactions on Computers. / Real-world optimization problems are often complex and NP-hard. Their modeling is continuously evolving in terms of constraints and objectives, and their resolution is CPU time-consuming. Although near-optimal algorithms such as metaheuristics (generic heuristics) make it possible to reduce the temporal complexity of their resolution, they fail to tackle large problems satisfactorily. Over the last decades, parallel computing has been revealed as an unavoidable way to deal with large problem instances of difficult optimization problems. The design and implementation of parallel metaheuristics are strongly influenced by the computing platform. Nowadays, GPU computing has recently been revealed effective to deal with time-intensive problems. This new emerging technology is believed to be extremely useful to speed up many complex algorithms. One of the major issues for metaheuristics is to rethink existing parallel models and programming paradigms to allow their deployment on GPU accelerators. Generally speaking, the major issues we have to deal with are: the distribution of data processing between CPU and GPU, the thread synchronization, the optimization of data transfer between the different memories, the memory capacity constraints, etc. The contribution of this thesis is to deal with such issues for the redesign of parallel models of metaheuristics to allow solving of large scale optimization problems on GPU architectures. Our objective is to rethink the existing parallel models and to enable their deployment on GPUs. Thereby, we propose in this document a new generic guideline for building efficient parallel metaheuristics on GPU. Our challenge is to come out with the GPU-based design of the whole hierarchy of parallel models.In this purpose, very efficient approaches are proposed for CPU-GPU data transfer optimization, thread control, mapping of solutions to GPU threadsor memory management. These approaches have been exhaustively experimented using five optimization problems and four GPU configurations. Compared to a CPU-based execution, experiments report up to 80-fold acceleration for large combinatorial problems and up to 2000-fold speed-up for a continuous problem. The different works related to this thesis have been accepted in a dozen of publications, including the IEEE Transactions on Computers journal.

Les technologies du numérique s’invitent de plus en plus dans l’enseignement. Les nouvelles pratiques pédagogiques révolutionnent également les standards de la formation. La « gamification » des cursus est, par exemple, devenue une tendance actuelle. Elle permet, par le jeu, d’exercer les apprenants différemment. Les simulations de gestion d’entreprise entrent dans ce cadre. Elles positionnent les stagiaires à la tête d’entreprises virtuelles et simulent un marché concurrentiel. Le déploiement de cette pratique se heurte néanmoins à des difficultés opérationnelles : taille du groupe, formation de l’animateur… C’est dans ce contexte que nous envisageons la mise en œuvre d’agents autonomes permettant d’accompagner ou de concurrencer les apprenants.Pour cela, nous proposons, tout d’abord, une modélisation performante d’une entreprise à base de programmes linéaires mixtes permettant l’optimisation des départements internes des entreprises (production, distribution, finance). Ensuite, nous introduisons une heuristique de recherche locale afin de générer des solutions performantes dans un environnement économique. Aussi, à la suite d’une phase d’extraction de connaissances, nous proposons la définition et la construction d’arbres d’anticipation qui permettent de prévoir les décisions concurrentielles des protagonistes engagés et ainsi de pouvoir estimer la qualité des solutions construites. Afin de valider les approches proposées, nous les avons comparées aux comportements réels de joueurs et avons évalué l’apport de l’exploitation de la connaissance. Enfin, nous avons proposé une généralisation de la méthode à d’autres simulateurs de gestion d’entreprise. / Digital technologies are becoming increasingly popular in teaching and learning processes. New educational practices are also revolutionizing the standards of training. For example, the "gamification" of the curricula has become a current trend. It allows, through games, to exercise learners differently. Business management simulation, also known as business games, fall within this context. They place learners at the head of virtual companies and simulate a competitive market. The deployment of this practice nevertheless encounters some operational difficulties: size of the group, training of the teacher... It is in this context that we envisage the implementation of autonomous agents to accompany the learners or the competitors.To do this, firstly, we propose a modeling of a company, based on mixed linear programs allowing optimization of the internal departments of the companies (production, delivery, finance). For the second step, we will introduce a local heuristic search, ensuring a generation of efficient solutions in a given economic and competitive environment. Thirdly, following a knowledge extraction phase, we propose the definition and construction of anticipation trees that predict the competitive decisions of the engaged protagonists and thus to be able to estimate the quality of the solutions built. In order to validate the proposed approaches, we compared them with the real behaviors of players and evaluated the contribution of the exploitation of the knowledge. Finally, we proposed a framework allowing a generalization of the method to other business games.

Le cloud computing a émergé au cours de la dernière décennie pour être largement adopté aujourd’hui dans plusieurs domaines de l’informatique. Il consiste à proposer des ressources axées, ou non, sur le marché sous forme de services qui peuvent être consommés de manière souple et transparente. Dans cette thèse, nous traitons le problème d’ordonnancement, un des enjeux majeurs du cloud. Selon la configuration de cloud ciblée, nous avons identifié trois niveaux d’ordonnancement : niveau service, niveau tâche et niveau machine virtuelle. Nous revisitons la modélisation du problème, la conception et l’implémentation des métaheuristiques multiobjectives pour chaque niveau d’ordonnancement du cloud. Les ordonnanceurs à base de métaheuristiques que nous proposons portent sur différents critères notamment la consommation d’énergie, les émissions de gaz à effet de serre, le profit et la qualité du service (coût et temps de réponse). Nous prouvons leur capacité d’adaptation aux contraintes du cloud en les intégrant au sein du gestionnaire de cloud OpenNebula. De plus, nos ordonnanceurs ont été largement expérimentés utilisant des configurations réalistes de cloud sur Grid’5000, en tant qu’infrastructure en tant que service (IAAS), et des scénarios concrets basés sur les instances et les tarifications d’Amazon EC2. Les résultats présentés montrent que les méthodes que nous proposons surpassent les approches d’ordonnancement existantes sur tous les critères cités précédemment. / Cloud computing has emerged during the last decade to be widely adopted nowadays in several IT areas. It consists to propose market or not market-oriented resources as services that can be consumed in a ubiquitous, flexible and transparent way. In this PhD thesis, we deal with scheduling, one of the major cloud computing issue. According to the targeted cloud configuration, we have identified three levels of scheduling: service-level, task-level and Virtual Machine-level. We revisit the problem modeling, the design and the implementation of multi-objective metaheuristics for each scheduling level of the cloud. The proposed metaheuristics-based schedulers address different criteria including energy consumption, greenhouse gas emissions, profit and QoS (cost and response time). We prove their adaptability to the cloud constraints by integrating them as a part of the OpenNebula cloud manager. Moreover, our schedulers have been extensively experimented using realistic cloud configurations on Grid'5000, considered as an infrastructure as a service (IAAS), and concrete scenarios based on Amazon EC2 instances and prices. The reported results show that our proposed methods outperform existing scheduling approaches in terms of all previously cited criteria.

Les problèmes d'optimisation à grande échelle sont généralement difficiles à résoudre de façon optimale.Des algorithmes d'approximation tels que les métaheuristiques, capables de trouver rapidement des solutions sous-optimales, sont souvent préférés. Cette thèse porte sur les algorithmes de recherche locale multi-objectif (MOLS), des métaheuristiques capables de traiter l'optimisation simultanée de plusieurs critères. Comme de nombreux algorithmes, les MOLS exposent de nombreux paramètres qui ont un impact important sur leurs performances. Ces paramètres peuvent être soit prédits et définis avant l'exécution de l'algorithme, soit ensuite modifiés dynamiquement. Alors que de nombreux progrès ont récemment été réalisés pour la conception automatique d'algorithmes, la grande majorité d'entre eux ne traitent que d'algorithmes mono-objectif et l'optimisation d'un unique indicateur de performance. Dans cette thèse, nous étudions les relations entre la conception automatique d'algorithmes et l'optimisation multi-objective. Nous passons d'abord en revue les stratégies MOLS possibles et présentons un framework MOLS général et hautement configurable. Nous proposons également MO-ParamILS, un configurateur automatique spécialement conçu pour gérer plusieurs indicateurs de performance. Nous menons ensuite plusieurs études sur la conception automatique de MOLS sur de multiples problèmes combinatoires bi-objectifs. Enfin, nous discutons deux extensions de la configuration d'algorithme classique : d'abord l'intégration des mécanismes de contrôle de paramètres, pour bénéficier de multiples prédictions de configuration; puis l'utilisation séquentielle de plusieurs configurations. / Large-scale optimisation problems are usually hard to solve optimally.Approximation algorithms such as metaheuristics, able to quickly find sub-optimal solutions, are often preferred.This thesis focuses on multi-objective local search (MOLS) algorithms, metaheuristics able to deal with the simultaneous optimisation of multiple criteria. As many algorithms, metaheuristics expose many parameters that significantly impact their performance. These parameters can be either predicted and set before the execution of the algorithm, or dynamically modified during the execution itself. While in the last decade many advances have been made on the automatic design of algorithms, the great majority of them only deal with single-objective algorithms and the optimisation of a single performance indicator such as the algorithm running time or the final solution quality. In this thesis, we investigate the relations between automatic algorithm design and multi-objective optimisation, with an application on MOLS algorithms. We first review possible MOLS strategies ans parameters and present a general, highly configurable, MOLS framework. We also propose MO-ParamILS, an automatic configurator specifically designed to deal with multiple performance indicators. Then, we conduct several studies on the automatic offline design of MOLS algorithms on multiple combinatorial bi-objective problems. Finally, we discuss two online extensions of classical algorithm configuration: first the integration of parameter control mechanisms, to benefit from having multiple configuration predictions; then the use of configuration schedules, to sequentially use multiple configurations.

Cette thèse traite de la segmentation et du suivi de structures curvilinéaires. La méthodologie proposée est appliquée à la segmentation et au suivi des guide-fils durant les interventions d'angioplastie. Pendant ces opérations, les cardiologues s'assurent que le positionnement des différents outils est correct au moyen d'un système d'imagerie fluoroscopique temps-réel. Les images obtenues sont très bruitées et les guides sont, en conséquence, particulièrement difficiles à segmenter. Les contributions de cette thèse peuvent être regroupées en trois parties. La première est consacrée à la détection des guides, la seconde a leur segmentation et la dernière a leur suivi. La détection partielle des guide-fils est réalisée soit par la sélection d'un opérateur de filtrage approprié soit en utilisant des méthodes modernes d'apprentissage artificiel. Dans un premier temps, un système réalisant un Boosting asymétrique pour entraîner un détecteur de guides est présenté. Par la suite, une méthode renforçant la réponse d'un filtre orientable au moyen d'une variante efficace de vote tensoriel est décrite. Dans la seconde partie, une approche ascendante est proposée, qui consiste à regrouper des points sélectionnés par le détecteur de fil, à extraire des primitives des agrégats obtenus et a les lier. Deux procédures locales de regroupement des points sont étudiées : une reposant sur un clustering de graphe non supervisé suivi d'une extraction de segments de droites ; et l'autre reposant sur un modèle graphique puis une extraction d'axe central. Par la suite, deux méthodes de liaison des primitives sont étudiées : la première repose sur une approche de programmation linéaire, et la seconde sur une heuristique de recherche locale. Dans la dernière partie, des méthodes de recalage sont utilisées pour améliorer la segmentation et pour suivre les fils. Le suivi propos'e couple un suivi iconique avec un suivi géométrique contenant un modèle prédictif. Cette méthode utilise un modèle graphique déterminant à la fois une position du guide-fil (segmentation) et des correspondances (tracking). La solution optimale de ce modèle graphique décrit simultanément les déplacements du guide-fil et les appariements entre points d'intérêt qui en sont extraits, fournissant ainsi une estimation robuste des déformations du fil par rapport aux grands déplacements et au bruit.

La Programmation Linéaire en Nombres Entiers (PLNE) est couramment utilisée pour modéliser des problèmes d'optimisation du monde industriel, de par la facilité à modéliser des problèmes complexes d'optimisation et par l’existence d’une résolution générique par l'algorithme de Branch&Bound (B&B). La résolution B&B est souvent limitée pour des problèmes de taille réelle, les méthodes heuristiques sont alors utilisées pour trouver des solutions de bonne qualité sans avoir de preuve d'optimalité. Cette thèse étudie les limites de la résolution exacte et des heuristiques sur des problèmes industriels d'EDF, en vue de leur insertion dans le processus décisionnel opérationnel. L'application principale concerne la planification des arrêts de maintenance et de rechargement des centrales nucléaires, sujet du Challenge ROADEF 2010. Nous avons aussi traité un problème de production journalière d'un parc thermique à flammes. La méthodologie suivie est analogue pour les deux cas. On modélise tout d'abord le problème avec une formulation compacte PLNE, pour en analyser les limites de la résolution frontale, avant d’envisager des méthodes de décomposition. On dérive ensuite les méthodes exactes en matheuristiques pour résoudre des instances de taille réelle. Dans cette optique, l'hybridation de Variable Neighborhood Search (VNS) avec des voisinages définis par PLNE a donné des résultats très probants sur les deux problèmes en termes de qualités de solutions. Le fait d'avoir travaillé avec des méthodes exactes a permis également de chiffrer l'impact d'hypothèses de résolutions, de répondre à des considérations opérationnelles, mais également d'obtenir des bornes inférieures. / Mixed Integer Linear Programming (MILP) is a very popular and useful framework to model industrial optimization problems. This success is due to the facility to model complex optimization problems, the work can be focused on modeling, with a black box generic resolution to optimality with Branch&Bound (B&B) algorithm, or with a specialized decomposition algorithm. If MILP made lots of progresses on the last decades, it is often not sufficient to tackle real world size instances. In such cases, heuristic methods are commonly used to find good quality solutions, without any guarantee to reach the optimum and any proven bound to the optimum. Our work focus on two complex optimization problems from energy management. First application is a discretized daily Unit Commitment Problem of thermal units with specific dynamic constraints. Second application comes from the EURO/ROADEF 2010 challenge, scheduling problem of nuclear power plants' outages for maintenances and refueling. In both cases the methodology was first to model efficiently the considered problem with a MILP compact formulation, and analyze the frontal resolution's limits with B&B. Decomposition methods could also be investigated, before the exact methods are derived in a matheuristic, to be able to tackle real size instances. In particular, Variable Neighborhood Search (VNS) with MILP neighborhoods gave outstanding results on our problems. Our work allowed to estimate the impacts of usual and natural hypothesis. Furthermore, we derived dual bounds for these optimizations problems.

Thèse numérisée par la Direction des bibliothèques de l'Université de Montréal.

Cette thèse traite de la segmentation et du suivi de structures curvilinéaires. La méthodologie proposée est appliquée à la segmentation et au suivi des guide-fils durant les interventions d’angioplastie. Pendant ces opérations, les cardiologues s’assurent que le positionnement des différents outils est correct au moyen d’un système d’imagerie fluoroscopique temps-réel. Les images obtenues sont très bruitées et les guides sont, en conséquence, particulièrement difficiles à segmenter. Les contributions de cette thèse peuvent être regroupées en trois parties. La première est consacrée à la détection des guides, la seconde a leur segmentation et la dernière a leur suivi. La détection partielle des guide-fils est réalisée soit par la sélection d’un opérateur de filtrage approprié soit en utilisant des méthodes modernes d’apprentissage artificiel. Dans un premier temps, un système réalisant un Boosting asymétrique pour entraîner un détecteur de guides est présenté. Par la suite, une méthode renforçant la réponse d’un filtre orientable au moyen d’une variante efficace de vote tensoriel est décrite. Dans la seconde partie, une approche ascendante est proposée, qui consiste à regrouper des points sélectionnés par le détecteur de fil, à extraire des primitives des agrégats obtenus et a les lier. Deux procédures locales de regroupement des points sont étudiées : une reposant sur un clustering de graphe non supervisé suivi d’une extraction de segments de droites ; et l’autre reposant sur un modèle graphique puis une extraction d’axe central. Par la suite, deux méthodes de liaison des primitives sont étudiées : la première repose sur une approche de programmation linéaire, et la seconde sur une heuristique de recherche locale. Dans la dernière partie, des méthodes de recalage sont utilisées pour améliorer la segmentation et pour suivre les fils. Le suivi propos´e couple un suivi iconique avec un suivi géométrique contenant un modèle prédictif. Cette méthode utilise un modèle graphique déterminant à la fois une position du guide-fil (segmentation) et des correspondances (tracking). La solution optimale de ce modèle graphique décrit simultanément les déplacements du guide-fil et les appariements entre points d’intérêt qui en sont extraits, fournissant ainsi une estimation robuste des déformations du fil par rapport aux grands déplacements et au bruit. / This thesis addresses the segmentation and the tracking of thin curvilinear structures. The proposed methodology is applied to the delineation and the tracking of the guide-wires that are used during cardiac angioplasty. During these interventions, cardiologists assess the displacement of the different devices with a real-time fluoroscopic imaging system. The obtained images are very noisy and, as a result, guide-wires are particularly challenging to segment and track. The contributions of this thesis can be grouped into three parts. The first part is devoted to the detection of the guide-wires, the second part addresses their segmentation and the last part focuses on their spatio-temporal tracking. Partial detection of guide-wires is addressed either through the selection of appropriate filter operators or using modern machine learning methods. First, a learning framework using an asymmetric Boosting algorithm for training a guidewire detector is presented. A second method enhancing the output of a steerable filter by using an efficient tensor voting variant is then described. In the second part, a bottom-up method is proposed, that consists in grouping points selected by the wire detector, in extracting primitives from these aggregates and in linking these primitives together. Two local grouping procedures are investigated: one based on unsupervised graph-based clustering followed by a linesegment extraction and one based on a graphical model formulation followed by a graph-based centerline extraction. Subsequently, two variants of linking methods are investigated: one is based on integer programming and one on a local search heuristic. In the last part, registration methods are exploited for improving the segmentation via an image fusion method and then for tracking the wires. This latter is performed by a graph-based iconic tracking method coupled with a graphbased geometric tracking that encodes to certain extend a predictive model. This method uses a coupled graphical model that seeks both optimal position (segmentation) and spatio-temporal correspondences (tracking). The optimal solution of this graphical model simultaneously determines the guide-wire displacements and matches the landmarks that are extracted along it, what provides a robust estimation of the wire deformations with respect to large motion and noise.

Dans cette thèse, nous proposons un modèle de calcul parallèle, appelé « matrice cellulaire », pour apporter des réponses aux problématiques de calcul parallèle appliqué à la résolution de problèmes d’appariement de graphes euclidiens. Ces problèmes d’optimisation NP-difficiles font intervenir des données réparties dans le plan et des structures élastiques représentées par des graphes qui doivent s’apparier aux données. Ils recouvrent des problèmes connus sous des appellations diverses telles que geometric k-means, elastic net, topographic mapping, elastic image matching. Ils permettent de modéliser par exemple le problème du voyageur de commerce euclidien, le problème du cycle médian, ainsi que des problèmes de mise en correspondance d’images. La contribution présentée est divisée en trois parties. Dans la première partie, nous présentons le modèle de matrice cellulaire qui partitionne les données et définit le niveau de granularité du calcul parallèle. Nous présentons une boucle générique de calcul parallèle qui modélise le principe des projections de graphes et de leur appariement. Dans la deuxième partie, nous appliquons le modèle de calcul parallèle aux algorithmes de k-means avec topologie dans le plan. Les algorithmes proposés sont appliqués au voyageur de commerce, à la génération de maillage structuré et à la segmentation d'image suivant le concept de superpixel. L’approche est nommée superpixel adaptive segmentation map (SPASM). Dans la troisième partie, nous proposons un algorithme de recherche locale parallèle, appelé distributed local search (DLS). La solution du problème résulte des opérations locales sur les structures et les données réparties dans le plan, incluant des évaluations, des recherches de voisinage, et des mouvements structurés. L’algorithme est appliqué à des problèmes d’appariement de graphe tels que le stéréo-matching et le problème de flot optique. / In this thesis, we propose a parallel computing model, called cellular matrix, to provide answers to problematic issues of parallel computation when applied to Euclidean graph matching problems. These NP-hard optimization problems involve data distributed in the plane and elastic structures represented by graphs that must match the data. They include problems known under various names, such as geometric k-means, elastic net, topographic mapping, and elastic image matching. The Euclidean traveling salesman problem (TSP), the median cycle problem, and the image matching problem are also examples that can be modeled by graph matching. The contribution presented is divided into three parts. In the first part, we present the cellular matrix model that partitions data and defines the level of granularity of parallel computation. We present a generic loop for parallel computations, and this loop models the projection between graphs and their matching. In the second part, we apply the parallel computing model to k-means algorithms in the plane extended with topology. The proposed algorithms are applied to the TSP, structured mesh generation, and image segmentation following the concept of superpixel. The approach is called superpixel adaptive segmentation map (SPASM). In the third part, we propose a parallel local search algorithm, called distributed local search (DLS). The solution results from the many local operations, including local evaluation, neighborhood search, and structured move, performed on the distributed data in the plane. The algorithm is applied to Euclidean graph matching problems including stereo matching and optical flow.

Un très grand nombre de problèmes combinatoires appartient à la famille des problèmes de satisfaction de contraintes (Constraint Satisfaction Problem ou CSP) : configuration, ordonnancement, affectation de ressources... Ces problèmes partagent une description commune qui autorise en général une modélisation claire et intuitive. Dans cette thèse, nous avons proposé et étudié une nouvelle méthode de résolution hybride pour les CSPs. Nous avons nommé cette méthode Tabu-NG pour Tabu Search based on NoGood. Le nom est un peu réducteur car il s'agit d'une hybridation d'algorithme de filtrage, de propagation de contraintes, de Recherche Tabou et de gestion de nogoods. La méthode a été appliquée sur deux types de problèmes. Le premier est l'affectation des fréquences (FAP) dans les réseaux de radiocommunications militaires, en particulier les problèmes proposés de 1993 (instances du projet européen CALMA) jusqu'à 2010 (instances d'un projet DGA). Le deuxième est le problème académique de k-coloration de graphes sur les instances DIMACS. La méthode a amélioré quelques meilleurs scores connus actuellement. Dans les deux problèmes nous avons traité des contraintes unaires et binaires, ainsi que des contraintes n-aires et de l'optimisation de fonction sous contraintes pour le FAP. Les principes de Tabu-NG sont généraux et elle peut s'appliquer sur d'autres CSP. Elle peut par ailleurs accueillir des heuristiques spécifiques aux problèmes, nous l'avons pratiqué sur les problèmes cités, et en ce sens nous pensons pouvoir qualifier la méthode de métaheuristique sans abuser de cette définition.