A tractable consideration set structure for network revenue management

Models incorporating more realistic models of customer behavior, as customers choosing from an offerset, have recently become popular in assortment optimization and revenue management. The dynamicprogram for these models is intractable and approximated by a deterministic linear program called theCDLP which has an exponential number of columns. When there are products that are being consideredfor purchase by more than one customer segment, CDLP is difficult to solve since column generationis known to be NP-hard. However, recent research indicates that a formulation based on segments withcuts imposing consistency (SDCP+) is tractable and approximates the CDLP value very closely. In thispaper we investigate the structure of the consideration sets that make the two formulations exactly equal.We show that if the segment consideration sets follow a tree structure, CDLP = SDCP+. We give acounterexample to show that cycles can induce a gap between the CDLP and the SDCP+ relaxation.We derive two classes of valid inequalities called flow and synchronization inequalities to further improve(SDCP+), based on cycles in the consideration set structure. We give a numeric study showing theperformance of these cycle-based cuts.

A new compact linear programming formulation for choice network revenue management

The choice network revenue management model incorporates customer purchase behavioras a function of the offered products, and is the appropriate model for airline and hotel networkrevenue management, dynamic sales of bundles, and dynamic assortment optimization.The optimization problem is a stochastic dynamic program and is intractable. A certainty-equivalencerelaxation of the dynamic program, called the choice deterministic linear program(CDLP) is usually used to generate dyamic controls. Recently, a compact linear programmingformulation of this linear program was given for the multi-segment multinomial-logit (MNL)model of customer choice with non-overlapping consideration sets. Our objective is to obtaina tighter bound than this formulation while retaining the appealing properties of a compactlinear programming representation. To this end, it is natural to consider the affine relaxationof the dynamic program. We first show that the affine relaxation is NP-complete even for asingle-segment MNL model. Nevertheless, by analyzing the affine relaxation we derive a newcompact linear program that approximates the dynamic programming value function betterthan CDLP, provably between the CDLP value and the affine relaxation, and often comingclose to the latter in our numerical experiments. When the segment consideration sets overlap,we show that some strong equalities called product cuts developed for the CDLP remain validfor our new formulation. Finally we perform extensive numerical comparisons on the variousbounds to evaluate their performance.

Parallel scheduling of multiclass M/M/m queues: Approximate and heavy-traffic optimization of achievable performance

We address the problem of scheduling a multiclass $M/M/m$ queue with Bernoulli feedback on $m$ parallel servers to minimize time-average linear holding costs. We analyze the performance of a heuristic priority-index rule, which extends Klimov's optimal solution to the single-server case: servers select preemptively customers with larger Klimov indices. We present closed-form suboptimality bounds (approximate optimality) for Klimov's rule, which imply that its suboptimality gap is uniformly bounded above with respect to (i) external arrival rates, as long as they stay within system capacity;and (ii) the number of servers. It follows that its relativesuboptimality gap vanishes in a heavy-traffic limit, as external arrival rates approach system capacity (heavy-traffic optimality). We obtain simpler expressions for the special no-feedback case, where the heuristic reduces to the classical $c \mu$ rule. Our analysis is based on comparing the expected cost of Klimov's ruleto the value of a strong linear programming (LP) relaxation of the system's region of achievable performance of mean queue lengths. In order to obtain this relaxation, we derive and exploit a new set ofwork decomposition laws for the parallel-server system. We further report on the results of a computational study on the quality of the $c \mu$ rule for parallel scheduling.

Optimization of multiclass queueing networks with changeover times via the achievable region approach: Part I, the single-station case

We address the performance optimization problem in a single-stationmulticlass queueing network with changeover times by means of theachievable region approach. This approach seeks to obtainperformance bounds and scheduling policies from the solution of amathematical program over a relaxation of the system's performanceregion. Relaxed formulations (including linear, convex, nonconvexand positive semidefinite constraints) of this region are developedby formulating equilibrium relations satisfied by the system, withthe help of Palm calculus. Our contributions include: (1) newconstraints formulating equilibrium relations on server dynamics;(2) a flow conservation interpretation of the constraintspreviously derived by the potential function method; (3) newpositive semidefinite constraints; (4) new work decomposition lawsfor single-station multiclass queueing networks, which yield newconvex constraints; (5) a unified buffer occupancy method ofperformance analysis obtained from the constraints; (6) heuristicscheduling policies from the solution of the relaxations.

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.

Optimization of multiclass queueing networks with changeover times via the achievable region method: Part II, the multi-station case

We address the problem of scheduling a multi-station multiclassqueueing network (MQNET) with server changeover times to minimizesteady-state mean job holding costs. We present new lower boundson the best achievable cost that emerge as the values ofmathematical programming problems (linear, semidefinite, andconvex) over relaxed formulations of the system's achievableperformance region. The constraints on achievable performancedefining these formulations are obtained by formulatingsystem's equilibrium relations. Our contributions include: (1) aflow conservation interpretation and closed formulae for theconstraints previously derived by the potential function method;(2) new work decomposition laws for MQNETs; (3) new constraints(linear, convex, and semidefinite) on the performance region offirst and second moments of queue lengths for MQNETs; (4) a fastbound for a MQNET with N customer classes computed in N steps; (5)two heuristic scheduling policies: a priority-index policy, anda policy extracted from the solution of a linear programmingrelaxation.

Long-range transport of Saharan dust to northern Europe: The 11-16 October 2001 outbreak observed with EARLINET

The spread of mineral particles over southwestern, western, and central Europeresulting from a strong Saharan dust outbreak in October 2001 was observed at10 stations of the European Aerosol Research Lidar Network (EARLINET). For the firsttime, an optically dense desert dust plume over Europe was characterized coherentlywith high vertical resolution on a continental scale. The main layer was located abovethe boundary layer (above 1-km height above sea level (asl)) up to 3–5-km height, andtraces of dust particles reached heights of 7–8 km. The particle optical depth typicallyranged from 0.1 to 0.5 above 1-km height asl at the wavelength of 532 nm, andmaximum values close to 0.8 were found over northern Germany. The lidar observationsare in qualitative agreement with values of optical depth derived from Total OzoneMapping Spectrometer (TOMS) data. Ten-day backward trajectories clearly indicated theSahara as the source region of the particles and revealed that the dust layer observed,e.g., over Belsk, Poland, crossed the EARLINET site Aberystwyth, UK, and southernScandinavia 24–48 hours before. Lidar-derived particle depolarization ratios,backscatter- and extinction-related A ° ngstro¨m exponents, and extinction-to-backscatterratios mainly ranged from 15 to 25%, 0.5 to 0.5, and 40–80 sr, respectively, within thelofted dust plumes. A few atmospheric model calculations are presented showing the dustconcentration over Europe. The simulations were found to be consistent with thenetwork observations.

Diacylglycerol is required for the formation of COPI vesicles in the Golgi-to-ER transport pathway

Diacylglycerol is necessary for trans-Golgi network (TGN) to cell surface transport, but its functional relevance in the early secretory pathway is unclear. Although depletion of diacylglycerol did not affect ER-to-Golgi transport, it led to a redistribution of the KDEL receptor to the Golgi, indicating that Golgi-to-ER transport was perturbed. Electron microscopy revealed an accumulation of COPI-coated membrane profiles close to the Golgi cisternae. Electron tomography showed that the majority of these membrane profiles originate from coated buds, indicating a block in membrane fission. Under these conditions the Golgi-associated pool of ARFGAP1 was reduced, but there was no effect on the binding of coatomer or the membrane fission protein CtBP3/BARS to the Golgi. The addition of 1,2-dioctanoyl-sn-glycerol or the diacylglycerol analogue phorbol 12,13-dibutyrate reversed the effects of endogenous diacylglycerol depletion. Our findings implicate diacylglycerol in the retrograde transport of proteins from Golgi to the ER and suggest that it plays a critical role at a late stage of COPI vesicle formation.

Hierarchical neural network with high storage capacity

A recent method used to optimize biased neural networks with low levels of activity is applied to a hierarchical model. As a consequence, the performance of the system is strongly enhanced. The steps to achieve optimization are analyzed in detail.

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.

Structural factors impacting carrier transport and electroluminescence from Si nanocluster-sensitized Er ions.

We present an analysis of factors influencing carrier transport and electroluminescence (EL) at 1.5 µm from erbium-doped silicon-rich silica (SiOx) layers. The effects of both the active layer thickness and the Si excess content on the electrical excitation of erbium are studied. We demonstrate that when the thickness is decreased from a few hundred to tens of nanometers the conductivity is greatly enhanced. Carrier transport is well described in all cases by a Poole-Frenkel mechanism, while the thickness-dependent current density suggests an evolution of both density and distribution of trapping states induced by Si nanoinclusions. We ascribe this observation to stress-induced effects prevailing in thin films, which inhibit the agglomeration of Si atoms, resulting in a high density of sub-nm Si inclusions that induce traps much shallower than those generated by Si nanoclusters (Si-ncs) formed in thicker films. There is no direct correlation between high conductivity and optimized EL intensity at 1.5 µm. Our results suggest that the main excitation mechanism governing the EL signal is impact excitation, which gradually becomes more efficient as film thickness increases, thanks to the increased segregation of Si-ncs, which in turn allows more efficient injection of hot electrons into the oxide matrix. Optimization of the EL signal is thus found to be a compromise between conductivity and both number and degree of segregation of Si-ncs, all of which are governed by a combination of excess Si content and sample thickness. This material study has strong implications for many electrically driven devices using Si-ncs or Si-excess mediated EL.

Entry Regulation Asymmetries and Gasoline Competition in a Mixed Motorway Network

Regulatory and funding asymmetries in the Spanish motorway network produce huge differences in the structure of gasoline markets by motorway type: free or toll. While competition is encouraged among gas stations on free motorways, the regulations for toll motorways allow private concessionaires to auction all gas stations to the same provider, thereby limiting competition and consolidating market power. This paper reports how this regulatory asymmetry results in higher prices and fewer gas stations. Specifically, we show that competition is constrained on toll motorways by the granting of geographical monopolies, resulting in a small number of rivals operating in close proximity to each other, and allowing gas stations to operate as local monopolies. The lack of competition would seem to account for the price differential between toll and free motorways. According to available evidence, deregulation measures affecting toll motorway concessions could help to mitigate price inefficiencies and increase consumer welfare.

Privatization and PPPS in transportation infrastructure: Network effects of increasing user fees

PPPS: Problem: Public-private-partnerships in transport infrastructure characteristically increase user-fees. Purpose: We aim to identify the network effects of the use of PPPs and increased user tolls in road infrastructure. Methods: We study the increases in user tolls on motorways due to the use of PPPs in the US. Results and conclusions: Among other things, the monetization of motorways is associated with an increase in toll levels that has consequences for their users, and also for the rest of the sections of the network.

Infrastructure and nation building: The regulation and financing of network transportation infrastructures in Spain (1720-2010)

This paper analyzes Spanish infrastructure policy since the early 1700s: Road building in the eighteenth century, railway creation and expansion in the nineteenth, motorway expansion in the twentieth, and high speed rail development in the twenty-first. The analysis reveals a long-term pattern, in which infrastructure policy in Spain has been driven not by the requirements of commerce and economic activity, but rather by the desire to centralize transportation around the country’s political capital.

Price rivalry in airline markets: A study of a successful strategy of a network carrier against a low-cost carrier

Competition in airline markets may be tough. In this context, network carriers have two alternative strategies to compete with low-cost carriers. First, they may establish a low-cost subsidiary. Second, they may try to reduce costs using the main brand. This paper examines a successful strategy of the first type implemented by Iberia in the Spanish domestic market. Our analysis of data and the estimation of a pricing equation show that Iberia has been able to charge lower prices than rivals with its low-cost subsidiary. The pricing policy of the Spanish network carrier has been particularly aggressive in less dense routes and shorter routes.