Download the flier
Learn about the Surrogate Lagrangian Relaxation method of mixed-integer linear optimization problems in this IE Decisions Systems Engineering Fall 2017 Seminar Series event hosted by Assistant Professor Giulia Pedrielli.
Are practical mixed-integer linear optimization problems hopeless to solve?
Presented by Peter B. Luh, University of Connecticut, Storrs, Connecticut
Friday, October 20, 2017
noon
Brickyard (BYENG) 210, Tempe campus [map]
Abstract
Mixed-integer linear optimization problems are prevalent in practical applications, such as manufacturing, power, energy and building systems. Since derivatives of an objective function with respect to discrete decision variables do not exist, there is no necessary optimality conditions. As a result, partial enumeration of discrete variables is generally needed, and the complexity to obtain an optimal solution increases exponentially as the problem size increases.
Historically, Lagrangian relaxation was used to solve such problems by relaxing “coupling constraints” and decomposing relaxed problems into subproblems. However, the method suffers major convergence and computational difficulties. The recent trend is to use branch-and-cut that exploits problem linearity. However, complex problems pose major challenges.
We developed the Surrogate Lagrangian Relaxation method where a proper direction to update multipliers are obtained without optimally solving all subproblems with much reduced computational efforts and much less multiplier zigzagging.
Also, convergence to the optimum does not require the knowledge of the optimal dual value. The method is then synergistically combined with branch-and-cut. The latest developments include Surrogate Augmented Lagrangian Relaxation to further speed up convergence; tightening subproblem formulation with much reduced cutting; and distributed and asynchronous versions for self-optimization applications.
The approach opens up a new direction for optimizing mixed-integer linear optimization problems to obtain near-optimal solutions with quantifiable quality in a computationally efficient manner.
About the speaker
Peter B. Luh received his bachelor’s from National Taiwan University, his master’s from MIT and his doctorate from Harvard University.
He has been with the University of Connecticut since 1980 and currently is the SNET Professor of Communications and Information Technologies.
Luh is also a member of the Chair Professors Group, Center for Intelligent and Networked Systems (CFINS) in the Department of Automation, Tsinghua University Beijing, China.
He is a Life Fellow of IEEE and the Chair of IEEE TAB Periodicals Committee for the 2018–2019 term. He was the VP of Publications of IEEE Robotics and Automation Society (RAS, 2008–2011), the founding editor-in-chief of the IEEE Transactions on Automation Science and Engineering (2003–2007) and the editor-in-chief of IEEE Transactions on Robotics and Automation (1999–2003). He was the Founding Chair of the Steering Committee of the IEEE Conference on Automation Science and Engineering (2006–2011), and continues as a member.
His research interests include smart and green buildings, smart power systems and intelligent manufacturing. He received the RAS 2013 Pioneer Award and the 2017 George Saridis Leadership Award.
