An upper-bound on the value of $S$ in $(s,S)$ policy

Question

I recently have come across a problem which can be categorized as a stochastic optimization. The problem seems simple, but I haven't been able to solve it yet. It has a major impact on algorithm design for real business problems.

Assume that there is a retailer who faces a stationary/stochastic demand with a known discrete distribution. Let $K$ denote the fixed cost of ordering, and $h$ and $b$ denote the holding and back-order cost of the retailer respectively. It can be shown that the optimal solution for this problem over an infinite horizon follows $(s, S)$ policy in which whenever the inventory level of the retailer falls below $s$, it brings it back to $S$ by setting an order.

What I like to know here is, if there is any upper-bound for the value of $S$ (based on $K$, $h$, and $b$)?

Extension: The problem has two stages, and in the upper stage, there is a supplier who has to respond to the orders. Assuming $K$s, $h$s and $b$s as the setup cost of the supplier, holding and back-order costs of the supplier, and the problem is solved in an integrated manner, what is the bound for the $s$ and $S$?

Answer 1

There is (sort of) such a bound. Zheng and Federgruen (1991) prove that for a single-node system with discrete demands and fixed costs,

$$S^* \le \max\{y \ge y^*|g(y) \le g^*\},$$

where $g(y)$ is the (discrete) newsvendor cost function, $y^*$ is its optimizer, $g^* = g(s^*,S^*)$, and $g(s,S)$ is the expected cost function for the $(s,S)$ problem. In other words, $S^*$ cannot be larger than the largest $y$ for which $g(y) \le g^*$. This is not necessarily a useful bound because it requires knowledge of the optimal solution—it is not simply in terms of the policy parameters.

However, Zheng and Federgruen present this result in the context of a pretty simple algorithm for optimizing $s$ and $S$, which may be sufficient for your needs. (We also cover this in our book, if that helps.)

As for the two-node problem: If you simply optimize the retailer first, then optimize the supplier, you can probably get a probability distribution for the order quantities placed by the retailer, and then optimize the supplier the same way you optimized the retailer (i.e., $(s,S)$ policy with discrete demands).

If you are hoping to optimize them jointly, then the problem is harder. One paper I know of is by Shang and Zhou (2010); this isn't exactly the setup you're describing, but it might be a starting point.

---

UPDATE: Actually, I think it should be possible to show that $S^*$ is less than or equal to the largest $y$ such that

$$g(y) \le g(y^*) + K,$$

where $g(\cdot)$ is the newsvendor cost function. I can't quite work out the details at the moment, but if this seems like a promising approach to you, I can try to work it out, or point you to the sections in our book that might contain the pieces you'd have to assemble to prove it.