On the tractability of the piecewise-linear approximation for general discrete-choice network revenue management

The choice network revenue management (RM) model incorporates customer purchase behavioras customers purchasing products with certain probabilities that are a function of the offeredassortment of products, and is the appropriate model for airline and hotel network revenuemanagement, dynamic sales of bundles, and dynamic assortment optimization. The underlyingstochastic dynamic program is intractable and even its certainty-equivalence approximation, inthe form of a linear program called Choice Deterministic Linear Program (CDLP) is difficultto solve in most cases. The separation problem for CDLP is NP-complete for MNL with justtwo segments when their consideration sets overlap; the affine approximation of the dynamicprogram is NP-complete for even a single-segment MNL. This is in contrast to the independentclass(perfect-segmentation) case where even the piecewise-linear approximation has been shownto be tractable. In this paper we investigate the piecewise-linear approximation for network RMunder a general discrete-choice model of demand. We show that the gap between the CDLP andthe piecewise-linear bounds is within a factor of at most 2. We then show that the piecewiselinearapproximation is polynomially-time solvable for a fixed consideration set size, bringing itinto the realm of tractability for small consideration sets; small consideration sets are a reasonablemodeling tradeoff in many practical applications. Our solution relies on showing that forany discrete-choice model the separation problem for the linear program of the piecewise-linearapproximation can be solved exactly by a Lagrangian relaxation. We give modeling extensionsand show by numerical experiments the improvements from using piecewise-linear approximationfunctions.

Fast Approximation of Nonlinearities for improving inversion algorithms of PNL mixtures and Wiener systems

This paper proposes a very fast method for blindly approximating a nonlinear mapping which transforms a sum of random variables. The estimation is surprisingly good even when the basic assumption is not satisfied.We use the method for providing a good initialization for inverting post-nonlinear mixtures and Wiener systems. Experiments show that the algorithm speed is strongly improved and the asymptotic performance is preserved with a very low extra computational cost.

Validity of the acoustic approximation in full-waveform seismic crosshole tomography

Acoustic waveform inversions are an increasingly popular tool for extracting subsurface information from seismic data. They are computationally much more efficient than elastic inversions. Naturally, an inherent disadvantage is that any elastic effects present in the recorded data are ignored in acoustic inversions. We investigate the extent to which elastic effects influence seismic crosshole data. Our numerical modeling studies reveal that in the presence of high contrast interfaces, at which P-to-S conversions occur, elastic effects can dominate the seismic sections, even for experiments involving pressure sources and pressure receivers. Comparisons of waveform inversion results using a purely acoustic algorithm on synthetic data that is either acoustic or elastic, show that subsurface models comprising small low-to-medium contrast (?30%) structures can be successfully resolved in the acoustic approximation. However, in the presence of extended high-contrast anomalous bodies, P-to-S-conversions may substantially degrade the quality of the tomographic images. In particular, extended low-velocity zones are difficult to image. Likewise, relatively small low-velocity features are unresolved, even when advanced a priori information is included. One option for mitigating elastic effects is data windowing, which suppresses later arriving seismic arrivals, such as shear waves. Our tests of this approach found it to be inappropriate because elastic effects are also included in earlier arriving wavetrains. Furthermore, data windowing removes later arriving P-wave phases that may provide critical constraints on the tomograms. Finally, we investigated the extent to which acoustic inversions of elastic data are useful for time-lapse analyses of high contrast engineered structures, for which accurate reconstruction of the subsurface structure is not as critical as imaging differential changes between sequential experiments. Based on a realistic scenario for monitoring a radioactive waste repository, we demonstrated that acoustic inversions of elastic data yield substantial distortions of the tomograms and also unreliable information on trends in the velocity changes.

A Fast Gradient Approximation for Nonlinear Blind Signal Processing

When dealing with nonlinear blind processing algorithms (deconvolution or post-nonlinear source separation), complex mathematical estimations must be done giving as a result very slow algorithms. This is the case, for example, in speech processing, spike signals deconvolution or microarray data analysis. In this paper, we propose a simple method to reduce computational time for the inversion of Wiener systems or the separation of post-nonlinear mixtures, by using a linear approximation in a minimum mutual information algorithm. Simulation results demonstrate that linear spline interpolation is fast and accurate, obtaining very good results (similar to those obtained without approximation) while computational time is dramatically decreased. On the other hand, cubic spline interpolation also obtains similar good results, but due to its intrinsic complexity, the global algorithm is much more slow and hence not useful for our purpose.

On the approximation of the subgrid scale for systems of equations

Postprint (published version)

Biased diffusion in confined media: Test of the Fick-Jacobs approximation and validity criteria

We study biased, diffusive transport of Brownian particles through narrow, spatially periodic structures in which the motion is constrained in lateral directions. The problem is analyzed under the perspective of the Fick-Jacobs equation, which accounts for the effect of the lateral confinement by introducing an entropic barrier in a one-dimensional diffusion. The validity of this approximation, based on the assumption of an instantaneous equilibration of the particle distribution in the cross section of the structure, is analyzed by comparing the different time scales that characterize the problem. A validity criterion is established in terms of the shape of the structure and of the applied force. It is analytically corroborated and verified by numerical simulations that the critical value of the force up to which this description holds true scales as the square of the periodicity of the structure. The criterion can be visualized by means of a diagram representing the regions where the Fick-Jacobs description becomes inaccurate in terms of the scaled force versus the periodicity of the structure.

A consistent extension of the local spin density approximation to account for quantum dot mass and dielectric mismatches

A consistent extension of local spin density approximation (LSDA) to account for mass and dielectric mismatches in nanocrystals is presented. The extension accounting for variable effective mass is exact. Illustrative comparisons with available configuration interaction calculations show that the approach is also very reliable when it comes to account for dielectric mismatches. The modified LSDA is as fast and computationally low demanding as LSDA. Therefore, it is a tool suitable to study large particle systems in inhomogeneous media without much effort.

Reliability of the density functional approximation to describe the charge transfer and electrostatic complexes involved in the modeling of organic conducting polymers

Both the intermolecular interaction energies and the geometries for M ̄ thiophene, M ̄ pyrrole, M n+ ̄ thiophene, and M n+ ̄ pyrrole ͑with M = Li, Na, K, Ca, and Mg; and M n+ = Li+ , Na+ , K+ , Ca2+, and Mg2+͒ have been estimated using four commonly used density functional theory ͑DFT͒ methods: B3LYP, B3PW91, PBE, and MPW1PW91. Results have been compared to those provided by HF, MP2, and MP4 conventional ab initio methods. The PBE and MPW1PW91 are the only DFT methods able to provide a reasonable description of the M ̄ complexes. Regarding M n+ ̄ ␲ complexes, the four DFT methods have been proven to be adequate in the prediction of these electrostatically stabilized systems, even though they tend to overestimate the interaction energies.

Microscopic-macroscopic approach for binding energies with the Wigner-Kirkwood method. II. Deformed nuclei

The binding energies of deformed even-even nuclei have been analyzed within the framework of a recently proposed microscopic-macroscopic model. We have used the semiclassical Wigner-Kirkwood ̄h expansion up to fourth order, instead of the usual Strutinsky averaging scheme, to compute the shell corrections in a deformed Woods-Saxon potential including the spin-orbit contribution. For a large set of 561 even-even nuclei with Z 8 and N 8, we find an rms deviation from the experiment of 610 keV in binding energies, comparable to the one found for the same set of nuclei using the finite range droplet model of Moller and Nix (656 keV). As applications of our model, we explore its predictive power near the proton and neutron drip lines as well as in the superheavy mass region. Next, we systematically explore the fourth-order Wigner-Kirkwood corrections to the smooth part of the energy. It is found that the ratio of the fourth-order to the second-order corrections behaves in a very regular manner as a function of the asymmetry parameter I=(N−Z)/A. This allows us to absorb the fourth-order corrections into the second-order contributions to the binding energy, which enables us us to simplify and speed up the calculation of deformed nuclei.

Microscopic-macroscopic approach for binding energies with the Wigner-Kirkwood method

The semiclassical Wigner-Kirkwood ̄h expansion method is used to calculate shell corrections for spherical and deformed nuclei. The expansion is carried out up to fourth order in ̄h. A systematic study of Wigner-Kirkwood averaged energies is presented as a function of the deformation degrees of freedom. The shell corrections, along with the pairing energies obtained by using the Lipkin-Nogami scheme, are used in the microscopic-macroscopic approach to calculate binding energies. The macroscopic part is obtained from a liquid drop formula with six adjustable parameters. Considering a set of 367 spherical nuclei, the liquid drop parameters are adjusted to reproduce the experimental binding energies, which yields a root mean square (rms) deviation of 630 keV. It is shown that the proposed approach is indeed promising for the prediction of nuclear masses.

The octagon, the hendecagon and the approximation of pi: the geometric design of the clypeus in the enclosure of Imperial cult in Tarraco

The ancient temple dedicated to the Roman Emperor Augustus on the hilltop of Tarraco (today’s Tarragona), was the main element of the sacred precinct of the Imperial cult. It was a two hectare square, bordered by a portico with an attic decorated with a sequence of clypeus (i.e. monumental shields) made with marble plates from the Luni-Carrara’s quarries. This contribution presents the results of the analysis of a three-dimensional photogrammetric survey of one of these clipeus, partially restored and exhibited at the National Archaeological Museum of Tarragona. The perimeter ring was bounded by a sequence of meanders inscribed in a polygon of 11 sides, a hendecagon. Moreover, a closer geometric analysis suggests that the relationship between the outer meander rim and the oval pearl ring that delimited the divinity of Jupiter Ammon can be accurately determined by the diagonals of an octagon inscribed in the perimeter of the clypeus. This double evidence suggests a combined layout, in the same design, of an octagon and a hendecagon. Hypothetically, this could be achieved by combining the octagon with the approximation to Pi used in antiquity: 22/7 of the circle’s diameter. This method allows the drawing of a hendecagon with a clearly higher precision than with other ancient methods. Even the modelling of the motifs that separate the different decorative stripes corroborates the geometric scheme that we propose.

The effect of skewness and kurtosis on the Kenward-Roger approximation when group distributions differ

This study examined the independent effect of skewness and kurtosis on the robustness of the linear mixed model (LMM), with the Kenward-Roger (KR) procedure, when group distributions are different, sample sizes are small, and sphericity cannot be assumed. Methods: A Monte Carlo simulation study considering a split-plot design involving three groups and four repeated measures was performed. Results: The results showed that when group distributions are different, the effect of skewness on KR robustness is greater than that of kurtosis for the corresponding values. Furthermore, the pairings of skewness and kurtosis with group size were found to be relevant variables when applying this procedure. Conclusions: With sample sizes of 45 and 60, KR is a suitable option for analyzing data when the distributions are: (a) mesokurtic and not highly or extremely skewed, and (b) symmetric with different degrees of kurtosis. With total sample sizes of 30, it is adequate when group sizes are equal and the distributions are: (a) mesokurtic and slightly or moderately skewed, and sphericity is assumed; and (b) symmetric with a moderate or high/extreme violation of kurtosis. Alternative analyses should be considered when the distributions are highly or extremely skewed and samples sizes are small.

Analytical Dirac-Hartree-Fock-Slater screening function for atoms (Z=1-92)

An analytical approximation, depending on five parameters, for the atomic screening function is proposed. The corresponding electrostatic potential takes a simple analytical form (superposition of three Yukawa potentials) well suited to most practical applications. Parameters in the screening function, determined by an analytical fitting procedure to Dirac-Hartree-Fock-Slater (DHFS) self-consistent data, are given for Z=1¿92. The reliability of this analytical approach is demonstrated by showing that (a) Born cross sections for elastic scattering of fast charged particles by the present analytical field and by the DHFS field practically coincide and (b) one-electron binding energies computed from the independent-particle model with our analytical field (corrected for exchange and electrostatic self-interaction) agree closely with the DHFS energy eigenvalues.