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 program and propose a Lagrangian-relaxation solution algorithm. By exploiting the structure of the problem, we find a low-order polynomial algorithm for the nonlinear integer program that must be solved in solving the Lagrangian relaxation subproblems. We also compare our approach with an existing algorithm.