讲座题目：A Column Generation Algorithm for Facility Location with General Facility Cost Functions

主讲人：宋苗 助理教授 (香港大学, The University of Hong Kong)

时间： 2015年6月26日（周五）15:00-17:00

地点： H3-400 MBA专用教室

主持人：马利军 副教授 管理科学系副主任

主讲人简介：

Dr. Miao Song earned her PhD degree from Massachusetts Institute of Technology in 2010. She is currently an assistant professor in the Department of Industrial and Manufacturing Systems Engineering at the University of Hong Kong. Her research focuses on operations research applications in supply chain management. She has published in top journals such as Management Science and Operations Research.

讲座内容简介：

Most existing facility location models assume that the facility cost is either a fixed setup cost or comprised of a fixed setup and a problem-specific concave or submodular cost term. This structural property plays a critical role in developing fast column generation, Lagrangian relaxation, efficient constant ratio approximation algorithms, and conic IP reformulation approaches for these NP-hard problems. Many practical considerations and complicating factors, however, can make the facility cost no longer concave or submodular. By removing this restrictive assumption, we study a new location model that considers general nonlinear costs to operate facilities in the facility location framework. The general model does not even admit any approximation algorithms unless P = NP because it takes the unsplittable hard-capacitated metric facility location problem as a special case. In response to this, we propose a new column generation approach, in each iteration of which a pricing problem must be solved. Although we show that the pricing problem is NP-hard, we effectively analyze its structural properties, based on which, column generation can be employed to address the general model. The numerical results obtained from the implementations on the location and production/capacity planning models with economies and diseconomies of scale are used to demonstrate the effectiveness of the solution approach.

欢迎感兴趣的师生参加！

　　　　　　　　　　　　　　　永利集团 3044am永利集团官网 管理科学系