In this paper, we study the stochastic transportation-inventory network design problem involving one supplier and multiple retailers. Each retailer faces some uncertain demand. Due to this uncertainty, some amount of safety stock must be maintained to achieve suitable service levels. However, risk-pooling benefits may be achieved by allowing some retailers to serve as distribution centers (and therefore inventory storage locations) for other retailers. The problem is to determine which retailers should serve as distribution centers and how to allocate the other retailers to the distribution centers. Shen et al. (2000) and Daskin et al. (2001) formulated this problem as a set-covering integer-programming model. The pricing subproblem that arises from the column generation algorithm gives rise to a new class of submodular function minimization problem. They only provided efficient algorithms for two special cases, and assort to ellipsoid method to solve the general pricing problem, which run in O(n⁷ log(n)) time, where n is the number of retailers. In this paper, we show that by exploiting the special structures of the pricing problem, we can solve it in O(n² log n) time. Our approach implicitly utilizes the fact that the set of all lines in 2-D plane has low VC-dimension. Computational results show that moderate size transportation-inventory network design problem can be solved efficiently via this approach. / Singapore-MIT Alliance (SMA)

In this master thesis a visual odometry system is implemented and explained. Visual odometry is a technique, which could be used on autonomous vehicles to determine its current position and is preferably used indoors when GPS is notworking. The only input to the system are the images from a stereo camera and the output is the current location given in relative position. In the C++ implementation, image features are found and matched between the stereo images and the previous stereo pair, which gives a range of 150-250 verified feature matchings. The image coordinates are triangulated into a 3D-point cloud. The distance between two subsequent point clouds is minimized with respect to rigid transformations, which gives the motion described with six parameters, three for the translation and three for the rotation. Noise in the image coordinates gives reconstruction errors which makes the motion estimation very sensitive. The results from six experiments show that the weakness of the system is the ability to distinguish rotations from translations. However, if the system has additional knowledge of how it is moving, the minimization can be done with only three parameters and the system can estimate its position with less than 5 % error.

Let F be a free group of finite rank. Given words u, v ∈ F, J.H.C. Whitehead solved the decision problem of finding an automorphism φ ∈ Aut(F), carrying u to v. He used topological methods to produce an algorithm. Higgins and Lyndon gave a very concise proof of the problem based on the works of Rapaport. We provide a detailed account of Higgins and Lyndon’s proof of the peak reduction lemma and the restricted version of Whitehead’s theorem, for cyclic words as well as for sets of cyclic words, with a full explanation of each step. Then, we give an inductive proof of Whitehead’s minimization theorem and describe Whitehead’s decision algorithm. Noticing that Higgins and Lyndon’s work is limited to the cyclic words, we extend their proofs to ordinary words and sets of ordinary words. In the last chapter, we mention an example given by Whitehead to show that the decision problem for finitely generated subgroups is more difficult and outline an approach due to Gersten to overcome this difficulty. We also give an extensive literature survey of Whitehead’s algorithm / Thesis / Master of Science (MSc)

Liver perfusion can be modelled by Darcy's flow in multiple connected com- partments. The first part of the present thesis shows in detail the existence of a solution to the multi-compartmental model. The flow in each compartment in this model is characterized by a permeability tensor, which is obtained from the geometry of liver vasculature. It turns out that this tensor might be singular, which potentially causes solvability problems. The second part deals with this abnormality in one compartment. By using the theory of degenerate Sobolev spaces, an appropriate weak formulation is defined. Analogues of Poincar'e and traces inequalities in this degenerate setting are proved, which also imply the existence of the weak solutions. In addition, this part justifies another possibil- ity how to deal with degenerate permeability, which is regularizing the tensor by adding a small isotropic permeability to it. In the third part, the aim is to find subdomains of autonomous perfusion with respect to the source positions. This is formulated as a minimization problem and several numerical results are presented. 1

This paper proposes and investigates a metaheuristic tabu search algorithm (TSA) that generates optimal or near optimal solutions sequences for the feedback length minimization problem (FLMP) associated to a design structure matrix (DSM). The FLMP is a non-linear combinatorial optimization problem, belonging to the NP-hard class, and therefore finding an exact optimal solution is very hard and time consuming, especially on medium and large problem instances. First, we introduce the subject and provide a review of the related literature and problem definitions. Using the tabu search method (TSM) paradigm, this paper presents a new tabu search algorithm that generates optimal or sub-optimal solutions for the feedback length minimization problem, using two different neighborhoods based on swaps of two activities and shifting an activity to a different position. Furthermore, this paper includes numerical results for analyzing the performance of the proposed TSA and for fixing the proper values of its parameters. Then we compare our results on benchmarked problems with those already published in the literature. We conclude that the proposed tabu search algorithm is very promising because it outperforms the existing methods, and because no other tabu search method for the FLMP is reported in the literature. The proposed tabu search algorithm applied to the process layer of the multidimensional design structure matrices proves to be a key optimization method for an optimal product development. / Ce mémoire présente un nouvel algorithme métaheuristique de recherche taboue pour trouver des solutions optimales ou sous-optimales au problème de minimisation de la longueur des dépendances d’une matrice de conception (FLMP). Ce problème comporte une fonction économique non-linéaire et il appartient à la classe NP-ardu. Il s’ensuit qu’il est très difficile à trouver une solution optimale exacte en temps réel pour les problèmes de taille moyenne ou grande. D’abord, on présente le problème et une revue de la littérature associée. Ensuite, on analyse le problème, et on présente les détails du nouvel algorithme de recherche taboue produisant des solutions au problème de réduction de l’effet de retour en utilisant deux voisinages différents, le premier basé sur l’échange des positions de deux activités ("swap"), et le second sur le déplacement d’une activité à une position différente ("shift"). Des résultats numériques permettent d’analyser le comportement de l’algorithme et de comparer les deux voisinages. La première étape consiste à déterminer de bonnes valeurs pour les paramètres en utilisant des problèmes générés aléatoirement. Ensuite nos résultats sont comparés avec ceux obtenus dans la littérature. On conclut que l’algorithme de recherche taboue proposé est très prometteur, car nos résultats sont meilleurs que ceux publiés dans la litérature. D’autant plus que la recherche taboue semble avoir été utilisée pour la première fois sur ce problème.

Les problèmes d’optimisation combinatoire sont généralement réputés NP-difficiles, donc il n’y a pas d’algorithmes efficaces pour les résoudre. Afin de trouver des solutions optimales locales ou réalisables, on utilise souvent des heuristiques ou des algorithmes approchés. Les dernières décennies ont vu naitre des méthodes approchées connues sous le nom de métaheuristiques, et qui permettent de trouver une solution approchées. Cette thèse propose de résoudre des problèmes d’optimisation déterministe et stochastique à l’aide de métaheuristiques. Nous avons particulièrement étudié la méthode de voisinage variable connue sous le nom de VNS. Nous avons choisi cet algorithme pour résoudre nos problèmes d’optimisation dans la mesure où VNS permet de trouver des solutions de bonne qualité dans un temps CPU raisonnable. Le premier problème que nous avons étudié dans le cadre de cette thèse est le problème déterministe de largeur de bande de matrices creuses. Il s’agit d’un problème combinatoire difficile, notre VNS a permis de trouver des solutions comparables à celles de la littérature en termes de qualité des résultats mais avec temps de calcul plus compétitif. Nous nous sommes intéressés dans un deuxième temps aux problèmes de réseaux mobiles appelés OFDMA-TDMA. Nous avons étudié le problème d’affectation de ressources dans ce type de réseaux, nous avons proposé deux modèles : Le premier modèle est un modèle déterministe qui permet de maximiser la bande passante du canal pour un réseau OFDMA à débit monodirectionnel appelé Uplink sous contraintes d’énergie utilisée par les utilisateurs et des contraintes d’affectation de porteuses. Pour ce problème, VNS donne de très bons résultats et des bornes de bonne qualité. Le deuxième modèle est un problème stochastique de réseaux OFDMA d’affectation de ressources multi-cellules. Pour résoudre ce problème, on utilise le problème déterministe équivalent auquel on applique la méthode VNS qui dans ce cas permet de trouver des solutions avec un saut de dualité très faible. Les problèmes d’allocation de ressources aussi bien dans les réseaux OFDMA ou dans d’autres domaines peuvent aussi être modélisés sous forme de problèmes d’optimisation bi-niveaux appelés aussi problèmes d’optimisation hiérarchique. Le dernier problème étudié dans le cadre de cette thèse porte sur les problèmes bi-niveaux stochastiques. Pour résoudre le problème lié à l’incertitude dans ce problème, nous avons utilisé l’optimisation robuste plus précisément l’approche appelée « distributionnellement robuste ». Cette approche donne de très bons résultats légèrement conservateurs notamment lorsque le nombre de variables du leader est très supérieur à celui du suiveur. Nos expérimentations ont confirmé l’efficacité de nos méthodes pour l’ensemble des problèmes étudiés. / Combinatorial optimization problems are generally NP-hard problems, so they can only rely on heuristic or approximation algorithms to find a local optimum or a feasible solution. During the last decades, more general solving techniques have been proposed, namely metaheuristics which can be applied to many types of combinatorial optimization problems. This PhD thesis proposed to solve the deterministic and stochastic optimization problems with metaheuristics. We studied especially Variable Neighborhood Search (VNS) and choose this algorithm to solve our optimization problems since it is able to find satisfying approximated optimal solutions within a reasonable computation time. Our thesis starts with a relatively simple deterministic combinatorial optimization problem: Bandwidth Minimization Problem. The proposed VNS procedure offers an advantage in terms of CPU time compared to the literature. Then, we focus on resource allocation problems in OFDMA systems, and present two models. The first model aims at maximizing the total bandwidth channel capacity of an uplink OFDMA-TDMA network subject to user power and subcarrier assignment constraints while simultaneously scheduling users in time. For this problem, VNS gives tight bounds. The second model is stochastic resource allocation model for uplink wireless multi-cell OFDMA Networks. After transforming the original model into a deterministic one, the proposed VNS is applied on the deterministic model, and find near optimal solutions. Subsequently, several problems either in OFDMA systems or in many other topics in resource allocation can be modeled as hierarchy problems, e.g., bi-level optimization problems. Thus, we also study stochastic bi-level optimization problems, and use robust optimization framework to deal with uncertainty. The distributionally robust approach can obtain slight conservative solutions when the number of binary variables in the upper level is larger than the number of variables in the lower level. Our numerical results for all the problems studied in this thesis show the performance of our approaches.