Nous adaptons une heuristique de recherche à voisinage variable pour traiter le problème du voyageur de commerce avec fenêtres de temps (TSPTW) lorsque l'objectif est la minimisation du temps d'arrivée au dépôt de destination. Nous utilisons des méthodes efficientes pour la vérification de la réalisabilité et de la rentabilité d'un mouvement. Nous explorons les voisinages dans des ordres permettant de réduire l'espace de recherche. La méthode résultante est compétitive avec l'état de l'art. Nous améliorons les meilleures solutions connues pour deux classes d'instances et nous fournissons les résultats de plusieurs instances du TSPTW pour la première fois. / We adapt a general variable neighborhood search heuristic to solve the traveling salesman problem with time windows (TSPTW) where the objective is to minimize the completion time. We use efficient methods to check the feasibility and the profitability of a movement. We use a specific order to reduce the search space while exploring the neighborhoods. The resulting method is competitive with the state-of-the-art. We improve the best known solutions for two classes of instances and provide the results of multiple instances of TSPTW for the first time.

Cette thèse traite d’une routine d’algèbre linéaire largement utilisée pour la résolution des systèmes li- néaires, il s’agit de la factorisation LU. Habituellement, pour calculer une telle décomposition, on utilise l’élimination de Gauss avec pivotage partiel (GEPP). La stabilité numérique de l’élimination de Gauss avec pivotage partiel est caractérisée par un facteur de croissance qui est reste assez petit en pratique. Toutefois, la version parallèle de cet algorithme ne permet pas d’atteindre les bornes inférieures qui ca- ractérisent le coût de communication pour un algorithme donné. En effet, la factorisation d’un bloc de colonnes constitue un goulot d’étranglement en termes de communication. Pour remédier à ce problème, Grigori et al [60] ont développé une factorisation LU qui minimise la communication(CALU) au prix de quelques calculs redondants. En théorie la borne supérieure du facteur de croissance de CALU est plus grande que celle de l’élimination de Gauss avec pivotage partiel, cependant CALU est stable en pratique. Pour améliorer la borne supérieure du facteur de croissance, nous étudions une nouvelle stra- tégie de pivotage utilisant la factorisation QR avec forte révélation de rang. Ainsi nous développons un nouvel algorithme pour la factorisation LU par blocs. La borne supérieure du facteur de croissance de cet algorithme est plus petite que celle de l’élimination de Gauss avec pivotage partiel. Cette stratégie de pivotage est ensuite combinée avec le pivotage basé sur un tournoi pour produire une factorisation LU qui minimise la communication et qui est plus stable que CALU. Pour les systèmes hiérarchiques, plusieurs niveaux de parallélisme sont disponibles. Cependant, aucune des méthodes précédemment ci- tées n’exploite pleinement ces ressources. Nous proposons et étudions alors deux algorithmes récursifs qui utilisent les mêmes principes que CALU mais qui sont plus appropriés pour des architectures à plu- sieurs niveaux de parallélisme. Pour analyser d’une façon précise et réaliste / This dissertation focuses on a widely used linear algebra kernel to solve linear systems, that is the LU decomposition. Usually, to perform such a computation one uses the Gaussian elimination with partial pivoting (GEPP). The backward stability of GEPP depends on a quantity which is referred to as the growth factor, it is known that in general GEPP leads to modest element growth in practice. However its parallel version does not attain the communication lower bounds. Indeed the panel factorization rep- resents a bottleneck in terms of communication. To overcome this communication bottleneck, Grigori et al [60] have developed a communication avoiding LU factorization (CALU), which is asymptotically optimal in terms of communication cost at the cost of some redundant computation. In theory, the upper bound of the growth factor is larger than that of Gaussian elimination with partial pivoting, however CALU is stable in practice. To improve the upper bound of the growth factor, we study a new pivoting strategy based on strong rank revealing QR factorization. Thus we develop a new block algorithm for the LU factorization. This algorithm has a smaller growth factor upper bound compared to Gaussian elimination with partial pivoting. The strong rank revealing pivoting is then combined with tournament pivoting strategy to produce a communication avoiding LU factorization that is more stable than CALU. For hierarchical systems, multiple levels of parallelism are available. However, none of the previously cited methods fully exploit these hierarchical systems. We propose and study two recursive algorithms based on the communication avoiding LU algorithm, which are more suitable for architectures with multiple levels of parallelism. For an accurate and realistic cost analysis of these hierarchical algo- rithms, we introduce a hierarchical parallel performance model that takes into account processor and network hierarchies. This analysis enables us to accurately predict the performance of the hierarchical LU factorization on an exascale platform.

L'analyse et la reconstruction automatique de scène urbaine 3D est un problème fondamental dans le domaine de la vision par ordinateur et du traitement numérique de la géométrie. Cette thèse présente des méthodologies pour résoudre le problème complexe de la reconstruction d'éléments urbains en 3D à partir de données aériennes Lidar ou bien de maillages générés par imagerie Multi-View Stereo (MVS). Nos approches génèrent une représentation précise et compacte sous la forme d'un maillage 3D comportant une sémantique de l'espace urbain. Deux étapes sont nécessaires ; une identification des différents éléments de la scène urbaine, et une modélisation des éléments sous la forme d'un maillage 3D. Le Chapitre 2 présente deux méthodes de classifications des éléments urbains en classes d'intérêts permettant d'obtenir une compréhension approfondie de la scène urbaine, et d'élaborer différentes stratégies de reconstruction suivant le type d'éléments urbains. Cette idée, consistant à insérer à la fois une information sémantique et géométrique dans les scènes urbaines, est présentée en détails et validée à travers des expériences. Le Chapitre 3 présente une approche pour détecter la 'Végétation' incluses dans des données Lidar reposant sur les processus ponctuels marqués, combinée avec une nouvelle méthode d'optimisation. Le Chapitre 4 décrit à la fois une approche de maillage 3D pour les 'Bâtiments' à partir de données Lidar et de données MVS. Des expériences sur des structures urbaines larges et complexes montrent les bonnes performances de nos systèmes. / Analysis and 3D reconstruction of urban scenes from physical measurements is a fundamental problem in computer vision and geometry processing. Within the last decades, an important demand arises for automatic methods generating urban scenes representations. This thesis investigates the design of pipelines for solving the complex problem of reconstructing 3D urban elements from either aerial Lidar data or Multi-View Stereo (MVS) meshes. Our approaches generate accurate and compact mesh representations enriched with urban-related semantic labeling.In urban scene reconstruction, two important steps are necessary: an identification of the different elements of the scenes, and a representation of these elements with 3D meshes. Chapter 2 presents two classification methods which yield to a segmentation of the scene into semantic classes of interests. The beneath is twofold. First, this brings awareness of the scene for better understanding. Second, deferent reconstruction strategies are adopted for each type of urban elements. Our idea of inserting both semantical and structural information within urban scenes is discussed and validated through experiments. In Chapter 3, a top-down approach to detect 'Vegetation' elements from Lidar data is proposed using Marked Point Processes and a novel optimization method. In Chapter 4, bottom-up approaches are presented reconstructing 'Building' elements from Lidar data and from MVS meshes. Experiments on complex urban structures illustrate the robustness and scalability of our systems.

Dans cette thèse nous présentons une étude des pertes de puissance en haute fréquence dans les rotors des machines synchrones à aimants permanent. Dans le cas des champs harmoniques temporels au rotor, nous avons montré par calcul éléments finis en 3D que la règle de segmentation des aimants présente une anomalie. Par conséquent, nous avons développé une étude sur l’efficacité de la segmentation à deux dimensions des aimants permanents, avec l’optimisation de la de segmentation des aimants afin de minimiser les pertes par courants de Foucault. Un simple critère est proposé mettant en évidence l’influence de l’effet de peau dans le calcul des pertes à haute fréquence. En deuxième lieu nous avons étudié les pertes rotoriques dues à la modification du champ fondamental par la denture statorique, Dans ce but nous avons proposé un modèle analytique représentant cette modification par un champ homogène dans une maquette 2D/3D. Ce modèle met en évidence l’influence des paramètres géométriques de la machine sur les pertes de puissance dans le rotor. Il était validé par calcul en éléments finis dans une couche mince. Le modèle analytique a donné les résultats acceptables en absence de l’effet de peau dans le cas des aimants longs. Par contre il reste à améliorer pour le calcul de pertes par denture dans les tôles du rotor. / In this thesis we present a study of high frequency rotor power losses in permanent magnet synchronous machines. In case of time harmonic fields we have shown by an analysis and confirmed by 3D finite element calculation an anomaly of the segmentation rule of the magnet. Consequently, we have proposed algorithms of optimization of the magnet segmentation aiming the minimization of eddy current losses, with a simple criterion on influence of the skin effect in losses calculation in high frequency. In the second part of the theses we have analyzed the rotor power losses dues to the stator slot harmonics. In case of homogeneous field we have proposed an analytical formulation taking into account machine’s geometrical parameters. We have then tested this model with aid of the finite element calculation. The analytical model gives acceptable results in absence of the skin effect in long magnets, but its application in laminated steels hasn’t proved successful.

Sont étudiés: 1) l'algorithme s.g.g.p. Pour la résolution d'un programme linéaire général; 2) la méthode de pivotage de Lemke, la methode du gradient conjugue conditionnel et la methode de l'inverse partiel pour la résolution des programmes quadratiques convexes; 3) les méthodes d'approximation extérieure et les méthodes de coupes planes et les méthodes de région de confiance pour l'optimisation non convexe.

L'étude et l'introduction de nouveaux systèmes dynamiques<br /> de type gradient sont l'objet central de cette thèse. Le<br /> caractère dissipatif de telles dynamiques est au coeur de<br /> nombreux domaines en mathématiques : optimisation,<br /> mécanique, équations d'évolutions en dimension infinie.<br /><br />Dans une première partie, les champs de gradients (ou de sous-différentiels<br /> de fonction convexe) sont contrôlés à l'aide d'opérateurs-barrières. <br />La motivation essentielle est d'obtenir<br /> des méthodes intérieures de descente en vue d'optimiser<br /> une fonction sous des contraintes convexes. Le cadre<br /> d'étude proposé permet d'unifier dans un même formalisme de nombreuses<br /> méthodes continues : gradient projeté, plus grande pente riemannienne,<br /> méthode continue de Newton... Parmi les conséquences de <br />la généralisation proposée, on peut, par exemple, évoquer des <br /> résultats abstraits de viabilité et de convergence globale. Toujours <br />dans cette <br />perspective, les fonctions de Legendre jouent un rôle crucial~:<br /> elles permettent d'une part de donner lieu à des structures<br /> riemanniennes possédant de nombreuses propriétés - parmi lesquelles une<br /> propriété d'intégration caractéristique remarquable -, et d'autre part, <br /> elles fournissent en dimension infinie un cadre intéressant<br /> pour l'étude de certaines équations d'évolution de type<br /> parabolique.<br /><br />La deuxième partie est consacrée à l'étude de systèmes<br /> dynamiques du second ordre en temps avec une dissipation géométrique<br /> de type hessien. Outre leur intérêt en optimisation<br /> et leurs liens avec les méthodes de type Newton, ces systèmes<br /> sont d'une grande souplesse et permettent d'approcher certains <br />phénomènes non-lisses en mécanique unilatérale. En guise d'application,<br /> il est en effet prouvé que les systèmes considérés permettent <br />d'obtenir à la limite des dynamiques <br />satisfaisant des lois de chocs inélastiques. Les<br /> perspectives de cette étude ouvrent en particulier la voie à une approche <br />alternative de certains systèmes d'inégalités variationnelles de type <br />hyperbolique.<br /><br /><br />L'une des préoccupations majeures de cette thèse est la question<br /> de la convergence des orbites des systèmes étudiés. Dans le <br /> cadre de la minimisation convexe, quasi-convexe, ou analytique, de nombreux<br /> résultats sont proposés : convergence globale, , <br />vitesse de convergence, contrôle asymptotique, attractivité des <br /> minima sous contraintes en dimension infinie.

This thesis concerns the mathematical modelling of phase transformations with a special emphasis on martensitic phase transformations and their application to the modelling of steels. In Chapter 1, we develop a framework that determines the optimal transformation strain between any two Bravais lattices and use it to give a rigorous proof of a conjecture by E.C. Bain in 1924 on the optimality of the so-called Bain strain. In Chapter 2, we review the Ball-James model and related concepts. We present some simplification of existing results. In Chapter 3, we pose a conjecture for the explicit form of the quasiconvex hull of the three tetragonal wells, known as the three-well problem. We present a new approach to finding inner and outer bounds. In Chapter 4, we focus on highly compatible, so called self-accommodating, martensitic structures and present new results on their fine properties such as estimates on their minimum complexity and bounds on the relative proportion of each martensitic variant in them. In Chapter 5, we investigate the contrary situation when self-accommodating microstructures do not exist. We determine, whether in this situation, it is still energetically favourable to nucleate martensite within austenite. By constructing different types of inclusions, we find that the optimal shape of an inclusion is flat and thin which is in agreement with experimental observation. In Chapter 6, we introduce a mechanism that identifies transformation strains with orientation relationships. This mechanism allows us to develop a simpler, strain-based approach to phase transformation models in steels. One novelty of this approach is the derivation of an explicit dependence of the orientation relationships on the ratio of tetragonality of the product phase. In Chapter 7, we establish a correspondence between common phenomenological models for steels and the Ball-James model. This correspondence is then used to develop a new theory for the (5 5 7) lath transformation in low-carbon steels. Compared to existing theories, this new approach requires a significantly smaller number of input parameters. Furthermore, it predicts a microstructure morphology which differs from what is conventionally believed.

Dans ce projet, nous étudions la reconstruction de milieux terrestres souterrains.L’imagerie sismique est traitée avec un problème de minimisation itérative àgrande échelle, et nous utilisons la méthode de l’inversion des formes d’ondes(Full Waveform Inversion, FWI method). La reconstruction est basée sur desmesures d’ondes sismiques, car ces ondes sont caractérisées par le milieu danslequel elles se propagent. Tout d’abord, nous présentons les méthodesnumériques qui sont nécessaires pour prendre en compte l’hétérogénéité etl’anisotropie de la Terre. Ici, nous travaillons avec les solutions harmoniques deséquations des ondes, donc dans le domaine fréquentiel. Nous détaillons leséquations et l’approche numérique mises en place pour résoudre le problèmed’onde.Le problème inverse est établi afin de reconstruire les propriétés du milieu. Ils’agit d’un problème non-linéaire et mal posé, pour lequel nous disposons de peude données. Cependant, nous pouvons montrer une stabilité de type Lipschitzpour le problème inverse associé avec l’équation de Helmholtz, en considérantdes modèles représentés par des constantes par morceaux. Nous explicitons laborne inférieure et supérieure pour la constante de stabilité, qui nous permetd’obtenir une caractérisation de la stabilité en fonction de la fréquence et del’échelle. Nous revoyons ensuite le problème de minimisation associé à lareconstruction en sismique. La méthode de Newton apparaît comme naturelle,mais peut être difficilement accessible, dû au coup de calcul de la Hessienne.Nous présentons une comparaison des méthodes pour proposer un compromisentre temps de calcul et précision. Nous étudions la convergence de l’algorithme,en fonction de la géométrie du sous-sol, la fréquence et la paramétrisation. Celanous permet en particulier de quantifier la progression en fréquence, en estimantla taille du rayon de convergence de l’espace des solutions admissibles.A partir de l’étude de la stabilité et de la convergence, l’algorithme deminimisation itérative est conduit en faisant progresser la fréquence et l’échellesimultanément. Nous présentons des exemples en deux et trois dimensions, etillustrons l’incorporation d’atténuation et la considération de milieux anisotropes.Finalement, nous étudions le cas de reconstruction avec accès aux données deCauchy, motivé par les dual sensors développés en sismique. Cela nous permetde définir une nouvelle fonction coût, qui permet de prometteuses perspectivesavec un besoin minimal quant aux informations sur l’acquisition. / In this project, we investigate the recovery of subsurface Earth parameters. Weconsider the seismic imaging as a large scale iterative minimization problem, anddeploy the Full Waveform Inversion (FWI) method, for which several aspects mustbe treated. The reconstruction is based on the wave equations because thecharacteristics of the measurements indicate the nature of the medium in whichthe waves propagate. First, the natural heterogeneity and anisotropy of the Earthrequire numerical methods that are adapted and efficient to solve the wavepropagation problem. In this study, we have decided to work with the harmonicformulation, i.e., in the frequency domain. Therefore, we detail the mathematicalequations involved and the numerical discretization used to solve the waveequations in large scale situations.The inverse problem is then established in order to frame the seismic imaging. Itis a nonlinear and ill-posed inverse problem by nature, due to the limitedavailable data, and the complexity of the subsurface characterization. However,we obtain a conditional Lipschitz-type stability in the case of piecewise constantmodel representation. We derive the lower and upper bound for the underlyingstability constant, which allows us to quantify the stability with frequency andscale. It is of great use for the underlying optimization algorithm involved to solvethe seismic problem. We review the foundations of iterative optimizationtechniques and provide the different methods that we have used in this project.The Newton method, due to the numerical cost of inverting the Hessian, may notalways be accessible. We propose some comparisons to identify the benefits ofusing the Hessian, in order to study what would be an appropriate procedureregarding the accuracy and time. We study the convergence of the iterativeminimization method, depending on different aspects such as the geometry ofthe subsurface, the frequency, and the parametrization. In particular, we quantifythe frequency progression, from the point of view of optimization, by showinghow the size of the basin of attraction evolves with frequency. Following the convergence and stability analysis of the problem, the iterativeminimization algorithm is conducted via a multi-level scheme where frequencyand scale progress simultaneously. We perform a collection of experiments,including acoustic and elastic media, in two and three dimensions. Theperspectives of attenuation and anisotropic reconstructions are also introduced.Finally, we study the case of Cauchy data, motivated by the dual sensors devicesthat are developed in the geophysical industry. We derive a novel cost function,which arises from the stability analysis of the problem. It allows elegantperspectives where no prior information on the acquisition set is required.

Waste minimisation is implemented worldwide and has become an urgent priority in South Africa as evidenced in the promulgated National Environmental Management Waste Act (2008). The most common waste disposal method in South Africa is by landfill, which is unacceptable. Local municipalities have made little progress towards waste minimisation. The aim of this study was to present a solution to waste minimisation for the City of Tshwane Metropolitan Municipality (CTMM) by determining the feasibility of establishing composting facilities on landfill sites. One third of all municipal waste consists of green waste, which is compostable and can be converted on landfill sites. Nine municipal landfill sites were screened. The four most feasible sites were evaluated further by applying identified parameters that address physical, social and operational requirements. It is a possible to establish composting facilities on all four sites investigated, with Hatherley ranking as the most suited. The findings of this study clearly provided the basic parameters and requirements for constructing a composting facility and practical procedures applicable within a South African context. The evaluation method used can be applied as a model to evaluate similar studies in other municipalities to aid them in the decision-making process for waste minimisation. / Environmental Management / M.A. (Environmental Management)

With the exception of horse racing, any form of gambling was criminalised in South Africa until the dawn of constitutional democracy in 1994. In the same year, the Lotteries and Gambling Board Act, 1993, came into force decriminalising, amongst others, casinos and gambling games within the Republic. This Act has since been repealed and gambling is governed by the National Gambling Act, 2004, as well as by provincial gambling laws. Interactive / online gambling is illegal pending authorisation by a national legislation. Such legislation, the National Gambling Amendment Act, 2008, seeking to regulate interactive gambling awaits proclamation of the date of its commencement by the President. The National Gambling Policy, 2016, dashes any hope of regulation of interactive gambling, however, as it seeks to embargo the introduction of (new) forms of gambling, including but not limited to interactive gambling. The scourge of problem gambling and the protection of traditional forms of gambling, that is, casinos, are the main reasons for advocating for the continued prohibition of interactive gambling. Problem gambling is not unique to interactive gambling, but affects all modes of gambling. South Africa is among countries with a high rate of problem gambling. It is feared that interactive gambling will exacerbate the scourge of problem gambling as gamblers with access to the internet will now have unlimited gambling opportunities around the clock. On the other hand, interactive gambling offers practical solutions to the implementation of harm minimisation strategies to deal with problem gambling such as limitations on gambling deposits, losses and time. Prohibition of interactive gambling is difficult to enforce and deprives the country of an opportunity to control, through licensing, this mode of gambling and possible benefit from taxation and licensing fees. It further exposes gamblers – who despite prohibition choose this mode of gambling – to unregulated and illegal gambling websites. This thesis attempts to provide safeguards for regulation of interactive gambling and to embrace the benefits of the technological development that makes interactive gambling a reality. The United Kingdom (UK) is a prime example of a country that has successfully legalised and licensed interactive gambling in its jurisdiction. / Criminal and Procedural Law / LL. D.