9625320 Shaw This research develops a new methodology, known as columnwise formulation and column generation, for solving combinatorial optimization problems. Combinatorial optimization problems are a very important problem class, and include such problems as the traveling salesman problem, the general assignment problem, and the capacitated minimum spanning tree problem. Problems in this class are among the most difficult combinatorial problems to solve efficiently. The researcher has identified potential industrial partners, including two large telecommunications firms, interested in capacity expansion problems in the design of both local access and broad-band networks. Further, the investigator will undertake two innovative educational projects. One is to integrate modern communication tools, such as the World Wide Web, into classroom teaching; the other is to enhance the teaching and research program in optimization and to develop a computer laboratory for modeling and optimization. The methodology is innovative and has potential for significant theoretical advances in efficiently solving difficult combinatorial problems. At the same time, it has promising real-world applications in the design of telecommunications networks.
