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$?

  • $\begingroup$ I managed to develop the following upper-bounds for the problem: $\endgroup$ Feb 12, 2020 at 9:27

1 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.

  • $\begingroup$ Thanks so much for your response. I actually had read Zheng and Federgruen (1991) and as you mentioned the bounds are not quite helpful as you need to identify the optimal (s,S) in the first place. The last few days I was trying to develop some bounds like what you suggested in the update section. But not much chance. I also tried the logic of optimization for the stochastic problem and with contradiction develop some bounds. $\endgroup$ Feb 13, 2020 at 13:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.