Large-scale supply chain network optimization via nested partitions

Large-scale supply chain design problems are generally intractable with respect to standard mixed-integer programming (MIP) tools such as the direct application of general-purpose branch-and-cut (BC) commercial solvers such as CPLEX. In this research, we investigate a Nested Partitions (NP) framework that combines meta-heuristics with MIP tools (including branch-and-cut). We also present a Column Generation algorithm for generating lower bounds that takes advantage of high-quality feasible solutions produced by NP.; We consider a variety of alternative formulations and decomposition methods for this problem class. Our results show that our NP based Column Generation algorithm is capable of efficiently producing high quality bounds to supply chain network design problems. For large-scale problems in this class, this approach is significantly faster and generates better bounds than either CPLEX (applied directly to the given MIP) or the iterative Lagrangian-based methods that have generally been regarded as the most effective structure-based techniques for large-scale supply chain network optimization.; This overall process is implemented via looping constructs available in the AMPL modeling language (with CPLEX being used as the branch-and-cut solver). This procedure represents a novel framework for the utilization of modeling-language/branch-and-cut software for the generation, evaluation, and coordination of information corresponding to appropriately partitioned global views of the original problem while taking good advantage of the structure of the problem class. The results show that our approach is capable of efficiently producing high quality feasible solutions and lower bounds.