j9九游会

报告主题：具有快速收敛的多项式离散妄想的线性模子
报告人： 方述诚 教授 (美国北卡州立大学)
报告时间：2016年12月14日（周三）16:00
报告所在：校本部G508
约请人：白延琴
主理部分：理学院数学系
报告摘要：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 e?ort 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 e?ective manner. Theoretical analysis shows that the new method signi?cantly reduces the required number of linear constraints from O(h3n3) to O(hn) for a cubic polynomial discrete program with n variables in h possible values. Numerical experiments also con?rm a two-order (102 times) reduction in computational time for randomly generated problems with millions of variables and constraints.

接待西席、学生加入 ！