Warehouse-Retailer Network Design: New Formulation and Approximation Algorithm

We study a warehouse-retailer network design model due to Teo and Shu (2004). A column generation algorithm was proposed by Teo and Shu to solve the linear programming relaxation of a set partitioning formulation of this model, which has exponential number of variables. In this paper, we suggest a new integer programming formulation of this model that enjoys polynomial number of constraints of variables. Computational results shall be reported. We also propose a polynomial time approximation algorithm that has a constant-factor performance guarantee.