Lifeng Chen
Department of Industrial Engineering & Operations Research
Title:
Local Search Approximation Algorithms for Deterministic Inventory Optimization
Abstract:
We consider local search heuristics (LSH) for deterministic inventory problems. LSHs are attractive for their simplicity and have proven effective and efficient in both theory and practice for facility location and scheduling problems, which are closely related to inventory problems. However, the application of LSHs to inventory problems has not received much attention. In this paper we show that LSHs are able to quickly provide high-quality solutions for several classical inventory problems. As an illustrative instance, we focus on the one-warehouse multi-retailer (OWMR) problem. We propose novel LSHs for it that repeatedly improve a given solution by moving to a better neighborhood solution obtained by placing new orders or canceling existing orders. Using these heuristics, we develop the first combinatorial approximation algorithm for the OWMR problem that achieves a constant performance guarantee ($(3+\sqrt{5})/2 +\epsilon$). As a distinguishing feature, the running time of our algorithm is almost linear in the number of arcs for defining the underlying network of the OWMR problem -- $\widetilde{O}(mn^3)$ for an $n$-period, $m$-retailer problem -- in sharp contrast to the complexity $\widetilde{O}(m^3n^9)$ of solving large LP-relaxations of the problem. The proposed algorithm applies to other fundamental inventory problems including the joint replenishment problem and the assembly problem. It also applies to problems with non-additive holding costs and hence allows for perishable products. In addition, it applies to the OWMR problem with backlogs and yields the first constant approximation algorithm. Finally, the algorithm does not require the {\em Monge property} on the holding costs that was necessary in previous work.