报告摘要:

Integer and mixed-integer optimization problems are prevalent in practical applications, e.g., manufacturing, energy, power, and building systems.  Since derivatives of the objective function with respect to discrete decision variables do not exist, generally there is no necessary optimality conditions.  As a result, partial enumeration of discrete variables are 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 with a separable structure by relaxing coupling constraints and decomposing relaxed problems into subproblems.  Although subgradient methods were widely used to update multipliers, they require the relaxed problem to be fully optimized, and this can be computationally expensive.  Moreover, convergence can be slow because optimal dual values are needed to calculate step sizes, and multipliers often zigzag across “ridges” of the dual function.  The recent trend is to solve these problems by using branch-and-cut that exploits problem linearity.  However, complex problems can pose major computational challenges.  The reason is that cuts that define a convex hull are problem-dependent and may be difficult to obtain.  More importantly, there is no “local” concept, and complex constraints within a subsystem are treated as global constraints and affect the entire solution process.  Very recently, we developed the Surrogate Lagrangian Relaxation method where a proper direction to update multipliers can be obtained without optimally solving all subproblems with much reduced computational effort and much less multiplier zigzagging.  Also, convergence to the optimum does not require the knowledge of the optimal dual value.  To enable an efficient exploitation of separability as well as linearity, surrogate Lagrangian relaxation and branch-and-cut are synergistically combined where surrogate Lagrangian relaxation is used to decompose a problem into subproblems, and each subproblem is solved by using branch-and-cut.  With decomposition, the complexity of a subproblem is much smaller than that of the original problem.  Constraints associated with a subproblem are handled locally and do not affect the entire solution process.  Furthermore, by exploiting the novel observation that subproblem constraints and therefore the associated subproblem convex hulls remain invariant after multipliers are updated, if a subproblem convex hull is obtained, solving the subproblem in future iterations will be a piece of cake.  Even if subproblem convex hulls cannot be fully obtained, cuts obtained remain valid and can be used for future iterations.  The approach thus opens up a new direction for optimizing discrete or mixed integer optimization problems for obtaining near-optimality solutions with quantifiable quality in a computationally efficient manner. 

报告人介绍：

Peter B. Luh received his BS. from National Taiwan University, M.S. from M.I.T., and Ph.D. from Harvard University.  He has been with the University of Connecticut since 1980, and currently is the SNET Professor of Communications & Information Technologies.  He was the Head of the Department of Electrical and Computer Engineering from 2006 to 2009.  He 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.  Professor Luh is a Fellow of IEEE and a member of IEEE TAB Periodicals Committee.  He was the VP of Publications of 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 received IEEE Robotics and Automation Society 2013 Pioneer Award for his pioneering contributions to the development of near-optimal and efficient planning, scheduling, and coordination methodologies for manufacturing and power systems.  His research interests include Smart Power Systems – smart grid, design of auction methods for electricity markets, robust renewable (wind and solar) integration to the grid, and electricity load and price forecasting; Intelligent Manufacturing Systems – planning, scheduling, and coordination of design, manufacturing, and service activities; Smart and Green Buildings and Eco Communities – optimized energy management, HVAC fault detection and diagnosis, emergency crowd guidance, and eco communities.