Department of Computer Science

Benjamin Wah

Date: Apr. 22, 2004

Time: 3:30PM

Location: 2055 Hoover

Title: Nonlinear Optimization in Planning and Scheduling

Abstract: The solution of mixed-integer constrained optimization problems with highly nonlinear objectives and/or constraints has long been considered challenging. These problems are abundant in many engineering applications, including IC design automation, signal processing, planning and scheduling, computer aided manufacturing, robotics, data mining, and neural-network learning. In this talk, we present a new theory based on the extended saddle point condition that is proved to be necessary and sufficient for characterizing constrained local minima in these problems. An important property of the condition is that it can be partitioned into multiple necessary conditions that collectively are necessary and sufficient. This allows complex problems to be partitioned into simpler subproblems that can be solved independently, before resolving violated global constraints that relate the subproblems. We illustrate the application of the theory in temporal planning and the design of a new planner for space applications. Partitioning is attractive in temporal planning problems because many of their constraints and objectives are related to activities with temporal locality. We also discuss other related applications in machine learning, signal processing, and nonlinear optimization.

About the Speaker: Benjamin W. Wah is currently the Franklin W. Woeltge Professor of Engineering and a Professor in the Department of Electrical and Computer Engineering and the Coordinated Science Laboratory of the University of Illinois at Urbana-Champaign, Urbana, IL. He received his Ph.D. degree in computer science from the University of California, Berkeley, CA, in 1979. Previously, he had served on the faculty of Purdue University (1979-85), as a Program Director at the National Science Foundation (1988-89), as Fujitsu Visiting Chair Professor of Intelligence Engineering, University of Tokyo (1992), and McKay Visiting Professor of Electrical Engineering and Computer Science, University of California, Berkeley (1994). In 1989, he was awarded a University Scholar of the University of Illinois; in 1998, he received the IEEE Computer Society Technical Achievement Award; in 2000, the IEEE Millennium Medal; and in 2003, the Raymond T. Yeh Lifetime Achievement Award from the Society for Design and Process Science.

Wah's current research interests are in the areas of nonlinear search and optimization, multimedia signal processing, and computer networks.

Wah was the Editor-in-Chief of the IEEE Transactions on Knowledge and Data Engineering between 1993 and 1996, and is the Honorary Editor-in-Chief of Knowledge and Information Systems. He currently serves on the editorial boards of Information Sciences, International Journal on Artificial Intelligence Tools, Journal of VLSI Signal Processing, World Wide Web, and Neural Processing Letters. He had chaired a number of international conferences and was the International Program Committee Chair of the IFIP World Congress in 2000. He has served the IEEE Computer Society in various capacities; among them include Vice President for Publications (1998 and 1999) and President (2001). He is a Fellow of the IEEE and the Society for Design and Process Science.