The quadratic assignment problem (QAP) is known to be one of the most computationally difficult combinatorial problems. Optimally solvable instances of the QAP remain of size n ≤ 40 with heuristics used to solve instances in the range 40 ≤ n ≤ 256. In this thesis we develop a local optimization algorithm called GradSwaps (GS). GS uses the first-order Taylor approximation (FOA) to efficiently determine improving swaps in the solution. We use GS to locally optimize instances of the QAP of size 1000 ≤ n ≤ 70000 where the data matrices are given in factored form, enabling efficient computations. We give theoretical background and justification for using the FOA and bound the error inherent in the approximation. A strategy for extending GS to larger scale QAPs using blocks of indices is described in detail. Three novel large-scale applications of the QAP are developed. First, a strategy for data visualization using an extreme learning machine (ELM) where the quality of the visualization is measured in the original data space instead of the projected space. Second, a version of the traveling salesperson problem (TSP) with the squared Euclidean distance metric; this distance metric allows the factorization of the data matrix, a key component for using GS. Third, a method for generating random data with designated distribution and correlation to an accuracy surpassing traditional techniques.

The problem of selecting the connectivity of a triangulation in order to minimize a given cost function is studied. This problem is of great importance for applications, such as generating triangle mesh models of images and other bivariate functions. In early work, a well-known method named the local optimization procedure (LOP) was proposed by Lawson for solving the triangulation optimization problem. More recently, Yu et al. proposed a variant of the LOP called the LOP with lookahead (LLOP), which has proven to be more effective than the LOP. Unfortunately, each of the LOP and LLOP can only guarantee to yield triangulations that satisfy a weak optimality condition for most cost functions. That is, the triangulation optimized by the LOP or LLOP is only guaranteed to be such that no single edge flip can reduce the triangulation cost. In this thesis, a new optimality criterion named n-flip optimality is proposed, which has proven to be a useful tool for analyzing the optimality property. We propose a more general framework called the modified LOP (MLOP), with several free parameters, that can be used to solve the triangulation-cost optimization problem. By carefully selecting the free parameters, two MLOP-based methods called the MLOPB(L,M) and MLOPC(L) are derived from this framework. According to the optimality property introduced in the thesis, we have proven our proposed methods can satisfy a stronger optimality condition than the LOP and LLOP. That is, the triangulation produced by our MLOP-based methods cannot have their cost reduced by any single edge flip or any two edge flips. Due to satisfying this stronger optimality condition, our proposed methods tend to yield triangulations of significantly lower cost than the LOP and LLOP methods. In order to evaluate the performance of our MLOP-based methods, they are compared with two other competing approaches, namely the LOP and LLOP. Experimental results show that the MLOPB and MLOPC methods consistently yield triangulations of much lower cost than the LOP and LLOP. More specifically, our MLOPB and MLOPC methods yield triangulations with an overall median cost reduction of 16.36% and 16.62%, respectively, relative to the LOP, while the LLOP can only yield triangulations with an overall median cost reduction of 11.49% relative to the LOP. Moreover, our proposed methods MLOPB(2,i) and MLOPA(i) are shown to produce even better results if the parameter i is increased at the expense of increased computation time. / Graduate

A connected dominating set D is a set of vertices of a graph G=(V,E) such that every vertex in V-D is adjacent to at least one vertex in D and the subgraph induced by the set D is connected. The connected domination number is the minimum of the cardinalities of the connected dominating sets of G. The problem of finding a minimum connected dominating set D is known to be NP-hard. Many polynomial time algorithms that achieve some approximation factors have been provided earlier in finding a minimum connected dominating set. In this work, we present a survey on known properties of graph domination as well as some approximation algorithms. We implemented some of these algorithms and tested them with random graphs and compared their performance in finding a minimum connected dominating set D.

A global/local framework for multidisciplinary optimization of generalized aircraft wing structure has been developed. The concept of curvilinear stiffening members (spars, ribs and stiffeners) has been applied in the optimization of a wing structure. A global wing optimization framework EBF3WingOpt, which integrates the static aeroelastic, flutter and buckling analysis, has been implemented for exploiting the optimal design at the wing level. The wing internal structure is optimized using curvilinear spars and ribs (SpaRibs). A two-step optimization approach, which consists of topology optimization with shape design variables and size optimization with thickness design variables, is implemented in EBF3WingOpt. A local panel optimization EBF3PanelOpt, which includes stress and buckling evaluation criteria, is performed to optimize the local panels bordered by spars and ribs for further structural weight saving. The local panel model is extracted from the global finite element model. The boundary conditions are defined on the edges of local panels using the displacement fields obtained from the global model analysis. The local panels are optimized to satisfy stress and buckling constraints. Stiffened panel with curvilinear stiffeners is implemented in EBF3PanelOpt to improve the buckling resistance of the local panels. The optimization of stiffened panels has been studied and integrated in the local panel optimization. EBF3WingOpt has been applied for the optimization of the wing structure of the Boeing N+2 supersonic transport wing and NASA common research model (CRM). The optimization results have shown the advantage of curvilinear spars and ribs concept. The local panel optimization EBF3PanelOpt is performed for the NASA CRM wing. The global-local optimization framework EBF3GLWingOpt, which incorporates global wing optimization module EBF3WingOpt and local panel optimization module EBF3PanelOpt, is developed using MATLAB and Python programming to integrate several commercial software: MSC.PATRAN for pre and post processing, MSC.NASTRAN for finite element analysis. An approximate optimization method is developed for the stiffened panel optimization so as to reduce the computational cost. The integrated global-local optimization approach has been applied to subsonic NASA common research model (CRM) wing which proves the methodology's application scaling with medium fidelity FEM analysis. Both the global wing design variables and local panel design variables are optimized to minimize the wing weight at an acceptable computational cost. / Ph. D.

Motion planning is defined as the problem of computing a feasible trajectory for an agent to follow. It is a well-studied problem with applications in fields such as robotics, control theory and artificial intelligence. In the last decade there has been an increased interest in algorithms for motion planning under uncertainty where the agent does not know the state of the environment due to, e.g. motion and sensing uncertainties. One approach is to generate an initial feasible trajectory using for example an algorithm such as RRT* and then improve that initial trajectory using local optimization. This thesis proposes a new modification of the RRT* algorithm that can be used to generate initial paths from which initial trajectories for the local optimization step can be generated. Unlike standard RRT*, the modified RRT* generates multiple paths at the same time, all belonging to different families of solutions (homotopy classes). Algorithms for motion planning under uncertainty that rely on local optimization of trajectories can use trajectories generated from these paths as initial solutions. The modified RRT* is implemented and its performance with respect to computation time and number of paths found is evaluated on simple scenarios. The evaluations show that the modified RRT* successfully computes solutions in multiple homotopy classes. Two methods for motion planning under uncertainty, Trajectory-optimized LQG (T-LQG), and a belief space variant of iterative LQG (iLQG) are implemented and combined with the modified RRT*. The performance with respect to cost function improvement, computation time and success rate when following the optimized trajectories for the two methods are evaluated in a simulation study. The results from the simulation studies show that it is advantageous to generate multiple initial trajectories. Some initial trajectories, due to for example passing through narrow passages or through areas with high uncertainties, can only be slightly improved by trajectory optimization or results in trajectories that are hard to follow or with a high collision risk. If multiple initial trajectories are generated the probability is higher that at least one of them will result in an optimized trajectory that is easy to follow, with lower uncertainty and lower collision risk than the initial trajectory. The results also show that iLQG is much more computationally expensive than T-LQG, but that it is better at computing control policies to follow the optimized trajectories.

To stay competitive internationally, the Swedish forestry sector must increase its productivity by 2 to 3% annually. There are a variety of ways in which productivity can be increased. One option is to develop remote-controlled or unmanned machines, thus reducing the need for operator intervention. Another option—and one that could be achieved sooner than full automation—would be to make some functions semi-automatic. Semi-automatic operation of the knuckle boom and felling head in particular would create “mini-breaks” for the operators, thereby reducing mental and physiological stress. It would also reduce training time and increase the productivity of a large proportion of operators. The objective of this thesis work has been to develop and evaluate algorithms for simplified boom control on forest machines. Algorithms for so called boom tip control, as well as automatic boom functions have been introduced. The algorithms solve the inverse kinematics of kinematically redundant knuckle booms while maximizing lifting capacity. The boom tip control was evaluated – first by means of a kinematic simulation and then in a dynamic forest machine simulator. The results show that boom tip control is an easier system to learn in comparison to conventional control, leading to savings in production due to shorter learning times and operators being able to reach full production sooner. Boom tip control also creates less mental strain than conventional control, which in the long run will reduce mental stress on operators of forest machines. The maximum lifting capacity algorithm was then developed further to enable TCP path-tracking, which was also implemented and evaluated in the simulator. An evaluation of the fidelity of the dynamic forest machine simulator was performed to ensure validity of the results achieved with the simplified boom control. The results from the study show that there is good fidelity between the forest machine simulator and a real forest machine, and that the results from simulations are reliable. It is also concluded that the simulator was a useful research tool for the studies performed in the context of this thesis work. The thesis had two overall objectives. The first was to provide the industry and forestry sector with usable and verified ideas and results in the area of automation. This has been accomplished with the implementation of a simplified boom control and semi-automation on a forwarder in a recently started joint venture between a hydraulic manufacturer, a forest machine manufacturer and a forest enterprise. The second objective was to strengthen the research and development links between the forestry sector and technical university research. This has been accomplished through the thesis work itself and by a number of courses, projects and Masters theses over the last three years. About 150 students in total have been studying forest machine technology in one way or the other. / QC 20100729

Le radar géologique est une méthode d'investigation géophysique basée sur la propagation d'ondes électromagnétiques dans le sous-sol. Avec des fréquences allant de 5 MHz à quelques GHz et une forte sensibilité aux propriétés électriques, le géoradar fournit des images de réflectivité dans des contextes et à des échelles très variés : génie civil, géologie, hydrogéologie, glaciologie, archéologie. Cependant, dans certains cas, la compréhension fine des processus étudiés dans la subsurface nécessite une quantification des paramètres physiques du sous-sol. Dans ce but, l'inversion des formes d'ondes complètes, méthode initialement développée pour l'exploration sismique qui exploite l'ensemble des signaux enregistrés, pourrait s'avérer efficace. Dans cette thèse, je propose ainsi des développements méthodologiques par une approche d'inversion multiparamètres (permittivité diélectrique et conductivité), pour des configurations en transmission, en deux dimensions.Ces développements sont ensuite appliqués à un jeu de données réelles acquises entre forages.Dans une première partie, je présente tout d'abord la méthode numérique utilisée pour modéliser la propagation des ondes électromagnétiques dans un milieu 2D hétérogène, élément indispensable pour mener à bien le processus d'imagerie. Ensuite, j’introduis puis étudie le potentiel des méthodes d’optimisation locale standards (gradient conjugué non linéaire, l-BFGS, Newton tronqué dans ses versions Gauss-Newton et Exact-Newton) pour découpler la permittivité diélectrique et la conductivité électrique. Je montre notamment qu’un découplage effectif n’est possible qu’avec un modèle initial suffisamment précis et la méthode la plus sophistiquée (Newton tronqué). Comme dans le cas général, ce modèle initial n’est pas disponible, il s’avère nécessaire d'introduire un facteur d'échelle qui répartit le poids relatif de chaque classe de paramètres dans l'inversion. Dans un milieu réaliste avec une acquisition entre puits, je montre que les différentes méthodes d'optimisation donnent des résultats similaires en matière de découplage de paramètres. C'est finalement la méthode l-BFGS qui est retenue pour l'application aux données réelles, en raison de coûts de calcul plus faibles.Dans une deuxième partie, j'applique cette méthodologie à des données réelles acquises entre deux forages localisés dans des formations carbonatées, à Rustrel (France, 84). Cette inversion est réalisée en parallèle d'une approche synthétique à l'aide d'un modèle représentatif du site étudié et des configurations d'acquisition similaires. Ceci permet de pouvoir comprendre, contrôler et valider les observations et conclusions obtenues sur les données réelles. Cette démarche montre que la reconstruction de la permittivité est très robuste. A contrario, l'estimation de la conductivité souffre de deux couplages majeurs, avec la permittivité diélectrique, d'une part, et avec l'amplitude de la source estimée, d'autre part. Les résultats obtenus sont confrontés avec succès à des données indépendantes (géophysique depuis la surface, analyse sur échantillons de roche), et permet de bénéficier d'une image haute-résolution des formations géologiques. Enfin, une analyse 3D confirme que les structures 3D à fort contraste de propriétés, telles que la galerie enfouie sur notre site, nécessiteraient une approche de modélisation 3D, notamment pour mieux expliquer les amplitudes observées. / Ground Penetrating Radar (GPR) is a geophysical investigation method based on electromagnetic waves propagation in the underground. With frequencies ranging from 5 MHz to a few GHz and a high sensitivity to electrical properties, GPR provides reflectivity images in a wide variety of contexts and scales: civil engineering, geology, hydrogeology, glaciology, archeology. However, in some cases, a better understanding of some subsurface processes requires a quantification of the physical parameters of the subsoil. For this purpose, inversion of full waveforms, a method initially developed for seismic exploration that exploits all the recorded signals, could prove effective. In this thesis, I propose methodological developments using a multiparameter inversion approach (dielectric permittivity and conductivity), for two-dimensional transmission configurations. These developments are then applied to a real data set acquired between boreholes.In a first part, I present the numerical method used to model the propagation of electromagnetic waves in a heterogeneous 2D environment, a much-needed element to carry out the process of imaging. Then, I introduce and study the potential of standard local optimization methods (nonlinear conjugate gradient, l-BFGS, Newton truncated in its Gauss-Newton and Exact-Newton versions) to fight the trade-off effects related to the dielectric permittivity and to the electrical conductivity. In particular, I show that effective decoupling is possible only with a sufficiently accurate initial model and the most sophisticated method (truncated Newton). As in the general case, this initial model is not available, it is necessary to introduce a scaling factor which distributes the relative weight of each parameter class in the inversion. In a realistic medium and for a cross-hole acquisition configuration, I show that the different optimization methods give similar results in terms of parameters decoupling. It is eventually the l-BFGS method that is used for the application to the real data, because of lower computation costs.In a second part, I applied the developed Full waveform inversion methodology to a set of real data acquired between two boreholes located in carbonate formations, in Rustrel (France, 84). This inversion is carried out together with a synthetic approach using a model representative of the studied site and with a similar acquisition configuration. This approach enables us to monitor and validate the observations and conclusions derived from data inversion. It shows that reconstruction of dielectrical permittivity is very robust. Conversely, conductivity estimation suffers from two major couplings: the permittivity and the amplitude of the estimated source. The derived results are successfully compared with independent data (surface geophysics and rock analysis on plugs) and provides a high resolution image of the geological formation. On the other hand, a 3D analysis confirms that 3D structures presenting high properties contrasts, such as the buried gallery present in our site, would require a 3D approach, notably to better explain the observed amplitudes.

<p>The focus of this thesis is on numerical algorithms for efficient solution of QTL analysis problem in genetics.</p><p>Firstly, we consider QTL mapping problems where a standard least-squares model is used for computing the model fit. We develop optimization methods for the local problems in a hybrid global-local optimization scheme for determining the optimal set of QTL locations. Here, the local problems have constant bound constraints and may be non-convex and/or flat in one or more directions. We propose an enhanced quasi-Newton method and also implement several schemes for constrained optimization. The algorithms are adopted to the QTL optimization problems. We show that it is possible to use the new schemes to solve problems with up to 6 QTLs efficiently and accurately, and that the work is reduced with up to two orders magnitude compared to using only global optimization.</p><p>Secondly, we study numerical methods for QTL mapping where variance component estimation and a REML model is used. This results in a non-linear optimization problem for computing the model fit in each set of QTL locations. Here, we compare different optimization schemes and adopt them for the specifics of the problem. The results show that our version of the active set method is efficient and robust, which is not the case for methods used earlier. We also study the matrix operations performed inside the optimization loop, and develop more efficient algorithms for the REML computations. We develop a scheme for reducing the number of objective function evaluations, and we accelerate the computations of the derivatives of the log-likelihood by introducing an efficient scheme for computing the inverse of the variance-covariance matrix and other components of the derivatives of the log-likelihood.</p>

The focus of this thesis is on numerical algorithms for efficient solution of QTL analysis problem in genetics. Firstly, we consider QTL mapping problems where a standard least-squares model is used for computing the model fit. We develop optimization methods for the local problems in a hybrid global-local optimization scheme for determining the optimal set of QTL locations. Here, the local problems have constant bound constraints and may be non-convex and/or flat in one or more directions. We propose an enhanced quasi-Newton method and also implement several schemes for constrained optimization. The algorithms are adopted to the QTL optimization problems. We show that it is possible to use the new schemes to solve problems with up to 6 QTLs efficiently and accurately, and that the work is reduced with up to two orders magnitude compared to using only global optimization. Secondly, we study numerical methods for QTL mapping where variance component estimation and a REML model is used. This results in a non-linear optimization problem for computing the model fit in each set of QTL locations. Here, we compare different optimization schemes and adopt them for the specifics of the problem. The results show that our version of the active set method is efficient and robust, which is not the case for methods used earlier. We also study the matrix operations performed inside the optimization loop, and develop more efficient algorithms for the REML computations. We develop a scheme for reducing the number of objective function evaluations, and we accelerate the computations of the derivatives of the log-likelihood by introducing an efficient scheme for computing the inverse of the variance-covariance matrix and other components of the derivatives of the log-likelihood.

A city is considered as a complex system. It consists of numerous interactivesub-systems and is affected by diverse factors including governmental landpolicies, population growth, transportation infrastructure, and market behavior.Land use and transportation systems are considered as the two most importantsubsystems determining urban form and structure in the long term. Meanwhile,urban growth is one of the most important topics in urban studies, and its maindriving forces are population growth and transportation development. Modelingand simulation are believed to be powerful tools to explore the mechanisms ofurban evolution and provide planning support in growth management. The overall objective of the thesis is to analyze and model urban growth basedon the simulation of land-use changes and the modeling of road networkexpansion. Since most previous urban growth models apply fixed transportnetworks, the evolution of road networks was particularly modeled. Besides,urban growth modeling is an interdisciplinary field, so this thesis made bigefforts to integrate knowledge and methods from other scientific and technicalareas to advance geographical information science, especially the aspects ofnetwork analysis and modeling. A multi-agent system was applied to model urban growth in Toronto whenpopulation growth is considered as being the main driving factor of urbangrowth. Agents were adopted to simulate different types of interactiveindividuals who promote urban expansion. The multi-agent model with spatiotemporalallocation criterions was shown effectiveness in simulation. Then, anurban growth model for long-term simulation was developed by integratingland-use development with procedural road network modeling. The dynamicidealized traffic flow estimated by the space syntax metric was not only used forselecting major roads, but also for calculating accessibility in land-usesimulation. The model was applied in the city centre of Stockholm andconfirmed the reciprocal influence between land use and street network duringthe long-term growth. To further study network growth modeling, a novel weighted network model,involving nonlinear growth and neighboring connections, was built from theperspective of promising complex networks. Both mathematical analysis andnumerical simulation were examined in the evolution process, and the effects ofneighboring connections were particular investigated to study the preferentialattachment mechanisms in the evolution. Since road network is a weightedplanar graph, the growth model for urban street networks was subsequentlymodeled. It succeeded in reproducing diverse patterns and each pattern wasexamined by a series of measures. The similarity between the properties of derived patterns and empirical studies implies that there is a universal growthmechanism in the evolution of urban morphology. To better understand the complicated relationship between land use and roadnetwork, centrality indices from different aspects were fully analyzed in a casestudy over Stockholm. The correlation coefficients between different land-usetypes and road network centralities suggest that various centrality indices,reflecting human activities in different ways, can capture land development andconsequently influence urban structure. The strength of this thesis lies in its interdisciplinary approaches to analyze andmodel urban growth. The integration of ‘bottom-up’ land-use simulation androad network growth model in urban growth simulation is the major contribution.The road network growth model in terms of complex network science is anothercontribution to advance spatial network modeling within the field of GIScience.The works in this thesis vary from a novel theoretical weighted network modelto the particular models of land use, urban street network and hybrid urbangrowth, and to the specific applications and statistical analysis in real cases.These models help to improve our understanding of urban growth phenomenaand urban morphological evolution through long-term simulations. Thesimulation results can further support urban planning and growth management.The study of hybrid models integrating methods and techniques frommultidisciplinary fields has attracted a lot attention and still needs constantefforts in near future. / <p>QC 20130514</p>