Design and Operation of a Multicommodity Production/Distribution System Using Primal Goal Decomposition

An optimization-based decision support system has been developed and used by NABISCO to manage complex problems involving facility selection, equipment location and utilization, and manufacture and distribution of products such as the familiar Ritz Crackers, Oreo Cookies, Fig Newtons, etc. (all product names trademarks of NABISCO). A mixed-integer, multi-commodity model is presented for the problems at hand, and a new class of goal decompositions is introduced to yield pure network subproblems for each commodity; the associated master problems have several notable properties which contribute to the effectiveness of the algorithm. Excellent quality solutions for problems with more than 40,000 variables (including several hundred binary variables with fixed charges) and in excess of 20,000 constraints require only 0.6 megabytes region and less than one compute minute on a time-shared IBM 3033 computer; average problems (with fewer binary variables) require only a second or two. The solution method has more to recommend it than sheer efficiency: new insights are given for the fundamental convergence properties of formal decomposition techniques. Several applications of this powerful interactive tool are discussed.