Inventory Placement in Acyclic Supply Chain Networks

The strategic safety stock placement problem is a constrained separable concave minimization problem and so is solvable, in principle, as a sequence of mixed-integer programming problems using a successive piecewise linear approximation approach. However, the research community has not actively pursued this approach. Instead, researchers have focused on developing other problem specific techniques, including a dynamic programming approach proposed by Graves and Willems (2000) for situations when the underlying network is a spanning tree. In this paper, we experimented with the use of mixed integer programming approach to this problem. By adding a set of redundant constraints to the formulation and by iteratively refining the piecewise linear approximations, we show that a commercial solver (CPLEX) is able to routinely solve moderate-size supply chain safety stock placement problems to optimality. For a random 100-stage sparse acyclic supply chain network, the algorithm typically finds a solution in under two minutes, achieving a speed-up of close to 90-100 over a mixed integer programming implementation using the traditional formulation. The speedup arises because the CPLEX solver is able to automatically generate stronger flow cover cuts using the redundant constraints added.