报告题目：On the complexity of sequentially lifting cover inequalities for the knapsack polytope

报告人：戴彧虹 研究员（中科院）

报告时间：2019年3月5 日下午 5：00-6：00

报告地点：老主楼321

摘要：The well-known lifted cover inequality is widely employed in solving mixed integer programs. However, it is still an open question whether an arbitrary project lifted cover inequality can be computed in polynomial time for a given minimal cover (Gu, Nemhauser, and Savelsbergh, INFORMS J. Comput., 26: 117123, 1999). We show that this problem is NP-hard, thus giving a negative answer to the question. This is a joint work with Wei-Kun Chen.

报告人简介：戴彧虹，冯康首席研究员，博导，中国运筹学会副理事长，中国运筹学会数学规划分会理事长，中国科学院数学院优化与应用研究中心副主任，计算数学与科学工程计算研究所所长助理，国家基金委数理学部会评专家。曾获得国家自然科学二等奖、第十届中国青年科技奖、“陈省身数学奖”冯康计算数学奖和国家杰出青年基金等奖励。他与袁亚湘院士共同提出了一个性质优良的非线性共轭梯度法，同行广泛称为Dai-Yuan方法，是四个主要的非线性共轭梯度法之一；他彻底解决了由美国西北大学教授Nocedal等提出的关于BFGS拟牛顿法对非凸函数是否收敛的公开问题；他证明了由加拿大数学家Borwein提出的BB梯度法的R-线性收敛性；他给出了一类梯度法的R-超线性收敛结果；他对一类特殊二次规划提出的梯度投影算法，被国际同行称作Dai-Fletcher方法，被成功应用于基于支撑向量机进行大型数据挖掘的并行软件中。

邀请人：韩德仁