One of the most important policies adopted in inventory control is the (R,S) policy (also known as the "replenishment cycle" policy). Under the non-stationary demand assumption the (R,S) policy takes the form (R,,S,) where R. denotes the length of the n(th) replenishment cycle, and S. the corresponding order-up-to-level. Such a policy provides an effective means of damping planning instability and coping with demand uncertainty. In this paper we develop a CP approach able to compute optimal (R-n,S-n) policy parameters under stochastic demand, ordering, holding and shortage costs. The convexity of the cost-function is exploited during the search to compute bounds. We use the optimal solutions to analyze the quality of the solutions provided by an approximate MIP approach that exploits a piecewise linear approximation for the cost function.