Multi-product newsboy problem (MPNP) with budget constraint is a classical inventory control/management problem. However, solution methods for MPNP under general demand distributions are limited in the current literature. In this paper, by analyzing properties of the optimal solution to the MPNP with a budget constraint, we develop a solution algorithm for the constrained MPNP. The proposed algorithm is binary in nature, and is applicable to general types of demand distribution functions, discrete as well as continuous. For continuous demand distribution function, our approach can obtain the optimal or near optimal solution to the constrained MPNP with polynomial computation complexity of the o(n) order. On the other hand, for discrete demand distribution functions, it can effectively provide good approximate solution. Numerical experiments are presented to show the performance of our method.
Multi-product newsboy problem (MPNP) with budget constraint, introduced firstly by Hadley and Whitin (1963), is a classical inventory control/management problem. Hadley and Whitin (1963) presents a solution method to the constrained MPNP, which encounters difficulties, particularly when the number of products is rather large. After Hadley and Whitin's early work, many researchers have developed different solution methods for MPNPs with different application background. Khouja (1999) presents a good literature review on these researches.
Erlebacher (2000) develops heuristic solutions for the MPNP with one capacity constraint. He begins by proving the optimality of the order quantities for two special cases, then he proceeds by developing heuristics for a few specific probability distribution functions. Vairaktarakis (2000) develops several minimax regret formulations for the MPNP with a budget constraint. His approach can obtain the optimal solution only when the values of demand are intervallic or discrete. For MPNP under general demand distributions, these approaches provide heuristic solutions rather than the optimal solutions.
Abdel-Malek et al. (2004) develops Lagrangian-based methods, which yield the optimal solution to the problem when the demand is uniformly distributed, and near optimal solution when the demand is other continuous distributions. As it is pointed out by Abdel-Malek and Montanari (2005a), most of the existing Lagrangian-based methods do not pay much attention to the lower bounds of the order quantities (non-negativity constraints), e.g., Abdel-Malek et al. (2004), Ben-Daya and Raouf (1993), Erlebacher (2000), Gallego and Moon (1993), Khouja (1999), Moon and Silver (2000), and Vairaktarakis (2000). This negligence, as observed by Lau and Lau, 1995 and Lau and Lau, 1996 could lead to infeasible order quantities (negative) for some of the considered products.
To address non-negativity constraints of the order quantities, Abdel-Malek and Montanari (2005a) extend the research of Abdel-Malek et al. (2004), and propose a modified Lagrangian-based method by analyzing the solution space. Their approach, however, can be applied to obtain the optimal solutions only for special demand distributions, e.g., uniform and normal demand.
In summary, the existing methods for the capacitated newsboy problems have the following limitations: (1) many existing Lagrangian-based models could lead to infeasible order quantities (negative) because of relaxing the lower bounds of the demand (Lau and Lau, 1995 and Lau and Lau, 1996); (2) current solution methods can only solve the optimal solution for the special cases (e.g., Erlebacher, 2000; Abdel-Malek et al., 2004); (3) for general demand distributions, the existing methods can only provide approximate or heuristic solutions (e.g., Erlebacher, 2000; Abdel-Malek and Montanari, 2005a).
In this paper, by analyzing properties of the optimal solution to the MPNP with a budget constraint, we develop a solution algorithm for the constrained MPNP. The proposed algorithm can overcome some of the aforementioned limitations of the current methods. Additionally, it is applicable to both types of demand distribution functions, discrete as well as continuous.
The reminder of this paper is organized as follows. We describe the constrained MPNP problem and the optimal solution to the unconstrained MPNP in Section 2. In Section 3, by presenting the properties of the optimal solution to the constrained MPNP, we develop a binary solution method for the constrained MPNP under general demand distribution. Numerical examples are illustrated in Section 4. Section 5 briefly concludes the paper. The proofs are presented in Appendix A.
In this paper, we propose a binary solution algorithm for multi-product newsboy problem (MPNP) with budget constraint by analyzing properties of its optimal solution. The proposed algorithm has three main advantages over current approaches: (1) it can provide the optimal or near optimal solution to the constrained MPNP under general continuous demand distribution; (2) it can effectively provide good approximate solution to the constrained MPNP under discrete demand distribution; (3) it is easy to follow, and can be extended for the constrained MPNP with non-zero lower bound constraints on order quantities.
There are many possible ways to extend this research. One is to find similar algorithm for the newsboy problem with multiple constraints. Unlike the works presented by Abdel-Malek and Montanari (2005b) and Abdel-Malek and Areeratchakul (2007), our method cannot be directly extended for the constrained MPNP with multiple constraints because defining a marginal budget benefit with multiple constraints needs considerable research works. Another way is to develop efficient algorithm for solving some extension problems, e.g., the gardener problem studied by Abdel-Malek et al. (2008). In addition, the basic idea of this research can also be used to study solution methods for general convex non-linear problems, which have been done in Zhang and Hua (2008).
