Equivalence of piecewise-linear approximation and Lagrangian relaxation for network revenue management

The network revenue management (RM) problem arises in airline, hotel, media,and other industries where the sale products use multiple resources. It can be formulatedas a stochastic dynamic program but the dynamic program is computationallyintractable because of an exponentially large state space, and a number of heuristicshave been proposed to approximate it. Notable amongst these -both for their revenueperformance, as well as their theoretically sound basis- are approximate dynamic programmingmethods that approximate the value function by basis functions (both affinefunctions as well as piecewise-linear functions have been proposed for network RM)and decomposition methods that relax the constraints of the dynamic program to solvesimpler dynamic programs (such as the Lagrangian relaxation methods). In this paperwe show that these two seemingly distinct approaches coincide for the network RMdynamic program, i.e., the piecewise-linear approximation method and the Lagrangianrelaxation method are one and the same.

An enhanced concave program relaxation for choice network revenue management

The network choice revenue management problem models customers as choosing from an offer-set, andthe firm decides the best subset to offer at any given moment to maximize expected revenue. The resultingdynamic program for the firm is intractable and approximated by a deterministic linear programcalled the CDLP which has an exponential number of columns. However, under the choice-set paradigmwhen the segment consideration sets overlap, the CDLP is difficult to solve. Column generation has beenproposed but finding an entering column has been shown to be NP-hard. In this paper, starting with aconcave program formulation based on segment-level consideration sets called SDCP, we add a class ofconstraints called product constraints, that project onto subsets of intersections. In addition we proposea natural direct tightening of the SDCP called ?SDCP, and compare the performance of both methodson the benchmark data sets in the literature. Both the product constraints and the ?SDCP method arevery simple and easy to implement and are applicable to the case of overlapping segment considerationsets. In our computational testing on the benchmark data sets in the literature, SDCP with productconstraints achieves the CDLP value at a fraction of the CPU time taken by column generation and webelieve is a very promising approach for quickly approximating CDLP when segment consideration setsoverlap and the consideration sets themselves are relatively small.

Analysis by optical absorption and transmission electron microscopy of the strain inhomogeneities in InGaAs/InP strained layers

Optical absorption spectra and transmission electron microscopy (TEM) observations on InGaAs/InP layers under compressive strain are reported. From the band¿gap energy dispersion, the magnitude of the strain inhomogeneities. Is quantified and its microscopic origin is analyzed in view of the layer microstructure. TEM observations reveal a dislocation network at the layer interface the density of which correlates with ¿¿. It is concluded that local variations of dislocation density are responsible for the inhomogeneous strain field together with another mechanism that dominates when the dislocation density is very low.

Strain-induced stabilization of new magnetic spinel structures in epitaxial oxide heterostructures.

We report here on the growth of NiFe2O4 epitaxial thin films of different thickness (3 nm ¿ t ¿ 32 nm) on single crystalline substrates having spinel (MgAl2O4) or perovskite (SrTiO3) structure. Ultrathin films, grown on any of those substrates, display a huge enhancement of the saturation magnetization: we will show that partial cationic inversion may account for this enhancement, although we will argue that suppression of antiparallel collinear spin alignment due to size-effects cannot be excluded. Besides, for thicker films, the magnetization of films on MAO is found to be similar to that of bulk ferrite; in contrast, the magnetization of films on STO is substantially lower than bulk. We discuss on the possible mechanisms leading to this remarkable difference of magnetization.

Relaxation times of non-Markovian processes

We consider a general class of non-Markovian processes defined by stochastic differential equations with Ornstein-Uhlenbeck noise. We present a general formalism to evaluate relaxation times associated with correlation functions in the steady state. This formalism is a generalization of a previous approach for Markovian processes. The theoretical results are shown to be in satisfactory agreement both with experimental data for a cubic bistable system and also with a computer simulation of the Stratonovich model. We comment on the dynamical role of the non-Markovianicity in different situations.

Relaxation time of processes driven by multiplicative noise

We consider systems described by nonlinear stochastic differential equations with multiplicative noise. We study the relaxation time of the steady-state correlation function as a function of noise parameters. We consider the white- and nonwhite-noise case for a prototype model for which numerical data are available. We discuss the validity of analytical approximation schemes. For the white-noise case we discuss the results of a projector-operator technique. This discussion allows us to give a generalization of the method to the non-white-noise case. Within this generalization, we account for the growth of the relaxation time as a function of the correlation time of the noise. This behavior is traced back to the existence of a non-Markovian term in the equation for the correlation function.

Relaxation times in a bistable system with parametric, white noise: Theory and experiment

We consider the effects of external, multiplicative white noise on the relaxation time of a general representation of a bistable system from the points of view provided by two, quite different, theoretical approaches: the classical Stratonovich decoupling of correlations and the new method due to Jung and Risken. Experimental results, obtained from a bistable electronic circuit, are compared to the theoretical predictions. We show that the phenomenon of critical slowing down appears as a function of the noise parameters, thereby providing a correct characterization of a noise-induced transition.

Relaxation from a marginal state in optical bistability

Characteristic decay times for relaxation close to the marginal point of optical bistability are studied. A model-independent formula for the decay time is given which interpolates between Kramers time for activated decay and a deterministic relaxation time. This formula gives the decay time as a universal scaling function of the parameter which measures deviation from marginality. The standard deviation of the first-passage-time distribution is found to vary linearly with the decay time, close to marginality, with a slope independent of the noise intensity. Our results are substantiated by numerical simulations and their experimental relevance is pointed out.

Transient and preparation colored-noise effects: The nonlinear relaxation-time approach

We develop a singular perturbation approach to the problem of the calculation of a characteristic time (the nonlinear relaxation time) for non-Markovian processes driven by Gaussian colored noise with small correlation time. Transient and initial preparation effects are discussed and explicit results for prototype situations are obtained. New effects on the relaxation of unstable states are predicted. The approach is compared with previous techniques.

Decay of unstable states in the presence of colored noise and random initial conditions. I. Theory of nonlinear relaxation times

The general theory of nonlinear relaxation times is developed for the case of Gaussian colored noise. General expressions are obtained and applied to the study of the characteristic decay time of unstable states in different situations, including white and colored noise, with emphasis on the distributed initial conditions. Universal effects of the coupling between colored noise and random initial conditions are predicted.

Selection, shape and relaxation of fronts: A numerical study of the effects of inertia.

We study the problem of front propagation in the presence of inertia. We extend the analytical approach for the overdamped problem to this case, and present numerical results to support our theoretical predictions. Specifically, we conclude that the velocity and shape selection problem can still be described in terms of the metastable, nonlinear, and linear overdamped regimes. We study the characteristic relaxation dynamics of these three regimes, and the existence of degenerate (¿quenched¿) solutions.