The three-dimensional single-bin-size bin packing problem: combining metaheuristic and machine learning approaches

The Three-Dimensional Single-Bin-Size Bin Packing Problem is one of the most studied problem in the Cutting & Packing category. From a strictly mathematical point of view, it consists of packing a finite set of strongly heterogeneous “small” boxes, called items, into a finite set of identical “large” rectangles, called bins, minimizing the unused volume and requiring that the items are packed without overlapping. The great interest is mainly due to the number of real-world applications in which it arises, such as pallet and container loading, cutting objects out of a piece of material and packaging design. Depending on these real-world applications, more objective functions and more practical constraints could be needed. After a brief discussion about the real-world applications of the problem and a exhaustive literature review, the design of a two-stage algorithm to solve the aforementioned problem is presented. The algorithm must be able to provide the spatial coordinates of the placed boxes vertices and also the optimal boxes input sequence, while guaranteeing geometric, stability, fragility constraints and a reduced computational time. Due to NP-hard complexity of this type of combinatorial problems, a fusion of metaheuristic and machine learning techniques is adopted. In particular, a hybrid genetic algorithm coupled with a feedforward neural network is used. In the first stage, a rich dataset is created starting from a set of real input instances provided by an industrial company and the feedforward neural network is trained on it. After its training, given a new input instance, the hybrid genetic algorithm is able to run using the neural network output as input parameter vector, providing as output the optimal solution. The effectiveness of the proposed works is confirmed via several experimental tests.

Be-Fe coupled method for the analysis of 3D elastodynamic problems in the time domain

By coupling the Boundary Element Method (BEM) and the Finite Element Method (FEM) an algorithm that combines the advantages of both numerical processes is developed. The main aim of the work concerns the time domain analysis of general three-dimensional wave propagation problems in elastic media. In addition, mathematical and numerical aspects of the related BE-, FE- and BE/FE-formulations are discussed. The coupling algorithm allows investigations of elastodynamic problems with a BE- and a FE-subdomain. In order to observe the performance of the coupling algorithm two problems are solved and their results compared to other numerical solutions.

Time-resolved studies of neutral and ionized Na_n clusters with femtosecond light pulses

The real-time dynamics of Na_n (n=3-21) cluster multiphoton ionization and fragmentation has been studied in beam experiments applying femtosecond pump-probe techniques in combination with ion and electron spectroscopy. Three dimensional wave packet motions in the trimer Na_3 ground state X and excited state B have been observed. We report the first study of cluster properties (energy, bandwidth and lifetime of intermediate resonances Na_n^*) with femtosecond laser pulses. The observation of four absorption resonances for the cluster Na_8 with different energy widths and different decay patterns is more difficult to interpret by surface plasmon like resonances than by molecular structure and dynamics. Timeresolved fragmentation of cluster ions Na_n^+ indicates that direct photo-induced fragmentation processes are more important at short times than the statistical unimolecular decay.

Fundamental interactions of molecules (Na_2, Na_3) with intense femtosecond laser pulses

The real-time dynamics of multiphoton ionization and fragmentation of molecules Na_2 and Na_3 has been studied in molecular beam experiments employing ion and electron spectroscopy together with femtosecond pump-probe techniques. Experiments with Na_2 and Na_3 reveal unexpected features of the dynamics of the absorption of several photons as seen in the one- and three-dimensional vibrational wave packet motion in different potential surfaces and in high laser fields: In Na_2 a second major resonance-enhanced multiphoton ionization (REMPI) process is observed, involving the excitation of two electrons and subsequent electronic autoionization. The possibility of controlling a reaction by controlling the duration of propagation of a wave packet on an electronically-excited surface is demonstrated. In high laser fields, the contributions from direct photoionization and from the second REMPI process to the total ion yield change, due to different populations in the electronic states participating in the multiphoton ionization (MPI) processes. In addition, a vibrational wave packet motion in the electronic ground state is induced through stimulated emission pumping by the pump laser. The 4^1 \summe^+_g shelf state of Na_2 is given as an example for performing frequency spectroscopy of highlying electronic states in the time domain. Pure wave packet effects, such as the spreading and the revival of a vibrational wave packet, are investigated. The three-dimensional wave packet motion in the Na_3 reflects the normal modes in the X and B states, and shows in addition the pseudorotational motion in the B state in real time.

Stochastic Modeling of Reversible Biochemical Reaction-Diffusion Systems and High-Resolution Shock-Capturing Methods for Fluid Interfaces

Thesis (Ph.D.)--University of Washington, 2016-08

Nonlinear wave-activity conservation laws and Hamiltonian structure for the two-dimensional anelastic equations

Exact, finite-amplitude, local wave-activity conservation laws are derived for disturbances to steady flows in the context of the two-dimensional anelastic equations. The conservation laws are expressed entirely in terms of Eulerian quantities, and have the property that, in the limit of a small-amplitude, slowly varying, monochromatic wave train, the wave-activity density A and flux F, when averaged over phase, satisfy F = cgA where cg is the group velocity of the waves. For nonparallel steady flows, the only conserved wave activity is a form of disturbance pseudoenergy; when the steady flow is parallel, there is in addition a conservation law for the disturbance pseudomomentum. The above results are obtained not only for isentropic background states (which give the so-called “deep form” of the anelastic equations), but also for arbitrary background potential-temperature profiles θ0(z) so long as the variation in θ0(z) over the depth of the fluid is small compared with θ0 itself. The Hamiltonian structure of the equations is established in both cases, and its symmetry properties discussed. An expression for available potential energy is also derived that, for the case of a stably stratified background state (i.e., dθ0/dz > 0), is locally positive definite; the expression is valid for fully three-dimensional flow. The counterparts to results for the two-dimensional Boussinesq equations are also noted.

Reduced three-wave model to study the hard transition to chaotic dynamics in Alfven wave-fronts

The derivative nonlinear Schrödinger (DNLS) equation, describing propagation of circularly polarized Alfven waves of finite amplitude in a cold plasma, is truncated to explore the coherent, weakly nonlinear, cubic coupling of three waves near resonance, one wave being linearly unstable and the other waves damped. In a reduced three-wave model (equal damping of daughter waves, three-dimensional flow for two wave amplitudes and one relative phase), no matter how small the growth rate of the unstable wave there exists a parametric domain with the flow exhibiting chaotic dynamics that is absent for zero growth-rate. This hard transition in phase-space behavior occurs for left-hand (LH) polarized waves, paralelling the known fact that only LH time-harmonic solutions of the DNLS equation are modulationally unstable.

Character of magnetic excitations in a quasi-one-dimensional antiferromagnet near the quantum critical points: Impact on magnetoacoustic properties

We report results of magnetoacoustic studies in the quantum spin-chain magnet NiCl(2)-4SC(NH(2))(2) (DTN) having a field-induced ordered antiferromagnetic (AF) phase. In the vicinity of the quantum critical points (QCPs) the acoustic c(33) mode manifests a pronounced softening accompanied by energy dissipation of the sound wave. The acoustic anomalies are traced up to T > T(N), where the thermodynamic properties are determined by fermionic magnetic excitations, the ""hallmark"" of one-dimensional (1D) spin chains. On the other hand, as established in earlier studies, the AF phase in DTN is governed by bosonic magnetic excitations. Our results suggest the presence of a crossover from a 1D fermionic to a three-dimensional bosonic character of the magnetic excitations in DTN in the vicinity of the QCPs.

Chebyshev real wave packet propagation: H+O-2 (J=0) state-to-state reactive scattering calculations

In this paper we explore the relative performance of two recently developed wave packet methodologies for reactive scattering, namely the real wave packet Chebyshev domain propagation of Gray and Balint-Kurti [J. Chem. Phys. 108, 950 (1998)] and the Lanczos subspace wave packet approach of Smith [J. Chem. Phys. 116, 2354 (2002); Chem. Phys. Lett. 336, 149 (2001)]. In the former method, a modified Schrodinger equation is employed to propagate the real part of the wave packet via the well-known Chebyshev iteration. While the time-dependent wave packet from the modified Schrodinger equation is different from that obtained using the standard Schrodinger equation, time-to-energy Fourier transformation yields wave functions which differ only trivially by normalization. In the Lanczos subspace approach the linear system of equations defining the action of the Green operator may be solved via either time-dependent or time-independent methods, both of which are extremely efficient due to the simple tridiagonal structure of the Hamiltonian in the Lanczos representation. The two different wave packet methods are applied to three dimensional reactive scattering of H+O-2 (total J=0). State-to-state reaction probabilities, product state distributions, as well as initial-state-resolved cumulative reaction probabilities are examined. (C) 2002 American Institute of Physics.

Time-lapse and probabilistic inversion strategies for plane-wave electromagnetic data.

L'utilisation efficace des systèmes géothermaux, la séquestration du CO2 pour limiter le changement climatique et la prévention de l'intrusion d'eau salée dans les aquifères costaux ne sont que quelques exemples qui démontrent notre besoin en technologies nouvelles pour suivre l'évolution des processus souterrains à partir de la surface. Un défi majeur est d'assurer la caractérisation et l'optimisation des performances de ces technologies à différentes échelles spatiales et temporelles. Les méthodes électromagnétiques (EM) d'ondes planes sont sensibles à la conductivité électrique du sous-sol et, par conséquent, à la conductivité électrique des fluides saturant la roche, à la présence de fractures connectées, à la température et aux matériaux géologiques. Ces méthodes sont régies par des équations valides sur de larges gammes de fréquences, permettant détudier de manières analogues des processus allant de quelques mètres sous la surface jusqu'à plusieurs kilomètres de profondeur. Néanmoins, ces méthodes sont soumises à une perte de résolution avec la profondeur à cause des propriétés diffusives du champ électromagnétique. Pour cette raison, l'estimation des modèles du sous-sol par ces méthodes doit prendre en compte des informations a priori afin de contraindre les modèles autant que possible et de permettre la quantification des incertitudes de ces modèles de façon appropriée. Dans la présente thèse, je développe des approches permettant la caractérisation statique et dynamique du sous-sol à l'aide d'ondes EM planes. Dans une première partie, je présente une approche déterministe permettant de réaliser des inversions répétées dans le temps (time-lapse) de données d'ondes EM planes en deux dimensions. Cette stratégie est basée sur l'incorporation dans l'algorithme d'informations a priori en fonction des changements du modèle de conductivité électrique attendus. Ceci est réalisé en intégrant une régularisation stochastique et des contraintes flexibles par rapport à la gamme des changements attendus en utilisant les multiplicateurs de Lagrange. J'utilise des normes différentes de la norme l2 pour contraindre la structure du modèle et obtenir des transitions abruptes entre les régions du model qui subissent des changements dans le temps et celles qui n'en subissent pas. Aussi, j'incorpore une stratégie afin d'éliminer les erreurs systématiques de données time-lapse. Ce travail a mis en évidence l'amélioration de la caractérisation des changements temporels par rapport aux approches classiques qui réalisent des inversions indépendantes à chaque pas de temps et comparent les modèles. Dans la seconde partie de cette thèse, j'adopte un formalisme bayésien et je teste la possibilité de quantifier les incertitudes sur les paramètres du modèle dans l'inversion d'ondes EM planes. Pour ce faire, je présente une stratégie d'inversion probabiliste basée sur des pixels à deux dimensions pour des inversions de données d'ondes EM planes et de tomographies de résistivité électrique (ERT) séparées et jointes. Je compare les incertitudes des paramètres du modèle en considérant différents types d'information a priori sur la structure du modèle et différentes fonctions de vraisemblance pour décrire les erreurs sur les données. Les résultats indiquent que la régularisation du modèle est nécessaire lorsqu'on a à faire à un large nombre de paramètres car cela permet d'accélérer la convergence des chaînes et d'obtenir des modèles plus réalistes. Cependent, ces contraintes mènent à des incertitudes d'estimations plus faibles, ce qui implique des distributions a posteriori qui ne contiennent pas le vrai modèledans les régions ou` la méthode présente une sensibilité limitée. Cette situation peut être améliorée en combinant des méthodes d'ondes EM planes avec d'autres méthodes complémentaires telles que l'ERT. De plus, je montre que le poids de régularisation des paramètres et l'écart-type des erreurs sur les données peuvent être retrouvés par une inversion probabiliste. Finalement, j'évalue la possibilité de caractériser une distribution tridimensionnelle d'un panache de traceur salin injecté dans le sous-sol en réalisant une inversion probabiliste time-lapse tridimensionnelle d'ondes EM planes. Etant donné que les inversions probabilistes sont très coûteuses en temps de calcul lorsque l'espace des paramètres présente une grande dimension, je propose une stratégie de réduction du modèle ou` les coefficients de décomposition des moments de Legendre du panache de traceur injecté ainsi que sa position sont estimés. Pour ce faire, un modèle de résistivité de base est nécessaire. Il peut être obtenu avant l'expérience time-lapse. Un test synthétique montre que la méthodologie marche bien quand le modèle de résistivité de base est caractérisé correctement. Cette méthodologie est aussi appliquée à un test de trac¸age par injection d'une solution saline et d'acides réalisé dans un système géothermal en Australie, puis comparée à une inversion time-lapse tridimensionnelle réalisée selon une approche déterministe. L'inversion probabiliste permet de mieux contraindre le panache du traceur salin gr^ace à la grande quantité d'informations a priori incluse dans l'algorithme. Néanmoins, les changements de conductivités nécessaires pour expliquer les changements observés dans les données sont plus grands que ce qu'expliquent notre connaissance actuelle des phénomenès physiques. Ce problème peut être lié à la qualité limitée du modèle de résistivité de base utilisé, indiquant ainsi que des efforts plus grands devront être fournis dans le futur pour obtenir des modèles de base de bonne qualité avant de réaliser des expériences dynamiques. Les études décrites dans cette thèse montrent que les méthodes d'ondes EM planes sont très utiles pour caractériser et suivre les variations temporelles du sous-sol sur de larges échelles. Les présentes approches améliorent l'évaluation des modèles obtenus, autant en termes d'incorporation d'informations a priori, qu'en termes de quantification d'incertitudes a posteriori. De plus, les stratégies développées peuvent être appliquées à d'autres méthodes géophysiques, et offrent une grande flexibilité pour l'incorporation d'informations additionnelles lorsqu'elles sont disponibles. -- The efficient use of geothermal systems, the sequestration of CO2 to mitigate climate change, and the prevention of seawater intrusion in coastal aquifers are only some examples that demonstrate the need for novel technologies to monitor subsurface processes from the surface. A main challenge is to assure optimal performance of such technologies at different temporal and spatial scales. Plane-wave electromagnetic (EM) methods are sensitive to subsurface electrical conductivity and consequently to fluid conductivity, fracture connectivity, temperature, and rock mineralogy. These methods have governing equations that are the same over a large range of frequencies, thus allowing to study in an analogous manner processes on scales ranging from few meters close to the surface down to several hundreds of kilometers depth. Unfortunately, they suffer from a significant resolution loss with depth due to the diffusive nature of the electromagnetic fields. Therefore, estimations of subsurface models that use these methods should incorporate a priori information to better constrain the models, and provide appropriate measures of model uncertainty. During my thesis, I have developed approaches to improve the static and dynamic characterization of the subsurface with plane-wave EM methods. In the first part of this thesis, I present a two-dimensional deterministic approach to perform time-lapse inversion of plane-wave EM data. The strategy is based on the incorporation of prior information into the inversion algorithm regarding the expected temporal changes in electrical conductivity. This is done by incorporating a flexible stochastic regularization and constraints regarding the expected ranges of the changes by using Lagrange multipliers. I use non-l2 norms to penalize the model update in order to obtain sharp transitions between regions that experience temporal changes and regions that do not. I also incorporate a time-lapse differencing strategy to remove systematic errors in the time-lapse inversion. This work presents improvements in the characterization of temporal changes with respect to the classical approach of performing separate inversions and computing differences between the models. In the second part of this thesis, I adopt a Bayesian framework and use Markov chain Monte Carlo (MCMC) simulations to quantify model parameter uncertainty in plane-wave EM inversion. For this purpose, I present a two-dimensional pixel-based probabilistic inversion strategy for separate and joint inversions of plane-wave EM and electrical resistivity tomography (ERT) data. I compare the uncertainties of the model parameters when considering different types of prior information on the model structure and different likelihood functions to describe the data errors. The results indicate that model regularization is necessary when dealing with a large number of model parameters because it helps to accelerate the convergence of the chains and leads to more realistic models. These constraints also lead to smaller uncertainty estimates, which imply posterior distributions that do not include the true underlying model in regions where the method has limited sensitivity. This situation can be improved by combining planewave EM methods with complimentary geophysical methods such as ERT. In addition, I show that an appropriate regularization weight and the standard deviation of the data errors can be retrieved by the MCMC inversion. Finally, I evaluate the possibility of characterizing the three-dimensional distribution of an injected water plume by performing three-dimensional time-lapse MCMC inversion of planewave EM data. Since MCMC inversion involves a significant computational burden in high parameter dimensions, I propose a model reduction strategy where the coefficients of a Legendre moment decomposition of the injected water plume and its location are estimated. For this purpose, a base resistivity model is needed which is obtained prior to the time-lapse experiment. A synthetic test shows that the methodology works well when the base resistivity model is correctly characterized. The methodology is also applied to an injection experiment performed in a geothermal system in Australia, and compared to a three-dimensional time-lapse inversion performed within a deterministic framework. The MCMC inversion better constrains the water plumes due to the larger amount of prior information that is included in the algorithm. The conductivity changes needed to explain the time-lapse data are much larger than what is physically possible based on present day understandings. This issue may be related to the base resistivity model used, therefore indicating that more efforts should be given to obtain high-quality base models prior to dynamic experiments. The studies described herein give clear evidence that plane-wave EM methods are useful to characterize and monitor the subsurface at a wide range of scales. The presented approaches contribute to an improved appraisal of the obtained models, both in terms of the incorporation of prior information in the algorithms and the posterior uncertainty quantification. In addition, the developed strategies can be applied to other geophysical methods, and offer great flexibility to incorporate additional information when available.

Suppression of scroll wave turbulence by noise

Rotating scroll waves are dynamical spatiotemporal structures characteristic of three-dimensional active media. It is well known that, under low excitability conditions, scroll waves develop an intrinsically unstable dynamical regime that leads to a highly disorganized pattern of wave propagation. Such a ¿turbulent¿ state bears some resemblance to fibrillation states in cardiac tissue. We show here that this unstable regime can be controlled by using a spatially distributed random forcing superimposed on a control parameter of the system. Our results are obtained from numerical simulations but an explicit analytical argument that rationalizes our observations is also presented.

Suppression of scroll wave turbulence by noise

Rotating scroll waves are dynamical spatiotemporal structures characteristic of three-dimensional active media. It is well known that, under low excitability conditions, scroll waves develop an intrinsically unstable dynamical regime that leads to a highly disorganized pattern of wave propagation. Such a ¿turbulent¿ state bears some resemblance to fibrillation states in cardiac tissue. We show here that this unstable regime can be controlled by using a spatially distributed random forcing superimposed on a control parameter of the system. Our results are obtained from numerical simulations but an explicit analytical argument that rationalizes our observations is also presented.

Acoustic scattering by mildly rough unbounded surfaces in three dimensions

For a nonlocally perturbed half- space we consider the scattering of time-harmonic acoustic waves. A second kind boundary integral equation formulation is proposed for the sound-soft case, based on a standard ansatz as a combined single-and double-layer potential but replacing the usual fundamental solution of the Helmholtz equation with an appropriate half- space Green's function. Due to the unboundedness of the surface, the integral operators are noncompact. In contrast to the two-dimensional case, the integral operators are also strongly singular, due to the slow decay at infinity of the fundamental solution of the three-dimensional Helmholtz equation. In the case when the surface is sufficiently smooth ( Lyapunov) we show that the integral operators are nevertheless bounded as operators on L-2(Gamma) and on L-2(Gamma G) boolean AND BC(Gamma) and that the operators depend continuously in norm on the wave number and on G. We further show that for mild roughness, i.e., a surface G which does not differ too much from a plane, the boundary integral equation is uniquely solvable in the space L-2(Gamma) boolean AND BC(Gamma) and the scattering problem has a unique solution which satisfies a limiting absorption principle in the case of real wave number.

Planetary-wave-induced transport in the stratosphere

In the stratosphere, chemical tracers are drawn systematically from the equator to the pole. This observed Brewer–Dobson circulation is driven by wave drag, which in the stratosphere arises mainly from the breaking and dissipation of planetary-scale Rossby waves. While the overall sense of the circulation follows from fundamental physical principles, a quantitative theoretical understanding of the connection between wave drag and Lagrangian transport is limited to linear, small-amplitude waves. However, planetary waves in the stratosphere generally grow to a large amplitude and break in a strongly nonlinear fashion. This paper addresses the connection between stratospheric wave drag and Lagrangian transport in the presence of strong nonlinearity, using a mechanistic three-dimensional primitive equations model together with offline particle advection. Attention is deliberately focused on a weak forcing regime, such that sudden warmings do not occur and a quasi-steady state is reached, in order to examine this question in the cleanest possible context. Wave drag is directly linked to the transformed Eulerian mean (TEM) circulation, which is often used as a surrogate for mean Lagrangian motion. The results show that the correspondence between the TEM and mean Lagrangian velocities is quantitatively excellent in regions of linear, nonbreaking waves (i.e., outside the surf zone), where streamlines are not closed. Within the surf zone, where streamlines are closed and meridional particle displacements are large, the agreement between the vertical components of the two velocity fields is still remarkably good, especially wherever particle paths are coherent so that diabatic dispersion is minimized. However, in this region the meridional mean Lagrangian velocity bears little relation to the meridional TEM velocity, and reflects more the kinematics of mixing within and across the edges of the surf zone. The results from the mechanistic model are compared with those from the Canadian Middle Atmosphere Model to test the robustness of the conclusions.

The stability of a two-dimensional vorticity filament under uniform strain

The quantitative effects of uniform strain and background rotation on the stability of a strip of constant vorticity (a simple shear layer) are examined. The thickness of the strip decreases in time under the strain, so it is necessary to formulate the linear stability analysis for a time-dependent basic flow. The results show that even a strain rate γ (scaled with the vorticity of the strip) as small as 0.25 suppresses the conventional Rayleigh shear instability mechanism, in the sense that the r.m.s. wave steepness cannot amplify by more than a certain factor, and must eventually decay. For γ < 0.25 the amplification factor increases as γ decreases; however, it is only 3 when γ e 0.065. Numerical simulations confirm the predictions of linear theory at small steepness and predict a threshold value necessary for the formation of coherent vortices. The results help to explain the impression from numerous simulations of two-dimensional turbulence reported in the literature that filaments of vorticity infrequently roll up into vortices. The stabilization effect may be expected to extend to two- and three-dimensional quasi-geostrophic flows.