Ferramentas de projeto de circuitos integrados (do inglˆes, electronic design automation, ou simplesmente EDA) tˆem um papel fundamental na crescente complexidade dos projetos de circuitos digitais. Elas permitem aos projetistas criar circuitos com um n´umero de componentes ordens de grandezas maior do que seria poss´ıvel se os circuitos fossem projetados `a m˜ao como nos dias iniciais da microeletrˆonica. Neste trabalho, dois importantes problemas em EDA ser˜ao abordados: dimensionamento de portas e posicionamento detalhado dirigido a desempenho. Para dimensionamento de portas, uma nova metodologia de relaxac¸ ˜ao Lagrangiana ´e apresentada baseada em informac¸ ˜ao de temporarizac¸ ˜ao locais e propagac¸ ˜ao de sensitividades. Para posicionamento detalhado dirigido a desempenho, um conjunto de movimentos de c´elulas ´e criado usando uma formac¸ ˜ao ´otima atenta `a forc¸a de alimentac¸ ˜ao para o balanceamento de cargas. Nossos resultados experimentais mostram que tais t´ecnicas s˜ao capazes de melhorar o atual estado-da-arte. / Electronic design automation (EDA) tools play a fundamental role in the increasingly complexity of digital circuit designs. They empower designers to create circuits with several order of magnitude more components than it would be possible by designing circuits by hand as was done in the early days of microelectronics. In this work, two important EDA problems are addressed: gate sizing and timing-driven detailed placement. They are studied and new techniques developed. For gate sizing, a new Lagrangian-relaxation methodology is presented based on local timing information and sensitivity propagation. For timing-driven detailed placement, a set of cell movement methods are created using drive strength-aware optimal formulation to driver/sink load balancing. Our experimental results shows that those techniques are able to improve the current state-of-the-art.

O Método do Lagrangeano aumentado em problemas de otimização estrutural com restrições dinâmicas, bem como os conceitos matemáticos e numéricos necessários à sua compreensão são descritos. Este método resolve uma seqüência de problemas de minimização sem restrições definidos utilizando a função objetivo e as funções restrições. Um programa de computador é desenvolvido e aplicado em diversos exemplos. Alem disto, foi efetuada uma análise de sensibilidade com relação aos parâmetros utilizados no método. O método mostrou-se eficiente nas aplicações em problemas com restrições dinâmicas. / We present the method of the augmented Lagrangian in problems of scructural optimization with dynamic restrictions, as well as its mathemathical and numerical concepts. This method solves a series of unconstrained minimization problems using the objective function and the restriction functions. A computational program is implemented and applied in several examples. The augmented Lagrangian parameters senbility is analysed. The method is quite efficient in applications in optimization problems with dynamic restrictions.

This dissertation presents the development and validation of the One Dimensional Turbulence (ODT) multiphase model in the Lagrangian reference frame. ODT is a stochastic model that captures the full range of length and time scales and provides statistical information on fine-scale turbulent-particle mixing and transport at low computational cost. The flow evolution is governed by a deterministic solution of the viscous processes and a stochastic representation of advection through stochastic domain mapping processes. The three algorithms for Lagrangian particle transport are presented within the context of the ODT approach. The Type-I and -C models consider the particle-eddy interaction as instantaneous and continuous change of the particle position and velocity, respectively. The Type-IC model combines the features of the Type-I and -C models. The models are applied to the multiphase flows in the homogeneous decaying turbulence and turbulent round jet. Particle dispersion, dispersion coefficients, and velocity statistics are predicted and compared with experimental data. The models accurately reproduces the experimental data sets and capture particle inertial effects and trajectory crossing effect. A new adjustable particle parameter is introduced into the ODT model, and sensitivity analysis is performed to facilitate parameter estimation and selection. A novel algorithm of the two-way momentum coupling between the particle and carrier phases is developed in the ODT multiphase model. Momentum exchange between the phases is accounted for through particle source terms in the viscous diffusion. The source term is implemented in eddy events through a new kernel transformation and an iterative procedure is required for eddy selection. This model is applied to a particle-laden turbulent jet flow, and simulation results are compared with experimental measurements. The effect of particle addition on the velocities of the gas phase is investigated. The development of particle velocity and particle number distribution are illustrated. The simulation results indicate that the model qualitatively captures the turbulent modulation with the presence of difference particle classes with different solid loadings. The model is then extended to simulate temperature evolution of the particles in a nonisothermal hot jet, in which heat transfer between the particles and gas is considered. The flow is bounded by a wall on the one side of the domain. The simulations are performed over a range of particle inertia and thermal relaxation time scales and different initial particle locations. The present study investigates the post-blast-phase mixing between the particles, the environment that is intended to heat them up, and the ambient environment that dilutes the jet flow. The results indicate that the model can qualitatively predict the important particle statistics in jet flame.

Dans cette thèse on utilise une méthode de Galerkin discontinue (GD) pour modéliser la propagation des ondes dans un matériau endommagé. Deux modèles différents pour la description de l’endommagement ont été considérés. Dans la première partie de la thèse on utilise un modèle d’endommagent assez général, basé sur une modélisation micromécanique. Pour ce modèle on établit un critère de stabilité basé sur une densité critique de fissuration. On développe aussi une méthode numérique GD capable de capturer les instabilités au niveau microscopique. On construit une solution exacte pour analyser la précision de la méthode proposée.Plusieurs résultats numériques vont permettre d’analyser la propagation des ondes dans les configurations planes et anti-planes. Dans la deuxième parte de la thèse on étudie la propagation des ondes dans un milieux fissuré (microfissures en contact avec frottement). La méthode numérique développée utilise une technique GD et la méthode du Lagrangien augmenté. En utilisant cette méthode on a pu calculer numériquement la vitesse de propagation moyenne dans un matériau endommagé. On a pu comparer les résultats obtenus avec les formules analytiques obtenues avec des approches micromécaniques. Finalement, on a utilisé les calculs numériques pour étudier la propagation des ondes après un impact sur une plaque céramique pour les deux modèles mécaniques considérés. / A discontinuous Galerkin (DG) technique for modeling wave propagation in damaged (brittle) materials is developed in this thesis. Two different types of mechanical models for describing the damaged materials are considered. In the first part of the thesis general micro-mechanics based damage models were used. A critical crack density parameter, which distinguishes between stable and unstable behaviors, wascomputed. A new DG-numerical scheme able to capture the instabilities and a micro-scale time step were proposed. An exact solution is constructed and the accuracy of the numerical scheme was analyzed. The wave propagation in one dimensional and anti-plane configuration was analyzed through several numerical computations. In the second part of the thesis the wave propagation in cracked materials with a nonlinear micro-structure (micro-cracks in frictional contact) was investigated. The numerical scheme developed makes use of a DG-method and an augmented Lagrangian technique. The effective wave velocity in a damaged material, obtained by a numerical upscaling homogenization method, was compared with analytical formula of effective elasticity theory. The wave propagation (speed, amplitude and pulse length) in micro-cracked materials in complex configurations was studied. Finally, numerical computations of blast wave propagation,for the both models, illustrate the role played by the micro-cracks orientation and by the friction.

The knowledge and understanding of sediment transport is essential for the development of effective management strategies for nutrient and sediment loading in estuarine systems. Estuarine suspended sediment (in high concentrations), has the ability to adversely impact upon surrounding ecosystems, such as the Great Barrier Reef, Australia. Due to a recent decline in water and sediment quality, it has recently been mandated that a number of tropical, coastal estuarine systems in Queensland, such as the Fitzroy River estuary, have their sediment loading reduced. In order to meet these requirements, a greater understanding of the sediment transport dynamics and driving processes (such as flocculation and settling velocity) needs to be achieved, and the accuracy of estimation improved. This research project was motivated by the need to improve the general accuracy of field measurements for estuarine suspended sediment transport and dynamics. Field-based measurements (especially settling velocity) are necessary for the parameterisation of sediment transport models. The difficulty in obtaining accurate, in situ data is well documented and is generally limited to methods that isolate a water sample from its natural environment, removing all influences of estuarine turbulence. Furthermore, the water samples are often extracted from points (Eulerian) where the history of the suspended particles is generally unknown. These sampling methods typically contain intrinsic errors as suspended sediment transport is essentially Lagrangian (i.e., flows with the net motion of flow-field) in nature. An investigation into different drogue systems conducted in parallel with a study into the tidal states of the Fitzroy River estuary led to the development of a novel Lagrangian drogue device, the LAD. Additionally, the water-tracking ability of the LAD was tested and found to accurately follow a parcel of estuarine water over a slack water period. Therefore the LAD was deployed in the Fitzroy River to assist in the further understanding of complex sediment transport processes such as flocculation and settling velocity in a natural estuarine flow field. The final device (the LAD - Lagrangian Acoustic Drogue) was developed, utilizing the principals of acoustic backscatter intensity-derived SSC measurements. The investigation of a series LAD deployments (during slack water) in the Fitzroy River estuary, revealed the dominant suspended sediment processes and also gave an insight into the prevailing flow-patterns. Results showed the presence of a settling lag mechanism between low and high tide, which can initiate a net sediment flow upstream with each flood tide. The bulk settling velocity showed comparable results at both low and high water. The LAD derived bulk settling velocity as a function of concentration (SSC), yielding a strong positive correlation (r2 = 0.73). Also the importance of flocculation in the bulk settling and clear up of the water column during periods of still water (high and low tide) was demonstrated as all in situ settling velocities (0.33 - 1.75 mm s-1) exceeded single grain approximations (0.47 mm s-1). This research demonstrates the potential for Lagrangian drogue studies as an effective measuring platform for the accurate quantification of estuarine suspended sediment dynamics. The application of the LAD in the Fitzroy River has lead to a significant improvement in the understanding of the system's real sediment transport processes. This research has provided an effective and accurate technique for measuring real settling velocities for input into numerical models or for the validation of existing model outputs. Furthermore, this technique shows great potential for application in other estuarine systems.

<p>In this thesis a method for solving the Generalized Assignment Problem (GAP) is described. It is based on a reformulation of the original problem into a Set Partitioning Problem (SPP), in which the columns represent partial solutions to the original problem. For solving this problem, column generation, with systematic overgeneration of columns, is used. Conditions that guarantee that an optimal solution to a restricted SPP is optimal also in the original problem are given. In order to satisfy these conditions, not only columns with the most negative Lagrangian reduced costs need to be generated, but also others; this observation leads to the use of overgeneration of columns.</p><p>The Generalized Assignment Problem has shown to be NP-hard and therefore efficient algorithms are needed, especially for large problems. The application of the proposed method decomposes GAP into several knapsack problems via Lagrangian relaxation, and enumerates solutions to each of these problems. The solutions obtained from the knapsack problems form a Set Partitioning Problem, which consists of combining one solution from each knapsack problem to obtain a solution to the original problem. The algorithm has been tested on problems with 10 agents and 60 jobs. This leads to 10 knapsack problems, each with 60 variables.</p>

We study a natural Dirac operator on a Lagrangian submanifold of a Kähler manifold. We first show that its square coincides with the Hodge - de Rham Laplacian provided the complex structure identifies the Spin structures of the tangent and normal bundles of the submanifold. We then give extrinsic estimates for the eigenvalues of that operator and discuss some examples.

This thesis consists of a summary of two papers dealing with questions related to Legendrian submanifolds of contact manifolds together with exact Lagrangian cobordisms between Legendrian submanifolds. The focus is on studying Legendrian submanifolds from the perspective of their handle decompositions. The techniques used are mainly from Symplectic Field Theory. In Paper I, a series of examples of Legendrian surfaces in standard contact 5-space are studied. For every g &gt; 0, we produce g+1 Legendrian surfaces of genus g, all with g+1 transverse Reeb chords, which lie in distinct Legendrian isotopy classes. For each g, exactly one of the constructed surfaces has a Legendrian contact homology algebra admitting an augmentation. Moreover, it is shown that the same surface is the only one admitting a generating family. Legendrian contact homology with Novikov coefficients is used to classify the different Legendrian surfaces. In particular, we study their augmentation varieties. In Paper II, the effect of a Legendrian ambient surgery on a Legendrian submanifold is studied. Given a Legendrian submanifold together which certain extra data, a Legendrian ambient surgery produces a Legendrian embedding of the manifold obtained by surgery on the original submanifold. The construction also provides an exact Lagrangian handle-attachment cobordism between the two submanifolds. The Legendrian contact homology of the submanifold produced by the Legendrian ambient surgery is then computed in terms of pseudo-holomorphic disks determined by data on the original submanifold. Also, the cobordism map induced by the exact Lagrangian handle attachment is computed. As a consequence, it is shown that a sub-critical standard Lagrangian handle attachment cobordism induces a one-to-one correspondence between the augmentations of the Legendrian contact homology algebras of its two ends.

This thesis studies the allocation of stock in a two-level inventory system with stochastic demand. The system consists of one central warehouse which supplies N non-identical retailers with one single product. Customer demand occurs solely at the retailers and follows independent Poisson processes. The purpose is to investigate the value of using a more advanced allocation policy than First Come-First Serve at the central warehouse. The focus is on evaluating how well the simple First Come-First Serve assumption works in a system where the warehouse has access to real-time point-of-sale data, and where shipments are time based and consolidated for all retailers. The considered allocation policy is a myopic policy where the solution to a minimization problem, formulated as a constrained newsvendor problem, determines how the warehouse allocates its stock to the retailers. The minimization problem is solved using (a heuristic method based on) Lagrangian relaxation, and simulation is used to evaluate the average inventory holding costs and backorder costs per time unit when using the considered policy. The simulation study shows that cost savings around 1-4 percent can be expected for most system configurations. However, there were cases where savings were as high as 5 percent, as well as cases where the policy performed worse than First Come-First Serve. The study also shows that the highest cost savings are found in systems with relatively low demand, few retailers, short transportation times and a short time interval between shipments.

There is an increasing interest in sustainability and a growing debate about environmental policy measures aiming at the reduction of green house gas emissions across di erent economic sectors worldwide. The transportation sector is one major greenhouse gas emitter which is heavily regulated to reduce its dependance on oil. These regulations along with the growing customer awareness about global warming has led vehicle manufacturers to seek di erent technologies to improve vehicle e ciencies and reduce the green house gases emissions while at the same time meeting customer's expectation of mobility and exibility. Plug-in hybrid electric vehicles (PHEV) is one major promising solution for a smooth transition from oil dependent transportation sector to a clean electric based sector while not compromising the mobility and exibility of the drivers. In the medium term, plug-in hybrid electric vehicles (PHEV) can lead to signi cant reductions in transportation emissions. These vehicles are equipped with a larger battery than regular hybrid electric vehicles which can be recharged from the grid. For short trips, the PHEV can depend solely on the electric engine while for longer journeys the alternative fuel can assist the electric engine to achieve extended ranges. This is bene cial when the use pattern is mixed such that and short long distances needs to be covered. The plug-in hybrid electric vehicles are well-suited for logistics since they can avoid the possible disruption caused by charge depletion in case of all-electric vehicles with tight time schedules. The use of electricity and fuel gives rise to a new variant of the classical vehicle routing with time windows which we call the plug-in hybrid electric vehicle routing problem with time windows (PHEVRPTW). The objective of the PHEVRPTW is to minimize the routing costs of a eet of PHEVs by minimizing the time they run on gasoline while meeting the demand during the available time windows. As a result, the driver of the PHEV has two decisions to make at each node: (1) recharge the vehicle battery to achieve a longer range using electricity, or (2) continue to the next open time window with the option of using the alternative fuel. In this thesis, we present a mathematical formulation for the plug-in hybrid-electric vehicle routing problem with time windows. We solve this problem using a Lagrangian relaxation and we propose a new tabu search algorithm. We also present the rst results for the full adapted Solomon instances.