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.

Pavement Management Performance Modeling: Evaluating the Existing PCI Equations, RB14-013 2014

The work described in this report documents the activities performed for the evaluation, development, and enhancement of the Iowa Department of Transportation (DOT) pavement condition information as part of their pavement management system operation. The study covers all of the Iowa DOT’s interstate and primary National Highway System (NHS) and non-NHS system. A new pavement condition rating system that provides a consistent, unified approach in rating pavements in Iowa is being proposed. The proposed 100-scale system is based on five individual indices derived from specific distress data and pavement properties, and an overall pavement condition index, PCI-2, that combines individual indices using weighting factors. The different indices cover cracking, ride, rutting, faulting, and friction. The Cracking Index is formed by combining cracking data (transverse, longitudinal, wheel-path, and alligator cracking indices). Ride, rutting, and faulting indices utilize the International Roughness Index (IRI), rut depth, and fault height, respectively.

SAT Modulo Linear Arithmetic for Solving Polynomial

Polynomial constraint solving plays a prominent role in several areas of hardware and software analysis and verification, e.g., termination proving, program invariant generation and hybrid system verification, to name a few. In this paper we propose a new method for solving non-linear constraints based on encoding the problem into an SMT problem considering only linear arithmetic. Unlike other existing methods, our method focuses on proving satisfiability of the constraints rather than on proving unsatisfiability, which is more relevant in several applications as we illustrate with several examples. Nevertheless, we also present new techniques based on the analysis of unsatisfiable cores that allow one to efficiently prove unsatisfiability too for a broad class of problems. The power of our approach is demonstrated by means of extensive experiments comparing our prototype with state-of-the-art tools on benchmarks taken both from the academic and the industrial world.

Generation and nonlinear evolution of shore-oblique/transverse sand bars

The coupling between topography, waves and currents in the surf zone may selforganize to produce the formation of shore-transverse or shore-oblique sand bars on an otherwise alongshore uniform beach. In the absence of shore-parallel bars, this has been shown by previous studies of linear stability analysis, but is now extended to the finite-amplitude regime. To this end, a nonlinear model coupling wave transformation and breaking, a shallow-water equations solver, sediment transport and bed updating is developed. The sediment flux consists of a stirring factor multiplied by the depthaveraged current plus a downslope correction. It is found that the cross-shore profile of the ratio of stirring factor to water depth together with the wave incidence angle primarily determine the shape and the type of bars, either transverse or oblique to the shore. In the latter case, they can open an acute angle against the current (upcurrent oriented) or with the current (down-current oriented). At the initial stages of development, both the intensity of the instability which is responsible for the formation of the bars and the damping due to downslope transport grow at a similar rate with bar amplitude, the former being somewhat stronger. As bars keep on growing, their finite-amplitude shape either enhances downslope transport or weakens the instability mechanism so that an equilibrium between both opposing tendencies occurs, leading to a final saturated amplitude. The overall shape of the saturated bars in plan view is similar to that of the small-amplitude ones. However, the final spacings may be up to a factor of 2 larger and final celerities can also be about a factor of 2 smaller or larger. In the case of alongshore migrating bars, the asymmetry of the longshore sections, the lee being steeper than the stoss, is well reproduced. Complex dynamics with merging and splitting of individual bars sometimes occur. Finally, in the case of shore-normal incidence the rip currents in the troughs between the bars are jet-like while the onshore return flow is wider and weaker as is observed in nature.

Maximum likelihood Linear Programming Data Fusion for Speaker Recognition

Biometric system performance can be improved by means of data fusion. Several kinds of information can be fused in order to obtain a more accurate classification (identification or verification) of an input sample. In this paper we present a method for computing the weights in a weighted sum fusion for score combinations, by means of a likelihood model. The maximum likelihood estimation is set as a linear programming problem. The scores are derived from a GMM classifier working on a different feature extractor. Our experimental results assesed the robustness of the system in front a changes on time (different sessions) and robustness in front a change of microphone. The improvements obtained were significantly better (error bars of two standard deviations) than a uniform weighted sum or a uniform weighted product or the best single classifier. The proposed method scales computationaly with the number of scores to be fussioned as the simplex method for linear programming.

Non-Linear and Non-Conventional Speech Processing: Alternative Techniques

This special issue aims to cover some problems related to non-linear and nonconventional speech processing. The origin of this volume is in the ISCA Tutorial and Research Workshop on Non-Linear Speech Processing, NOLISP’09, held at the Universitat de Vic (Catalonia, Spain) on June 25–27, 2009. The series of NOLISP workshops started in 2003 has become a biannual event whose aim is to discuss alternative techniques for speech processing that, in a sense, do not fit into mainstream approaches. A selected choice of papers based on the presentations delivered at NOLISP’09 has given rise to this issue of Cognitive Computation.

A Canonical Genetic Algorithm for Blind Inversion of Linear Channels

It is well known the relationship between source separation and blind deconvolution: If a filtered version of an unknown i.i.d. signal is observed, temporal independence between samples can be used to retrieve the original signal, in the same manner as spatial independence is used for source separation. In this paper we propose the use of a Genetic Algorithm (GA) to blindly invert linear channels. The use of GA is justified in the case of small number of samples, where other gradient-like methods fails because of poor estimation of statistics.

On the approximation of the subgrid scale for systems of equations

Postprint (published version)

On periodic solutions of 2-periodic Lyness difference equations

We study the existence of periodic solutions of the non--autonomous periodic Lyness' recurrence u_{n+2}=(a_n+u_{n+1})/u_n, where {a_n} is a cycle with positive values a,b and with positive initial conditions. It is known that for a=b=1 all the sequences generated by this recurrence are 5-periodic. We prove that for each pair (a,b) different from (1,1) there are infinitely many initial conditions giving rise to periodic sequences, and that the family of recurrences have almost all the even periods. If a is not equal to b, then any odd period, except 1, appears.

A non-linear Bayesian approach for upscaling local-scale hydraulic conductivity measurements based on local- and regional-scale geophysical data

Significant progress has been made with regard to the quantitative integration of geophysical and hydrological data at the local scale. However, extending the corresponding approaches to the regional scale represents a major, and as-of-yet largely unresolved, challenge. To address this problem, we have developed an upscaling procedure based on a Bayesian sequential simulation approach. This method is then applied to the stochastic integration of low-resolution, regional-scale electrical resistivity tomography (ERT) data in combination with high-resolution, local-scale downhole measurements of the hydraulic and electrical conductivities. Finally, the overall viability of this upscaling approach is tested and verified by performing and comparing flow and transport simulation through the original and the upscaled hydraulic conductivity fields. Our results indicate that the proposed procedure does indeed allow for obtaining remarkably faithful estimates of the regional-scale hydraulic conductivity structure and correspondingly reliable predictions of the transport characteristics over relatively long distances.

Short-term stability of testosterone and epitestosterone conjugates in urine samples: quantification by liquid chromatography-linear ion trap mass spectrometry.

A simple method using liquid chromatography-linear ion trap mass spectrometry for simultaneous determination of testosterone glucuronide (TG), testosterone sulfate (TS), epitestosterone glucuronide (EG) and epitestosterone sulfate (ES) in urine samples was developed. For validation purposes, a urine containing no detectable amount of TG, TS and EG was selected and fortified with steroid conjugate standards. Quantification was performed using deuterated testosterone conjugates to correct for ion suppression/enhancement during ESI. Assay validation was performed in terms of lower limit of detection (1-3ng/mL), recovery (89-101%), intraday precision (2.0-6.8%), interday precision (3.4-9.6%) and accuracy (101-103%). Application of the method to short-term stability testing of urine samples at temperature ranging from 4 to 37 degrees C during a time-storage of a week lead to the conclusion that addition of sodium azide (10mg/mL) is required for preservation of the analytes.

Simulating maize phenology as a function of air temperature with a linear and a nonlinear model

The objective of this study was to adapt a nonlinear model (Wang and Engel - WE) for simulating the phenology of maize (Zea mays L.), and to evaluate this model and a linear one (thermal time), in order to predict developmental stages of a field-grown maize variety. A field experiment, during 2005/2006 and 2006/2007 was conducted in Santa Maria, RS, Brazil, in two growing seasons, with seven sowing dates each. Dates of emergence, silking, and physiological maturity of the maize variety BRS Missões were recorded in six replications in each sowing date. Data collected in 2005/2006 growing season were used to estimate the coefficients of the two models, and data collected in the 2006/2007 growing season were used as independent data set for model evaluations. The nonlinear WE model accurately predicted the date of silking and physiological maturity, and had a lower root mean square error (RMSE) than the linear (thermal time) model. The overall RMSE for silking and physiological maturity was 2.7 and 4.8 days with WE model, and 5.6 and 8.3 days with thermal time model, respectively.

Análise genética de escores de avaliação visual de bovinos com modelos bayesianos de limiar e linear

O objetivo deste trabalho foi comparar as estimativas de parâmetros genéticos obtidas em análises bayesianas uni-característica e bi-característica, em modelo animal linear e de limiar, considerando-se as características categóricas morfológicas de bovinos da raça Nelore. Os dados de musculosidade, estrutura física e conformação foram obtidos entre 2000 e 2005, em 3.864 animais de 13 fazendas participantes do Programa Nelore Brasil. Foram realizadas análises bayesianas uni e bi-características, em modelos de limiar e linear. De modo geral, os modelos de limiar e linear foram eficientes na estimação dos parâmetros genéticos para escores visuais em análises bayesianas uni-características. Nas análises bi-características, observou-se que: com utilização de dados contínuos e categóricos, o modelo de limiar proporcionou estimativas de correlação genética de maior magnitude do que aquelas do modelo linear; e com o uso de dados categóricos, as estimativas de herdabilidade foram semelhantes. A vantagem do modelo linear foi o menor tempo gasto no processamento das análises. Na avaliação genética de animais para escores visuais, o uso do modelo de limiar ou linear não influenciou a classificação dos animais, quanto aos valores genéticos preditos, o que indica que ambos os modelos podem ser utilizados em programas de melhoramento genético.

Kinetic equations for difussion in the presence of entropic barriers

We use the mesoscopic nonequilibrium thermodynamics theory to derive the general kinetic equation of a system in the presence of potential barriers. The result is applied to a description of the evolution of systems whose dynamics is influenced by entropic barriers. We analyze in detail the case of diffusion in a domain of irregular geometry in which the presence of the boundaries induces an entropy barrier when approaching the exact dynamics by a coarsening of the description. The corresponding kinetic equation, named the Fick-Jacobs equation, is obtained, and its validity is generalized through the formulation of a scaling law for the diffusion coefficient which depends on the shape of the boundaries. The method we propose can be useful to analyze the dynamics of systems at the nanoscale where the presence of entropy barriers is a common feature.