报 告 人：美国康涅狄格大学Peter B. Luh教授

报告时间：2016年4月29日（星期五）

上午10:15-11:15

报告地点：东北大学老校部224

报告题目：Are practical integer or mixed-integer optimization problems hopeless to solve?

邀 请 人：工业工程与物流优化研究所 唐立新 教授

摘要: 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.  The recent trend is to solve these problems by using branch-and-cut that exploits problem linearity.  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 B.S. 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.