2018年论坛学术报告

[数学论坛]Linear Reformulation of Polynomial Discrete Programming for Fast Computation
发布日期:2018-06-12  浏览量:

报告题目:Linear Reformulation of Polynomial Discrete Programming for Fast Computation

报告人:Professor  Shu-Cherng Fang

报告人单位:North Carolina State University

报告时间:2018.06.15  1430-1530

报告地点:老主楼321学术交流厅

摘要:Optimization models involving a polynomial objective function and multiple polynomial constraints with discrete variables are often encountered in engineering, management and systems. Treating the non-convex cross-product terms is the key. State-of-the-art methods usually convert such a problem into a 0-1 mixed integer linear programming problem, and, then, adopt a branch-and-bound scheme to nd an optimal solution. Much eort has been spent on reducing the required numbers of variables and linear constraints as well as on avoiding unbalanced branch-and-bound trees. This talk presents a novel idea of linearizing the discrete cross-product terms in an extremely eective manner. Theoretical analysis shows that the new method signicantly reduces the required number of linear constraints from O(h^3n^3) to O(hn) for a cubic polynomial discrete program with n variables in h possible values. Numerical experiments also conrm a two-order (102 times) reduction in computational time for randomly generated problems with millions of variables and constraints.

报告人简介:美国工程院院士,祖籍湖北,生于台湾,“清华大学”数学系毕业。1979年获美国西北大学工业工程与管理科学博士学位。曾在马里兰大学任教,之后任职新泽西州AT&T贝尔实验室单位主管及该公司总部部门经理。1988年应聘至美国北卡州立大学运筹研究与工业工程系担任教授至今。方述诚教授是“雷诺斯奖”第17位受奖者,也是迄今获此奖的唯一华裔教授,这项荣誉肯定了他在专业领域上的卓越成就。

邀请人:夏勇

 

版权所有 2010 北京航空航天大学数学与系统科学学院     地址:北京市海淀区学院路37号      邮编:100191