9502502 The objective of the research is to develop efficient solution procedures for large-scale capacitated instances of Fixed Charge Network Design (FCND) problems. The research focus is on the development of new and stronger formulations that provide a tighter linear programming (LP) bound. Alternate formulations of the problem will be investigated, including the node-arc and path-flow formulations. To support the new formulations, new solution algorithms will be developed to solve the models. The techniques to be explored in developing the algorithms will have a strong emphasis on branch-and-price approaches (i.e., column generation techniques for solving LP relaxations embedded in a branch-and-bound approach), Lagrangian relaxation, and Benders decomposition. While emphasis will be on exact solution, the insights gained from the exact solution procedures will be used to develop heuristic algorithms. On the educational side, experiences from this research will be used to restructure the current approach to teaching operations research to integrate modeling and algorithms with applications. The restructuring will be carried out with an overhaul of the industrial engineering undergraduate curriculum at the host university. The restructuring will also involve developing a new elective course on mathematical programming for undergraduates to provide a forum for teaching advance modeling and algorithmic issues. A sequence of core courses in optimization will also be developed at the graduate level. The research problem is significant since the models to be developed are applicable to a broad range of industrial problems, including transportation, telecommunications, logistics, and production. Most existing solution techniques for these classes of problems are effective only for small size problems. Because the emphasis on this research is on moderate to large size problems, many industries stand to realize financial benefits if this research produces meaningful solution algorithms for reasonable size problems. Furthermore, existing solution techniques are directed mostly to uncapacitated problems. The current project is aimed at extending the research to the more general capacitated problem.
