A Multi-commodity Supply Chain Design Problem

We consider a multi-commodity supply chain design problem in which we need to determine where to locate facilities and how to allocate customers to facilities so as to minimize total costs. The cost associated with each facility exhibits economies of scale. We show that this problem can be formulated as a nonlinear integer programming model and propose a Lagrangian relaxation based solution algorithm. By exploiting the structure of the problem, we find a low-order polynomial algorithm for the nonlinear integer programming problem that must be solved in solving the Lagrangian relaxation subproblems. We also compare our approach with the existing algorithm.