Traffic Engineering (TE) uses methods and models from a variety of mathematical fields, such as statistics and optimization, to improve the performance of telecommunication networks. In this thesis, we study TE problems dealing with networks that impose single-path routing. As the name infers, in this type of routing, the traffic flow of each "commodity" cannot be split in its path between its origin and destination. Given its cheap cost, single-path routing is widely used in today's data centers, where thousands of stored servers perform computations or host Internet services. One common case of single-path routing is the one enforced by the Spanning Tree Protocol (STP) in switched Ethernet networks. The STP requires the network to keep its activated links loop-free, while maintaining the other redundant links ready for back-up, in case of link failure. The Multiple Spanning Tree Protocol (MSTP) extends the STP by installing multiple virtual networks compliant with the STP, over a single physical topology. Therefore, the MSTP is greatly beneficial for network service providers, as it allows for a more efficient use of the existing resources.Network design problems dealing with the MSTP are generally highly combinatorial and very hard to solve. As such, TE literature mainly suggests heuristic methods, which can quickly produce reasonable designs. Notwithstanding, due to a scarce existence of lower bounds to the optimum values of such problems, there is little knowledge about the quality of the solutions provided by these heuristics.In this sense, we propose mathematical programming models and methods that can provide optimal designs for these networks, or at the very least, obtain valid lower bounds. Taking into mind the goal of avoiding congestion in the network, we focus on two problems that deal with the following load-balancing objectives: the minimization of the worst-case link utilization, and the minimization of flow costs given by piecewise linear functions that penalize heavily-loaded links. The study of both these problems yielded relevant by-products: the first is the study of a MSTP network design problem, where we minimize the total load, and the second is the study of a fundamental unsplittable multicommodity flow problem with piecewise linear costs.For all the considered problems, we provide studies of complexity, extensive polyhedral studies to compare the proposed formulations, and a wide array of computational experiments to evaluate the performance of the proposed models and methods. / Doctorat en Sciences / info:eu-repo/semantics/nonPublished

Within the DIECOFIS framework, ec3, the Division of Business Statistics from the Vienna University of Economics and Business Administration and ISTAT worked together to find methods to create a comprehensive database of enterprise data required for taxation microsimulations via integration of existing disparate enterprise data sources. This paper provides an overview of the broad spectrum of investigated methodology (including exact and statistical matching as well as imputation) and related statistical quality indicators, and emphasises the relevance of data integration, especially for official statistics, as a means of using available information more efficiently and improving the quality of a statistical agency's products. Finally, an outlook on an empirical study comparing different exact matching procedures in the maintenance of Statistics Austria's Business Register is presented.

Cette thèse s’intéresse aux problèmes d’emploi du temps d’universités. Ces problèmes sont rencontrés chaque année par les utilisateurs. Nous proposons des bornes inférieures, des méthodes heuristiques et des modèles de programmation mixte en nombres entiers et de programmation par contraintes. Nous traitons le problème d’emploi du temps d’examens et celui d’affectation des étudiants. Nous proposons de nouvelles méthodes et formulations et les comparons aux approches existantes. Nous proposons, pour le problème d’emploi du temps d’examens, une amélioration d’un modèle mathématique en nombres entiers qui permettra d’obtenir des solutions optimales. Ensuite, des bornes inférieures, une formulation plus compacte des contraintes et un modèle de programmation par contraintes sont proposés. Pour le problème d’emploi du temps d’examens à l’Université de Technologie de Compiègne, nous proposons une approche mémétique. Enfin, nous présentons un modèle mathématique pour le problème d’affectation des étudiants et nous étudions sa performance sur un ensemble d’instances réelles. / This thesis investigates university timetabling problems. These problems occur across universities and are faced each year by the practitioners. We propose new lower bounds, heuristic approaches, mixed integer and constraint programming models to solve them. We address the exam timetabling and the student scheduling problem. We investigate new methods and formulations and compare them to the existing approaches. For exam timetabling, we propose an improvement to an existing mixed integer programming model that makes it possible to obtain optimal solutions. Next, lower bounds, a more compact reformulation for constraints and a constraint programming model are proposed. For the exam timetabling problem at Université de Technologie de Compiègne, we designed a memetic approach. Finally, we present a new formulation for the student scheduling problem and investigate its performance on a set of real-world instances.

The steady state response of thin-walled members subjected to harmonic forces is investigated in the present study. The governing differential equations of motion and associated boundary conditions are derived from the Hamilton variational principle. The harmonic form of the applied forces is exploited to eliminate the need to discretize the problem in the time domain, resulting in computational efficiency. The formulation is based on a generalization of the Timoshenko-Vlasov beam theory and accounts for warping effects, shear deformation effects due to bending and non-uniform warping, translational and rotary inertial effects and captures flexural-torsional coupling arising in asymmetric cross-sections. Six of the resulting seven field equations are observed to be fully coupled for asymmetric cross-sections while the equation of longitudinal motion is observed to be uncoupled. Separate closed form solutions are provided for the cases of (i) doubly symmetric cross sections, (ii) monosymmetric cross-sections, and (iii) asymmetric cross-sections. The closed-form solutions are provided for cantilever and simply-supported boundary conditions. A family of shape functions is then developed based on the exact solution of the homogeneous field equations and then used to formulate a series of super-convergent finite beam elements. The resulting two-noded beam elements are shown to successfully capture the static and dynamic responses of thin-walled members. The finite elements developed involve no special discretization errors normally encountered in other finite element formulations and provide results in excellent agreement with those based on other established finite elements with a minimal number of degrees of freedom. The formulation is also capable to predict the natural frequencies and mode-shapes of the structural members. Comparisons with non-shear deformable beam solutions demonstrate the importance of shear deformation effects within short-span members subjected to harmonic loads with higher exciting frequencies. Comparisons with shell element solution results demonstrate that distortional effects are more pronounced in cantilevers with short spans. A generalized stress extraction scheme from the finite element formulation is then developed. Also, a generalization of the analysis procedure to accommodate multiple loads with distinct exciting frequencies is established. The study is concluded with design examples which illustrate the applicability of the formulation, in conjunction with established principles of fatigue design, in determining the fatigue life of steel members subjected to multiple harmonic forces.

Cette thèse porte sur la résolution de problèmes de transport qui intègrent des contraintes temporelles considérant les fenêtres de temps, la synchronisation des visites et l’équilibrage des services. Ces problèmes trouvent plusieurs applications dans le monde réel.L’objectif de nos recherches est l’élaboration de nouvelles méthodes de résolution pour les problèmes considérés en examinant leur performance avec une étude comparative par rapport aux différentes approches de la littérature. Deux variantes sont traitées. Le premier cas étudie le Problème de Tournées de Véhicules avec Fenêtres de Temps (VRPTW). Nous proposons de nouveaux prétraitements et bornes inférieures pour déterminer le nombre de véhicules nécessaires en s’inspirant de travaux menés en ordonnancement (raisonnement énergétique) et d’autres problèmes combinatoires comme la clique maximum et les problèmes de bin-packing. Nous présentons également un algorithme d’optimisation par essaim particulaire qui traite de la minimisation du nombre de véhicules puis de celle du temps de trajet total. Le deuxième cas étudie le Problème de Tournées de Véhicules avec des Fenêtres de Temps et des Visites Synchronisées (VRPTWSyn). Nous proposons plusieurs méthodes basées sur des approches heuristiques et des formulations linéaires avec l’incorporation d’inégalités valides pour tenir compte de la contrainte de synchronisation. / This dissertation focuses on vehicle routing problems, one of the major academic problems in logistics. We address NP-Hard problems that model some realworld situations particularly those with different temporal constraints including time windows, visit synchronization and service balance.The aim of this research is to develop new algorithms for the considered problems,investigate their performance and compare them with the literature approaches.Two cases are carried out. The first case studies the Vehicle Routing Problem with Time Windows (VRPTW). We propose new lower bound methods for the number of vehicles. Then we present a Particle Swarm Optimization algorithm dealing with the Solomon objective. The second case studies the VehicleRouting Problem with Time Windows and Synchronized Visits (VRPTWsyn).Both exact methods and heuristics are proposed and compared to the literature approaches.

京都大学 / 0048 / 新制・課程博士 / 博士(理学) / 甲第21562号 / 理博第4469号 / 新制||理||1641(附属図書館) / 京都大学大学院理学研究科物理学・宇宙物理学専攻 / (主査)准教授 國友 浩, 教授 杉本 茂樹, 教授 田中 貴浩 / 学位規則第4条第1項該当 / Doctor of Science / Kyoto University / DFAM

La théorie des cordes est un de nos meilleurs candidats pour une théorie quantique de la gravité. A ce jour elle n'a pas encore été conclusive à propose de ce sujet. Malgré cela, on a réalisé qu'on peut en tirer des informations sur tout une variété de sujets, dont notamment les théories de jauges supersymétriques, en étudiant la limite de basse énergie dans le volume d'univers des branes. Cette immersion des théories de jauges en théorie des cordes nous fournit un autre point de vue. Ce dernier nous permet souvent de prendre une approche plus géométrique pour obtenir de nouveaux résultats sinon inaccessible par des méthodes plus conventionnelles. Même en absence de vérification expérimentale de la supersymétrie, sa présence dans cette classe de théories de jauge nous fournit un terrain de jeux propice pour tester de nouvelles méthodes d'une manière efficace. En effet, la présence de la supersymétrie donne une structure additionnelle qui rend la théorie plus rigide. Cela simplifie les calculs et rend des résultats plus accessibles. On peut oser de dire que si on n'arrive pas à calculer un certain résultat en présence de supersymétrie, il y a très peu de chance d'y arriver sans. L'approche par la théorie des cordes le rend possible de découvrir des symétries cachées ou de comprendre des symétries connues d'une autre manière.Une classe de théories quantique intéressantes qui sont présentes en théories des cordes, c'est les théories de petites cordes. Ces dernières ont été découverte il y a deux décennies. Ces théories en six dimensions ont été construite une première fois comme théories dans le volume d'universe de branes NS5 dans le cadre de la théorie des cordes IIB en prenant la limite du couplage de la corde qui tend vers zéro. Dans cette limite, la théorie résultant reste non-trivial mais les interactions en dehors de la brane sont supprimées, notamment la gravité. Comme le nom le suggère, ces théories contiennent des cordes qu'on appelle petites cordes. La tension des petites cordes est proportionnelle à l'échelle naturelle de la corde. En plus, ces théories profitent de la T-dualité comme les théories de cordes critiques. Elle sont donc des théories quantiques non-locales. Leur complexité se situe entre celle des théories quantiques locales et celle de la théorie des cordes complète. Elles sont donc des candidates intéressantes pour étudier la dynamique dans le volume d'univers de la brane NS5. Pour des énergies inférieures à l'échelle de la corde, elles ont une description en termes de théories de jauges symétriques de type quiver. On peut donc également obtenir des informations sur ces dernières. Cette description locale n'est plus valable une fois l'échelle de la corde atteinte.Le but principal de cette thèse est d'étudier des dualités entre le théories de petites cordes en utilisant différentes constructions disponible en théorie des cordes. Cela nous permet d'attaquer le problème d'angles différents et de faire un lien avec des structures géométriques. En conséquence on peut analyser différentes relation parmi les théories de petites cordes. On confirme ensuite la validité des dualités qu'on obtient en utilisant la fonction de partition instantonique. Cet object est complètement non-perturbative et établit ces dualités comme résultat exact. Cette structure de dualités s'étend naturellement aux descriptions de basse énergie en terme de théories de jauges supersymétriques. De plus, on étudie les conséquences directes du réseaux de dualités qu'on a découvert. / String theory remains one of our best candidates for a theory of quantum gravity. Until now it has not lived up to this goal. However, along the way it was realized that string theory can give us valu-able insights into a variety of subjects among which supersymmetric gauge theories by studying the low-energy worldvolume dynamics of branes. This embedding of gauge theories into string theory provides us with a different viewpoint that often allows us to use powerful geometric considerati-ons in order to obtain new results that are inaccessible from conventional methods. Even in the ab-sence of experimental confirmation of supersymmetry, its presence in this class of gauge theories provides us with a playground where different methods can be tested in an efficient way. Indeed, supersymmetry provides additional structure, rendering the underlying theory more rigid and thus simplifying computations and making results more accessible. One could dare to say that when a certain result can not be calculated in the presence of supersymmetry, there is probably not much hope of achieving it without supersymmetry. This stringy approach to gauge theories makes it pos-sible to unravel hidden dualities or to understand already known ones from a different perspective. An interesting class of quantum theories that are embedded into string theory are the so called little string theories. They have been discovered two decades ago. These six-dimensional theories were first obtained as the worldvolume theory of a stack of NS5 branes in the context of Type II string theory trough a particular decoupling limit that sends the string coupling constant to zero while kee-ping at the same time the string scale finite. In this limit, the resulting theory remains interacting but the bulk dynamics is decoupled, in particular gravity. As their name suggests, they contain strings. The tension of the little strings is proportional to the string scale, which is the only intrinsic scale in the theory. Furthermore, the little string theories enjoy T-duality similar to the critical string theory. They are thus non-local quantum theories. So the complexity of little string theory lies between that of local quantum field theories and full fledged critical string theory. This makes them interesting candidates for studying stringy phenomena in an easier setup where gravity is absent and to learn more about the worldvolume dynamics of the NS5 brane. At energies far below the string scale, they have a low-energy description in terms of quiver gauge theories, so their study can also give us insights into these kinds of theories. This local description breaks down as we reach the string scale and we must rely on the full little string theories. The main goal of this thesis is to study dualities between little string theories by using different dual constructions available in string theory. These allow us to attack the problem from different angles and they establish also a connection to geometric structures. This makes it possible to systematically analyse relations among different little string theories. We then confirm the validity of the newly found duality relations by using the so called instanton partition function. The latter is a completely non-perturbative object allowing us to establish the dualities as an exact result. This duality structure naturally extends to the low-energy description in terms of supersymmetric quiver gauge theories. Furthermore, we study the direct consequences of this duality web. We find interesting cases where the dimensional reduction from six to five dimensions simultaneously reduces the rank of the group and changes the matter content. Another result that we find is the presence of a hidden dihedral symmetry which acts in a highly non-trivial fashion on the spectrum of the underlying gauge theories.

In the paper we construct exact three-point discretizations of linear and nonlinear two-point boundary value problems with boundary conditions of the first kind. The finite element approach uses basis functions defined by the coefficients of the differential equations. All the discretized boundary value problems are of inverse isotone type and so are its exact discretizations which involve tridiagonal M-matrices in the linear case and M-functions in the nonlinear case.

京都大学 / 0048 / 新制・課程博士 / 博士(理学) / 甲第17770号 / 理博第3893号 / 新制||理||1561(附属図書館) / 30577 / 京都大学大学院理学研究科物理学・宇宙物理学専攻 / (主査)教授 青山 秀明, 教授 畑 浩之, 准教授 早田 次郎 / 学位規則第4条第1項該当 / Doctor of Science / Kyoto University / DFAM

京都大学 / 0048 / 新制・課程博士 / 博士(工学) / 甲第17871号 / 工博第3780号 / 新制||工||1578(附属図書館) / 30691 / 京都大学大学院工学研究科都市社会工学専攻 / (主査)教授 谷口 栄一, 教授 藤井 聡, 准教授 宇野 伸宏 / 学位規則第4条第1項該当 / Doctor of Philosophy (Engineering) / Kyoto University / DFAM