On Approximating Lead Time Demand Distributions Using the Generalised λ-type Distribution

In this paper the use of the generalised λ-type distribution (GLD) is proposed for the analysis of standard inventory problems. Using this distribution to approximate the lead time demand distribution we analyse the generalised newsboy problem and a (Q, r) policy. The standard inventory measures like optimal order size, reorder level, average demand lost, etc. are obtained under the GLD and are compared with those given by Shore's approximation and also under exact distributional assumptions. Through a numerical study the various inventory measures are compared using the GLD and Shore's approximation with the exact distributions. The comparison reveals that the GLD approximation is better suited than Shore's approximation to model the lead time demand.     

Minmax regret location–allocation problem on a network under uncertainty

We consider a robust location–allocation problem with uncertainty in demand coefficients. Specifically, for each demand point, only an interval estimate of its demand is known and we consider the problem of determining where to locate a new service when a given fraction of these demand points must be served by the utility. The optimal solution of this problem is determined by the “minimax regret” location, i.e., the point that minimizes the worst-case loss in the objective function that may occur because a decision is made without knowing which state of nature will take place. For the case where the demand points are vertices of a network we show that the robust location–allocation problem can be solved in O(min{p, n − p}n³m) time, where n is the number of demand points, p (p < n) is the fixed number of demand points that must be served by the new service and m is the number of edges of the network.     

Reordering strategies for a newsboy-type product

This paper considers the very common situation in which a single-period ‘newsboy’ type product may be ordered or produced twice during a season/period. We show that the explicit consideration of this reorder opportunity makes the newsboy problem very much richer. The specific version considered in this paper allows a reorder during mid-season after the early-season demand has been observed, and this reorder arrives after a given lead time. The demand distributions during the various portions of the season may have very general distribution forms; also, the late-season and early-season demands may be dependent. Solution procedures are developed to find the best way to exploit this reorder opportunity, and our numerical solutions indicate that this reorder opportunity can improve profits considerably as long as the product's profit margin is not very high. Other real-world variations of this two-order newsboy problem are briefly discussed.     

离散模糊需求报童问题的可能性模型研究

基于可能性分布函数质心特征值,本文建立了确定离散模糊需求报童问题订货量的利润模型,并分析了成本模型和利润模型的关系。研究结果表明:1)基于可能性分布函数质心的模糊可能性成本和利润模型确定的订货量不一致;2)对应不同订货量,模糊可能性成本与利润之和不为固定常数。数值计算表明:该方法不可取。     

Forecasting demand variation when there are stockouts

This paper addresses the common problem of forecasting demand when there are a large number of stockouts. The well-known single period stochastic inventory (or ‘newsboy’) problem provides the optimum, single period, stocking level for a product subject to stochastic demand. There are many situations where repetitive ‘newsboy’ solutions are implemented to guide stocking of repeat, but related, products, such as newspapers, magazines, or perishable groceries. Implementation of the ‘newsboy’ solution requires forecasts of the distribution of demand, although there are many plausible cost parameters that lead to optimum stocking policies where there is a high probability of a stockout. The company is, therefore, faced with the problem of attempting to forecast demand when a high percentage of the available sales data reflects the stock available for sale, rather than the true demand.A procedure has been developed¹ to improve estimates of the mean and variance of the distribution of demand when there are stockouts, but this procedure fails when the percentage of stockouts increases above 50%. A modified stockout adjustment procedure is presented in this paper, and it is shown that use of this new procedure can lead to greatly improved estimates of demand parameters, and greatly improved profitability, when there are a high percentage of stockouts.     

An analytical comparison of the LP relaxations of integer models for the k-club problem

Given an undirected graph G = (V, E), a k-club is a subset of nodes that induces a subgraph with diameter at most k. The k-club problem is to find a maximum cardinality k-club. In this study, we use a linear programming relaxation standpoint to compare integer formulations for the k-club problem. The comparisons involve formulations known from the literature and new formulations, built in different variable spaces. For the case k = 3, we propose two enhanced compact formulations. From the LP relaxation standpoint these formulations dominate all other compact formulations in the literature and are equivalent to a formulation with a non-polynomial number of constraints. Also for k = 3, we compare the relative strength of LP relaxations for all formulations examined in the study (new and known from the literature). Based on insights obtained from the comparative study, we devise a strengthened version of a recursive compact formulation in the literature for the k-club problem (k > 1) and show how to modify one of the new formulations for the case k = 3 in order to accommodate additional constraints recently proposed in the literature.     

The newsstand problem: A capacitated multiple-product single-period inventory problem

Practically all of the many earlier papers on the newsboy problem consider a single newsboy product with no capacity constraint. This paper presents formulations and solution procedures for handling multiple newsboy-type products under two cases: (A) one resource-capacity constraint; and (B) multiple resource constraints. For case A, we present a necessary extension to the classical Hadley-Whitin result for handling general demand distributions. For case B we present a solution procedure that can efficiently handle the common situation where a very large number of products are involved.     

Exact and approximation algorithms for the min–max k-traveling salesmen problem on a tree

Given k identical salesmen, where k ? 2 is a constant independent of the input size, the min–max k-traveling salesmen problem on a tree is to determine a set of k tours for the salesmen to serve all customers that are located on a tree-shaped network, so that each tour starts from and returns to the root of the tree with the maximum total edge weight of the tours minimized. The problem is known to be NP-hard even when k = 2. In this paper, we have developed a pseudo-polynomial time exact algorithm for this problem with any constant k ? 2, closing a question that has remained open for a decade. Along with this, we have further developed a (1 + ?)-approximation algorithm for any ? > 0.     

Worst-case performance of Wong's Steiner tree heuristic

A study of the worst-case performance of Wong's heuristic for the Steiner problem in directed networks (SPDN) is presented in this paper.SPDN is a classic combinatorial optimization problem having the status of a very difficult problem (NP-hard problem) and it is known as an optimization model for a broad class of problems in networks. Several exact and heuristic approaches have been designed for SPDN in the last twenty five years.Some papers analyze theoretical and experimental behavior of heuristics for SPDN, specially for undirected networks, but none of these has studied the worst-case performance of Wong's heuristic. In this paper, we find a lower bound for that performance and show that this bound is consistent with comparable results in the literature on SPDN and its undirected version.     

The multi-item newsvendor problem with a budget constraint and fixed ordering costs

This paper deals with a multi-item newsvendor problem subject to a budget constraint on the total value of the replenishment quantities. Fixed costs for non-zero replenishments have been explicitly considered. Dynamic programming procedures are presented for two situations: (i) where the end item demand distributions are assumed known (illustrated for the case of normally distributed demand) and (ii) a distribution free approach where only the first two moments of the distributions are assumed known. In addition, simple and efficient heuristic algorithms have been developed. Computational experiments show that the performance of the heuristics are excellent based on a set of test problems.     

Optimal worst-case pricing for a logit demand model with network effects

We consider optimal pricing problems for a product that experiences network effects. Given a price, the sales quantity of the product arises as an equilibrium, which may not be unique. In contrast to previous studies that take a best-case view when there are multiple equilibrium sales quantities, we maximize the seller’s revenue assuming that the worst-case equilibrium quantity will arise in response to a chosen price. We compare the best- and worst-case solutions, and provide asymptotic analysis of revenues.     

An analysis of the generalized Towers of Hanoi problem

A state-space graph for representing the states and their transitions ofn discs on three pegs is formulated. It is then transformed to a shortest-path tree for representing the shortest paths in transferringn discs in any configurations to a specified peg. The shortest-path tree clearly characterizes the generalized Towers of Hanoi problem; and its use leads to a very simple analysis of the generalized problem. The best-case, the worst-case and the average-case complexities are analyzed.     

Sell or Hold: A simple two-stage stochastic combinatorial optimization problem

The sell or hold problem (SHP) is to sell k out of n indivisible assets over two stages, with known first-stage prices and random second-stage prices, to maximize the total expected revenue. We show that SHP is NP-hard when the second-stage prices are realized as a finite set of scenarios. We show that SHP is polynomially solvable when the number of scenarios in the second stage is constant. A max{1/2,k/n}-approximation algorithm is presented for the scenario-based SHP.     

A stochastic inventory problem with fuzzy shortage cost

Up to now, many inventory models have been considered in the literature. Some assume stochastic demands and others consider the deterministic case. Though they include a shortage cost due to lost sales, it is usually assumed to be known concretely and a priori. This paper introduces fuzziness of shortage cost explicitly into the classical newsboy problem. That is, we investigate the so-called fuzzy newsboy problem where its shortage cost is vague and given by an L shape fuzzy number. Then the total expected profit function also becomes a fuzzy number. Finally, we find an optimal ordering quantity realizing the fuzzy max order of the profit function (fuzzy min order considering the profit function) and compare it with the optimal ordering quantity of the non-fuzzy newsboy problem.     

Sparse solutions to random standard quadratic optimization problems

The standard quadratic optimization problem (StQP) refers to the problem of minimizing a quadratic form over the standard simplex. Such a problem arises from numerous applications and is known to be NP-hard. In this paper we focus on a special scenario of the StQP where all the elements of the data matrix Q are independently identically distributed and follow a certain distribution such as uniform or exponential distribution. We show that the probability that such a random StQP has a global optimal solution with k nonzero elements decays exponentially in k. Numerical evaluation of our theoretical finding is discussed as well.     

The Distribution Free Newsboy Problem with Balking

The purpose of this paper is to study the classic newsboy model with more realistic assumptions. First, we allow customers to balk when inventory level is low. Secondly, we relax the assumption that the cumulative distribution function of the demand is completely known and merely assume that the first two moments of the distribution function are known.     

Improved approximation for non-preemptive single machine flow-time scheduling with an availability constraint

We study the problem of scheduling n non-preemptable jobs on a single machine which is not available for processing during a given time period. The objective is to minimize the sum of the job completion times. The best known approximation algorithm for this NP-hard problem has a relative worst-case error bound of 17.6%. We present a parametric O(nlog n)-algorithm H with which better worst-case error bounds can be obtained. The best error bound calculated for the algorithm in the paper is 7.4%. In a computational experiment, we test the algorithm with the performance guarantee set to 10.2%. It turns out that randomly generated instances with up to 1000 jobs can be solved with a mean (maximum) error of 0.31% (3.18%) and a mean (maximum) computation time of 0.8 (9.7) seconds.     

An asymptotic expansion of the distribution of Rao's U-statistic under a general condition

In this paper we consider the problem of testing the hypothesis about the sub-mean vector. For this propose, the asymptotic expansion of the null distribution of Rao's U-statistic under a general condition is obtained up to order of n^-1. The same problem in the k-sample case is also investigated. We find that the asymptotic distribution of generalized U-statistic in the k-sample case is identical to that of the generalized Hotelling's T² distribution up to n^-1. A simulation experiment is carried out and its results are presented. It shows that the asymptotic distributions have significant improvement when comparing with the limiting distributions both in the small sample case and the large sample case. It also demonstrates the equivalence of two testing statistics mentioned above.     

Worst-case analysis of demand point aggregation for the Euclidean p-median problem

Solving large-scale p-median problems is usually time consuming. People often aggregate the demand points in a large-scale p-median problem to reduce its problem size and make it easier to solve. Most traditional research on demand point aggregation is either experimental or assuming uniformly distributed demand points in analytical studies. In this paper, we study demand point aggregation for planar p-median problem when demand points are arbitrarily distributed. Efficient demand aggregation approaches are proposed with the corresponding attainable worst-case aggregation error bounds measured. We demonstrate that these demand aggregation approaches introduce smaller worst-case aggregation error bounds than that of the honeycomb heuristic [Papadimitriou, C.H., 1981. Worst-case and probabilistic analysis of a geometric location problem. SIAM Journal on Computing 10, 542–557] when demand points are arbitrarily distributed. We also conduct numerical experiments to show their effectiveness.     

Robust strategies for facility location under uncertainty

This paper considers a stochastic facility location problem in which multiple capacitated facilities serve customers with a single product, and a stockout probabilistic requirement is stated as a chance constraint. Customer demand is assumed to be uncertain and to follow either a normal or an ambiguous distribution. We study robust approximations to the problem in order to incorporate information about the random demand distribution in the best possible, computationally tractable way. We also discuss how a decision maker’s risk preferences can be incorporated in the problem through robust optimization. Finally, we present numerical experiments that illustrate the performance of the different robust formulations. Robust optimization strategies for facility location appear to have better worst-case performance than nonrobust strategies. They also outperform nonrobust strategies in terms of realized average total cost when the actual demand distributions have higher expected values than the expected values used as input to the optimization models.