Large-scale combinatorial optimization models may be used to represent problems of designing supply chain networks that yield desired service levels at minimum cost. Such problems are quite challenging because they are combinatorially explosive - some of these optimization models have millions of variables and millions of constraints, and hence are intractable with respect to conventional approaches such as branch-and-cut and constraint programming.