Title: Structure and instance driven approaches in Large-scale optimization
Professor and Chair, Department of Management Sciences,
University of Waterloo
Abstract: Problem information, such as structure, plays a fundamental role in large scale optimization. Block diagonal structure, for example, is the main driver behind most decomposition methodologies. Information may also exist in data at the instance level or in the structure of optimal or near-optimal solutions. We show how to exploit such information in the design efficient solution methodologies for hard and large optimization problems by discussing four approaches: detecting the structure of constraint matrix, identifying characteristics of near-optimal solutions, imposing structure through modeling, and exploiting instance-level information. In the first, we use community detection to identify bordered block diagonal structure in constraint matrices of integer programs, to make them suitable for column generation, Lagrangian relaxation and branch-and-price methodologies. Quality structures are identified within short CPU times. In the second, we discover an important characteristic of optimal solutions in a class of hub location problems, spatial separability, and use it to solve very large problems in brain connectivity networks. In the third, we impose structure through a novel formulation of the three-dimensional bin packing problem, leading to a column generation approach where the pricing subproblem generates layers. The proposed approach allows, for the first time, the solution of large industry-size instances within the industry standard of 2 minutes. Finally, we show how data at the instance level is used to reduce the complexity of large optimization problems, and allow for efficient solution methodologies. Two applications, one in pallet optimization and the other in layout design, are discussed.
About the Speaker: Samir Elhedhli is a Professor at the Department of Management Sciences at the University of Waterloo with research interests in in Large Scale Optimization and Data Analytics. His work has appeared in top scientific journals such as Management Science, Mathematical Programming, Manufacturing and Service Operations Management, INFORMS Journal on Computing, IISE transactions, and the European Journal of Operational Research among others. He held research grants from NSERC, CFI, OCE and MITACS and collaborated with industries in aircraft manufacturing, airline scheduling, and supply chain analytics. He served as president of the Canadian Operational Research Society (CORS) in 2011-2012. He is currently the Publication Chair and co-Editor-in-Chief of their flagship journal INFOR. He is the recipient of the CORS Service Award in 2013 and the University of Waterloo’s distinguished and outstanding performance awards in 2005, 2006, 2007, 2009, 2012 and 2015.
Title: Availability Analytics in Cloud Computing: Downtime Prediction, SLA Management, and Network Function Virtualization
Professor, Department of Management Science and Systems
University at Buffalo
Abstract: This talk is a synthesis of a body of research conducted by our group over the past several years on availability analytics in cloud computing. Originating from the estimation of the transient downtime distributions of virtual server systems, this research has progressed to the design of optimal price-penalty-resource trifecta in an availability-aware cloud SLA, optimal dynamic management of virtual infrastructures (VI) under flexible Cloud SLAs, and extensions of the downtime estimation methodology to Network Function Virtualization (NFV) architectures. The key features of this research program as follows.
First, a sample path randomization strategy is used to estimate transient downtime distributions. Second, treating the acceptable virtual machine downtime in a contract period as a perishable commodity, an optimal schedule of the trifecta is developed. Third, given the required availability, price and penalty in an SLA, optimal online algorithms are developed for the dynamic management of virtual resources during a contract period. Fourth, using a combination of convex decomposition of the underlying Markov processes and the sample path randomization strategy, a highly scalable, adaptable, easily extensible and fast estimation algorithm for transient downtime distributions of NFV architectures is developed.
Promising and practical future research avenues are: generalizations of the price-penalty-resource trifecta and optimal dynamic VI management under multiple, concurrent, availability-aware cloud SLAs – first with single network function virtualization, and subsequently extending it to multiple network functions.
About the Speaker: Ram Ramesh is a Professor at the Department of Management Science & Systems in the School of Management, State University of New York at Buffalo. His research spans economics of IT, conceptual modeling and database systems, operations and decision analysis. In particular, his contemporary works deal with predictive analytics of availability-aware cloud computing and high performance computing systems, design of service-level contract mechanisms in cloud computing markets, and predictive analytics of health information exchanges. Methodologically, his research is established in predictive modeling, mathematical programming and stochastic optimization. His research has been funded by the National Science Foundation, Google Research, Samsung, Raytheon and Westinghouse, besides various U.S. military research programs including U.S. Army Research Institute, U.S. Air Force Office of Scientific Research, U.S. Air Force Research Laboratory and the U.S. Naval Training Systems Center. He serves as an area editor for the machine learning & knowledge management area of INFORMS Journal on Computing and is a founding co-editor-in-chief of Information Systems Frontiers (published by Springer).
Ramesh has published extensively on the research topics above. His publications appear in such journals as INFORMS Journal on Computing, Information Systems Research, IEEE Transactions on Computers, IEEE Transactions on Knowledge and Data Engineering, ACM Transactions On Database Systems, ACM Transactions on the Web, ACM Transactions on MIS, IEEE Transactions on Systems, Man and Cybernetics, Naval Research Logistics, Management Science, Communications of the ACM, Journal of the American Society for Information Science and Technology (JASIST), Journal of American Medical Informatics Association (JAMIA), and Applied Artificial Intelligence. He has served in numerous leadership positions such as the Chair of department of management science & systems and Associate Dean for research at the School of Management at SUNY at Buffalo, and board member of Infotech Niagara (an association of CIOs in Western New York). He designed, developed and implemented a dual-degree MS/MBA program at Bangalore, India, in collaboration with Amrita University and Hewlett-Packard. He serves as its program director since 2007.