Algorithme de branch-and-price-and-cut pour le problème de conception de réseaux avec coûts fixes, capacités et un seul produit

De nombreux problèmes liés aux domaines du transport, des télécommunications et de la logistique peuvent être modélisés comme des problèmes de conception de réseaux. Le problème classique consiste à transporter un flot (données, personnes, produits, etc.) sur un réseau sous un certain nombre de contraintes dans le but de satisfaire la demande, tout en minimisant les coûts. Dans ce mémoire, on se propose d'étudier le problème de conception de réseaux avec coûts fixes, capacités et un seul produit, qu'on transforme en un problème équivalent à plusieurs produits de façon à améliorer la valeur de la borne inférieure provenant de la relaxation continue du modèle. La méthode que nous présentons pour la résolution de ce problème est une méthode exacte de branch-and-price-and-cut avec une condition d'arrêt, dans laquelle nous exploitons à la fois la méthode de génération de colonnes, la méthode de génération de coupes et l'algorithme de branch-and-bound. Ces méthodes figurent parmi les techniques les plus utilisées en programmation linéaire en nombres entiers. Nous testons notre méthode sur deux groupes d'instances de tailles différentes (gran-des et très grandes), et nous la comparons avec les résultats donnés par CPLEX, un des meilleurs logiciels permettant de résoudre des problèmes d'optimisation mathématique, ainsi qu’avec une méthode de branch-and-cut. Il s'est avéré que notre méthode est prometteuse et peut donner de bons résultats, en particulier pour les instances de très grandes tailles.

Type Ia supernovae from violent mergers of carbon-oxygen white dwarfs: polarization signatures

The violent merger of two carbon-oxygen white dwarfs has been proposed as a viable progenitor for some Type Ia supernovae. However, it has been argued that the strong ejecta asymmetries produced by this model might be inconsistent with the low degree of polarization typically observed in Type Ia supernova explosions. Here, we test this claim by carrying out a spectropolarimetric analysis for the model proposed by Pakmor et al. for an explosion triggered during the merger of a 1.1 and 0.9 M⊙ carbon-oxygen white dwarf binary system. Owing to the asymmetries of the ejecta, the polarization signal varies significantly with viewing angle. We find that polarization levels for observers in the equatorial plane are modest (≲1 per cent) and show clear evidence for a dominant axis, as a consequence of the ejecta symmetry about the orbital plane. In contrast, orientations out of the plane are associated with higher degrees of polarization and departures from a dominant axis. While the particular model studied here gives a good match to highly polarized events such as SN 2004dt, it has difficulties in reproducing the low polarization levels commonly observed in normal Type Ia supernovae. Specifically, we find that significant asymmetries in the element distribution result in a wealth of strong polarization features that are not observed in the majority of currently available spectropolarimetric data of Type Ia supernovae. Future studies will map out the parameter space of the merger scenario to investigate if alternative models can provide better agreement with observations.

Testing quasar unification: radiative transfer in clumpy winds

Various unification schemes interpret the complex phenomenology of quasars and luminous active galactic nuclei (AGN) in terms of a simple picture involving a central black hole, an accretion disc and an associated outflow. Here, we continue our tests of this paradigm by comparing quasar spectra to synthetic spectra of biconical disc wind models, produced with our state-of-the-art Monte Carlo radiative transfer code. Previously, we have shown that we could produce synthetic spectra resembling those of observed broad absorption line (BAL) quasars, but only if the X-ray luminosity was limited to 1043 erg s-1. Here, we introduce a simple treatment of clumping, and find that a filling factor of ˜0.01 moderates the ionization state sufficiently for BAL features to form in the rest-frame UV at more realistic X-ray luminosities. Our fiducial model shows good agreement with AGN X-ray properties and the wind produces strong line emission in, e.g., Lyα and C IV 1550 Å at low inclinations. At high inclinations, the spectra possess prominent LoBAL features. Despite these successes, we cannot reproduce all emission lines seen in quasar spectra with the correct equivalent-width ratios, and we find an angular dependence of emission line equivalent width despite the similarities in the observed emission line properties of BAL and non-BAL quasars. Overall, our work suggests that biconical winds can reproduce much of the qualitative behaviour expected from a unified model, but we cannot yet provide quantitative matches with quasar properties at all viewing angles. Whether disc winds can successfully unify quasars is therefore still an open question.

The peculiar Type Ia supernova iPTF14atg: Chandrasekhar-mass explosion or violent merger?

iPTF14atg, a subluminous peculiar Type Ia supernova (SN Ia) similar to SN 2002es, is the first SN Ia for which a strong UV flash was observed in the early-time light curves. This has been interpreted as evidence for a single-degenerate (SD) progenitor system, where such a signal is expected from interactions between the SN ejecta and the non-degenerate companion star. Here, we compare synthetic observables of multidimensional state-of-the-art explosion models for different progenitor scenarios to the light curves and spectra of iPTF14atg. From our models, we have difficulties explaining the spectral evolution of iPTF14atg within the SD progenitor channel. In contrast, we find that a violent merger of two carbon-oxygen white dwarfs with 0.9 and 0.76 M⊙, respectively, provides an excellent match to the spectral evolution of iPTF14atg from 10 d before to several weeks after maximum light. Our merger model does not naturally explain the initial UV flash of iPTF14atg. We discuss several possibilities like interactions of the SN ejecta with the circumstellar medium and surface radioactivity from an He-ignited merger that may be able to account for the early UV emission in violent merger models.

Predicting polarization signatures for double-detonation and delayed-detonation models of Type Ia supernovae

Calculations of synthetic spectropolarimetry are one means to test multidimensional explosion models for Type Ia supernovae. In a recent paper, we demonstrated that the violent merger of a 1.1 and 0.9 M⊙ white dwarf binary system is too asymmetric to explain the low polarization levels commonly observed in normal Type Ia supernovae. Here, we present polarization simulations for two alternative scenarios: the sub-Chandrasekhar mass double-detonation and the Chandrasekhar mass delayed-detonation model. Specifically, we study a 2D double-detonation model and a 3D delayed-detonation model, and calculate polarization spectra for multiple observer orientations in both cases. We find modest polarization levels (<1 per cent) for both explosion models. Polarization in the continuum peaks at ∼0.1–0.3 per cent and decreases after maximum light, in excellent agreement with spectropolarimetric data of normal Type Ia supernovae. Higher degrees of polarization are found across individual spectral lines. In particular, the synthetic Si II λ6355 profiles are polarized at levels that match remarkably well the values observed in normal Type Ia supernovae, while the low degrees of polarization predicted across the O I λ7774 region are consistent with the non-detection of this feature in current data. We conclude that our models can reproduce many of the characteristics of both flux and polarization spectra for well-studied Type Ia supernovae, such as SN 2001el and SN 2012fr. However, the two models considered here cannot account for the unusually high level of polarization observed in extreme cases such as SN 2004dt.

Three-dimensional simulations of gravitationally confined detonations compared to observations of SN 1991T

The gravitationally confined detonation (GCD) model has been proposed as a possible explosion mechanism for Type Ia supernovae in the single-degenerate evolution channel. It starts with ignition of a deflagration in a single off-centre bubble in a near-Chandrasekhar-mass white dwarf. Driven by buoyancy, the deflagration flame rises in a narrow cone towards the surface. For the most part, the main component of the flow of the expanding ashes remains radial, but upon reaching the outer, low-pressure layers of the white dwarf, an additional lateral component develops. This causes the deflagration ashes to converge again at the opposite side, where the compression heats fuel and a detonation may be launched. We first performed five three-dimensional hydrodynamic simulations of the deflagration phase in 1.4 M⊙ carbon/oxygen white dwarfs at intermediate-resolution (2563computational zones). We confirm that the closer the initial deflagration is ignited to the centre, the slower the buoyant rise and the longer the deflagration ashes takes to break out and close in on the opposite pole to collide. To test the GCD explosion model, we then performed a high-resolution (5123 computational zones) simulation for a model with an ignition spot offset near the upper limit of what is still justifiable, 200 km. This high-resolution simulation met our deliberately optimistic detonation criteria, and we initiated a detonation. The detonation burned through the white dwarf and led to its complete disruption. For this model, we determined detailed nucleosynthetic yields by post-processing 106 tracer particles with a 384 nuclide reaction network, and we present multi-band light curves and time-dependent optical spectra. We find that our synthetic observables show a prominent viewing-angle sensitivity in ultraviolet and blue wavelength bands, which contradicts observed SNe Ia. The strong dependence on the viewing angle is caused by the asymmetric distribution of the deflagration ashes in the outer ejecta layers. Finally, we compared our model to SN 1991T. The overall flux level of the model is slightly too low, and the model predicts pre-maximum light spectral features due to Ca, S, and Si that are too strong. Furthermore, the model chemical abundance stratification qualitatively disagrees with recent abundance tomography results in two key areas: our model lacks low-velocity stable Fe and instead has copious amounts of high-velocity 56Ni and stable Fe. We therefore do not find good agreement of the model with SN 1991T.

TRIPPy: Trailed Image Photometry in Python

Photometry of moving sources typically suffers from a reduced signal-to-noise ratio (S/N) or flux measurements biased to incorrect low values through the use of circular apertures. To address this issue, we present the software package, TRIPPy: TRailed Image Photometry in Python. TRIPPy introduces the pill aperture, which is the natural extension of the circular aperture appropriate for linearly trailed sources. The pill shape is a rectangle with two semicircular end-caps and is described by three parameters, the trail length and angle, and the radius. The TRIPPy software package also includes a new technique to generate accurate model point-spread functions (PSFs) and trailed PSFs (TSFs) from stationary background sources in sidereally tracked images. The TSF is merely the convolution of the model PSF, which consists of a moffat profile, and super-sampled lookup table. From the TSF, accurate pill aperture corrections can be estimated as a function of pill radius with an accuracy of 10 mmag for highly trailed sources. Analogous to the use of small circular apertures and associated aperture corrections, small radius pill apertures can be used to preserve S/Ns of low flux sources, with appropriate aperture correction applied to provide an accurate, unbiased flux measurement at all S/Ns.

Algorithme de branch-and-price-and-cut pour le problème de conception de réseaux avec coûts fixes, capacités et un seul produit

De nombreux problèmes liés aux domaines du transport, des télécommunications et de la logistique peuvent être modélisés comme des problèmes de conception de réseaux. Le problème classique consiste à transporter un flot (données, personnes, produits, etc.) sur un réseau sous un certain nombre de contraintes dans le but de satisfaire la demande, tout en minimisant les coûts. Dans ce mémoire, on se propose d'étudier le problème de conception de réseaux avec coûts fixes, capacités et un seul produit, qu'on transforme en un problème équivalent à plusieurs produits de façon à améliorer la valeur de la borne inférieure provenant de la relaxation continue du modèle. La méthode que nous présentons pour la résolution de ce problème est une méthode exacte de branch-and-price-and-cut avec une condition d'arrêt, dans laquelle nous exploitons à la fois la méthode de génération de colonnes, la méthode de génération de coupes et l'algorithme de branch-and-bound. Ces méthodes figurent parmi les techniques les plus utilisées en programmation linéaire en nombres entiers. Nous testons notre méthode sur deux groupes d'instances de tailles différentes (gran-des et très grandes), et nous la comparons avec les résultats donnés par CPLEX, un des meilleurs logiciels permettant de résoudre des problèmes d'optimisation mathématique, ainsi qu’avec une méthode de branch-and-cut. Il s'est avéré que notre méthode est prometteuse et peut donner de bons résultats, en particulier pour les instances de très grandes tailles.

Numerical methods for the variable-order fractional advection-diffusion equation with a nonlinear source term

In this paper, we consider a variable-order fractional advection-diffusion equation with a nonlinear source term on a finite domain. Explicit and implicit Euler approximations for the equation are proposed. Stability and convergence of the methods are discussed. Moreover, we also present a fractional method of lines, a matrix transfer technique, and an extrapolation method for the equation. Some numerical examples are given, and the results demonstrate the effectiveness of theoretical analysis.

Numerical methods for fractional partial differential equations with Riesz space fractional derivatives

In this paper, we consider the numerical solution of a fractional partial differential equation with Riesz space fractional derivatives (FPDE-RSFD) on a finite domain. Two types of FPDE-RSFD are considered: the Riesz fractional diffusion equation (RFDE) and the Riesz fractional advection–dispersion equation (RFADE). The RFDE is obtained from the standard diffusion equation by replacing the second-order space derivative with the Riesz fractional derivative of order αset membership, variant(1,2]. The RFADE is obtained from the standard advection–dispersion equation by replacing the first-order and second-order space derivatives with the Riesz fractional derivatives of order βset membership, variant(0,1) and of order αset membership, variant(1,2], respectively. Firstly, analytic solutions of both the RFDE and RFADE are derived. Secondly, three numerical methods are provided to deal with the Riesz space fractional derivatives, namely, the L1/L2-approximation method, the standard/shifted Grünwald method, and the matrix transform method (MTM). Thirdly, the RFDE and RFADE are transformed into a system of ordinary differential equations, which is then solved by the method of lines. Finally, numerical results are given, which demonstrate the effectiveness and convergence of the three numerical methods.

Numerical investigations of linear least squares methods for derivative estimation

The results of a numerical investigation into the errors for least squares estimates of function gradients are presented. The underlying algorithm is obtained by constructing a least squares problem using a truncated Taylor expansion. An error bound associated with this method contains in its numerator terms related to the Taylor series remainder, while its denominator contains the smallest singular value of the least squares matrix. Perhaps for this reason the error bounds are often found to be pessimistic by several orders of magnitude. The circumstance under which these poor estimates arise is elucidated and an empirical correction of the theoretical error bounds is conjectured and investigated numerically. This is followed by an indication of how the conjecture is supported by a rigorous argument.

Study of wheel-rail impact at insulated rail joint through experimental and numerical methods

As part of an ongoing research on the development of a longer life insulated rail joint (IRJ), this paper reports a field experiment and a simplified 2D numerical modelling for the purpose of investigating the behaviour of rail web in the vicinity of endpost in an insulated rail joint (IRJ) due to wheel passages. A simplified 2D plane stress finite element model is used to simulate the wheel-rail rolling contact impact at IRJ. This model is validated using data from a strain gauged IRJ that was installed in a heavy haul network; data in terms of the vertical and shear strains at specific positions of the IRJ during train passing were captured and compared with the results of the FE model. The comparison indicates a satisfactory agreement between the FE model and the field testing. Furthermore, it demonstrates that the experimental and numerical analyses reported in this paper provide a valuable datum for developing further insight into the behaviour of IRJ under wheel impacts.

Novel analytical and numerical methods for solving fractional dynamical systems

During the past three decades, the subject of fractional calculus (that is, calculus of integrals and derivatives of arbitrary order) has gained considerable popularity and importance, mainly due to its demonstrated applications in numerous diverse and widespread fields in science and engineering. For example, fractional calculus has been successfully applied to problems in system biology, physics, chemistry and biochemistry, hydrology, medicine, and finance. In many cases these new fractional-order models are more adequate than the previously used integer-order models, because fractional derivatives and integrals enable the description of the memory and hereditary properties inherent in various materials and processes that are governed by anomalous diffusion. Hence, there is a growing need to find the solution behaviour of these fractional differential equations. However, the analytic solutions of most fractional differential equations generally cannot be obtained. As a consequence, approximate and numerical techniques are playing an important role in identifying the solution behaviour of such fractional equations and exploring their applications. The main objective of this thesis is to develop new effective numerical methods and supporting analysis, based on the finite difference and finite element methods, for solving time, space and time-space fractional dynamical systems involving fractional derivatives in one and two spatial dimensions. A series of five published papers and one manuscript in preparation will be presented on the solution of the space fractional diffusion equation, space fractional advectiondispersion equation, time and space fractional diffusion equation, time and space fractional Fokker-Planck equation with a linear or non-linear source term, and fractional cable equation involving two time fractional derivatives, respectively. One important contribution of this thesis is the demonstration of how to choose different approximation techniques for different fractional derivatives. Special attention has been paid to the Riesz space fractional derivative, due to its important application in the field of groundwater flow, system biology and finance. We present three numerical methods to approximate the Riesz space fractional derivative, namely the L1/ L2-approximation method, the standard/shifted Gr¨unwald method, and the matrix transform method (MTM). The first two methods are based on the finite difference method, while the MTM allows discretisation in space using either the finite difference or finite element methods. Furthermore, we prove the equivalence of the Riesz fractional derivative and the fractional Laplacian operator under homogeneous Dirichlet boundary conditions – a result that had not previously been established. This result justifies the aforementioned use of the MTM to approximate the Riesz fractional derivative. After spatial discretisation, the time-space fractional partial differential equation is transformed into a system of fractional-in-time differential equations. We then investigate numerical methods to handle time fractional derivatives, be they Caputo type or Riemann-Liouville type. This leads to new methods utilising either finite difference strategies or the Laplace transform method for advancing the solution in time. The stability and convergence of our proposed numerical methods are also investigated. Numerical experiments are carried out in support of our theoretical analysis. We also emphasise that the numerical methods we develop are applicable for many other types of fractional partial differential equations.