ECE Seminar with Gang Feng

Lagrangian Relaxation Based Algorithms for Finding Constrained Shortest Path With Dr. Gang Feng Department of Electrical Engineering University of Wisconsin-Platteville Faculty Host: David Castanon Refreshments will be served outside Room 339 at 1:45 p.m. Abstract: Finding a shortest path subject to a set of additive constraints in a directed network is a fundamental problem arising in many applications such as quality of service routing in communication networks, vehicle routing, aircraft scheduling, etc. In this talk, we introduce the basic idea of Lagrangian relaxation based methods as well as a state-of-the-art algorithm called direction tuning. We show through experiments on various networks including the most challenging benchmark instances that the new algorithm can solve a significantly larger number of instances to optimality with less computational cost, often by one or two orders of magnitude, when compared with the best known algorithm in the literature. About the Speaker: Dr. Gang Feng is a professor in the Department of Electrical Engineering at the University of Wisconsin-Platteville. His research interests are in the broad area of computer networking, particularly focusing on solving routing problems in both wired and wireless networks. He has a considerable number of publications in developing efficient algorithms for constrained unicast and multicast routing problems. He is also interested in path enumeration algorithms (K-shortest paths), finding disjointed paths subject to quality of service (QoS) requirements, etc. In his early career, he had worked on many projects using Hopfield neural networks to solve optimization problems such as traveling sales problem (TSP), N-queen problem, etc. He is still interested in neural networks and evolutionary computation. Since his joining UW-Platteville in 2002, Dr. Feng has been teaching computer engineering courses such as Introduction to Microprocessors, Advanced Digital Design, etc. He has done numerous projects in embedded system design and avionics software verification.