Revenue management with aircraft reassignment flexibility

A well‐studied problem in airline revenue management is the optimal allocation of seat inventory among different fare‐classes, given a capacity for the flight and a demand distribution for each class. In practice, capacity on a flight does not have to be fixed; airlines can exercise some flexibility on the supply side by swapping aircraft of different capacities between flights as partial booking information is gathered. This provides the airline with the capability to more effectively match their supply and demand. In this paper, we study the seat inventory control problem considering the aircraft swapping option. For theoretical and practical purposes, we restrict our attention to the class of booking limit policies. Our analytical results demonstrate that booking limits considering the swapping option can be considerably different from those under fixed capacity. We also show that principles on the relationship between the optimal booking limits and demand characteristics (size and risk) developed for the fixed‐capacity problem no longer hold when swapping is an option. We develop new principles and insights on how demand characteristics affect the optimal booking limits under the swapping possibility. We also develop an easy to implement heuristic for determining the booking limits under the swapping option and show, through a numerical study, that the heuristic generates revenues close to those under the optimal booking limits. © 2011 Wiley Periodicals, Inc. Naval Research Logistics, 2011     

Signal‐to‐interference‐plus‐noise ratio estimation for wireless communication systems: Methods and analysis

The Signal‐to‐Interference‐plus‐Noise Ratio (SINR) is an important metric of wireless communication link quality. SINR estimates have several important applications. These include optimizing the transmit power level for a target quality of service, assisting with handoff decisions and dynamically adapting the data rate for wireless Internet applications. Accurate SINR estimation provides for both a more efficient system and a higher user‐perceived quality of service. In this paper, we develop new SINR estimators and compare their mean squared error (MSE) performance. We show that our new estimators dominate estimators that have previously appeared in the literature with respect to MSE. The sequence of transmitted bits in wireless communication systems consists of both pilot bits (which are known both to the transmitter and receiver) and user bits (which are known only by the transmitter). The SINR estimators we consider alternatively depend exclusively on pilot bits, exclusively on user bits, or simultaneously use both pilot and user bits. In addition, we consider estimators that utilize smoothing and feedback mechanisms. Smoothed estimators are motivated by the fact that the interference component of the SINR changes relatively slowly with time, typically with the addition or departure of a user to the system. Feedback estimators are motivated by the fact that receivers typically decode bits correctly with a very high probability, and therefore user bits can be thought of as quasipilot bits. For each estimator discussed, we derive an exact or approximate formula for its MSE. Satterthwaite approximations, noncentral F distributions (singly and doubly) and distribution theory of quadratic forms are the key statistical tools used in developing the MSE formulas. In the case of approximate MSE formulas, we validate their accuracy using simulation techniques. The approximate MSE formulas, of interest in their own right for comparing the quality of the estimators, are also used for optimally combining estimators. In particular, we derive optimal weights for linearly combining an estimator based on pilot bits with an estimator based on user bits. The optimal weights depend on the MSE of the two estimators being combined, and thus the accurate approximate MSE formulas can conveniently be used. The optimal weights also depend on the unknown SINR, and therefore need to be estimated in order to construct a useable combined estimator. The impact on the MSE of the combined estimator due to estimating the weights is examined. © 2004 Wiley Periodicals, Inc. Naval Research Logistics, 2004     

Gittins-index heuristics for research planning

The classical work of Gittins, which resulted in the celebrated index result, had applications to research planning as an important part of its motivation. However, research planning problems often have features that are not accommodated within Gittins's original framework. These include precedence constraints on the task set, influence between tasks, stopping or investment options and routes to success in which some tasks do not feature. We consider three classes of Markovian decision models for research planning, each of which has all of these features. Gittins-index heuristics are proposed and are assessed both analytically and computationally. They perform impressively. © 1995 John Wiley & Sons, Inc.     

Tabular aids for fitting weibull moment estimates

Moment estimators for the parameters of the Weibull distribution are considered in the context of analysis of field data. The data available are aggregated, with individual failure times not recorded. In this case, the complexity of the likelihood function argues against the use of maximum-likelihood estimation, particularly for relatively large sets of data, and moment estimators are a reasonable alternative. In this article, we derive the asymptotic covariance matrix of the moment estimators, and provide listings for BASIC computer programs which generate tables useful for calculation of the estimates as well as for estimating the asymptotic covariance matrix using aggregated data.     

Hybrid heuristics for minimum cardinality set covering problems

Minimum cardinality set covering problems (MCSCP) tend to be more difficult to solve than weighted set covering problems because the cost or weight associated with each variable is the same. Since MCSCP is NP-complete, large problem instances are commonly solved using some form of a greedy heuristic. In this paper hybrid algorithms are developed and tested against two common forms of the greedy heuristic. Although all the algorithms tested have the same worst case bounds provided by Ho [7], empirical results for 60 large randomly generated problems indicate that one algorithm performed better than the others.     

On estimating population characteristics from record-breaking observations. i. parametric results

Consider an experiment in which only record-breaking values (e.g., values smaller than all previous ones) are observed. The data available may be represented as X₁,K₁,X₂,K₂, …, where X₁,X₂, … are successive minima and K₁,K₂, … are the numbers of trials needed to obtain new records. We treat the problem of estimating the mean of an underlying exponential distribution, and we consider both fixed sample size problems and inverse sampling schemes. Under inverse sampling, we demonstrate certain global optimality properties of an estimator based on the “total time on test” statistic. Under random sampling, it is shown than an analogous estimator is consistent, but can be improved for any fixed sample size.     

Modified fictitious play

We describe a modification of Brown's fictitious play method for solving matrix (zero-sum two-person) games and apply it to both symmetric and general games. If the original game is not symmetric, the basic idea is to transform the given matrix game into an equivalent symmetric game (a game with a skew-symmetric matrix) and use the solution properties of symmetric games (the game value is zero and both players have the same optimal strategies). The fictitious play method is then applied to the enlarged skew-symmetric matrix with a modification that calls for the periodic restarting of the process. At restart, both players' strategies are made equal based on the following considerations: Select the maximizing or minimizing player's strategy that has a game value closest to zero. We show for both symmetric and general games, and for problems of varying sizes, that the modified fictitious play (MFP) procedure approximates the value of the game and optimal strategies in a greatly reduced number of iterations and in less computational time when compared to Brown's regular fictitious play (RFP) method. For example, for a randomly generated 50% dense skew-symmetric 100 × 100 matrix (symmetric game), with coefficients |a_ij| ≤ 100, it took RFP 2,652,227 iterations to reach a gap of 0.03118 between the lower and upper bounds for the game value in 70.71 s, whereas it took MFP 50,000 iterations to reach a gap of 0.03116 in 1.70 s. Improved results were also obtained for general games in which the MFP solves a much larger equivalent symmetric game. © 1996 John Wiley & Sons, Inc.     

A class of Bayes-optimal two-stage screens

Items are characterized by a set of attributes (T) and a collection of covariates (X) associated with those attributes. We wish to screen for acceptable items (T ∈ C_T), but T is expensive to measure. We envisage a two-stage screen in which observation of X_ is used as a filter at the first stage to sentence most items. The second stage involves the observation of T for those items for which the first stage is indecisive. We adopt a Bayes decision-theoretic approach to the development of optimal two-stage screens within a general framework for costs and stochastic structure. We also consider the important question of how much screens need to be modified in the light of resource limitations that bound the proportion of items that can be passed to the second stage. © 1996 John Wiley & Sons, Inc.     

Relaxation method for the solution of the minimax location-allocation problem in euclidean space

A method previously devised for the solution of the p-center problem on a network has now been extended to solve the analogous minimax location-allocation problem in continuous space. The essence of the method is that we choose a subset of the n points to be served and consider the circles based on one, two, or three points. Using a set-covering algorithm we find a set of p such circles which cover the points in the relaxed problem (the one with m < n points). If this is possible, we check whether the n original points are covered by the solution; if so, we have a feasible solution to the problem. We now delete the largest circle with radius r_p (which is currently an upper limit to the optimal solution) and try to find a better feasible solution. If we have a feasible solution to the relaxed problem which is not feasible to the original, we augment the relaxed problem by adding a point, preferably the one which is farthest from its nearest center. If we have a feasible solution to the original problem and we delete the largest circle and find that the relaxed problem cannot be covered by p circles, we conclude that the latest feasible solution to the original problem is optimal. An example of the solution of a problem with ten demand points and two and three service points is given in some detail. Computational data for problems of 30 demand points and 1–30 service points, and 100, 200, and 300 demand points and 1–3 service points are reported.