[Lecture, Dec 14] Linear reformulation of polynomial discrete programming for fast computation
time: 2018-11-30

Title: Linear reformulation of polynomial discrete programming for fast computation

Speaker: Professor Shu-Cherng Fang, North Carolina State University

Time: 9:30 am, December 14, 2018

Venue: Room 209, Building 37, Wushan Campus

Introduction to the Speaker:

Shu-Cherng Fang holds the Walter Clark Chair Professorship and Alumni Distinguished Graduate Professorship at the Industrial and Systems Engineering Department of the North Carolina State University, USA. Before joining NC State, Professor Fang was Senior Member of Research Staff at Western Electric Engineering Research Center, Supervisor at AT&T Bell Labs, and Department Manager at the Corporate Headquarters of AT&T Technologies. Professor Fang has published over two hundred refereed journal articles. He authored the books of Linear Optimization and Extensions: Theory and Algorithms , Entropy Optimization and Mathematical Programming and Linear Conic Optimization. He currently serves on the editorial boards of several scientific journals, including Optimization, Journal of Global Optimization, Optimization Letters, Pacific Journal of Optimization, Journal of Management and Industrial Optimization, Annals of Data Science, Systems Engineering – Theory and Practice, Journal of Systems Science and Information, Journal of Operations and Logistics, International Journal of Decision Support Systems, Journal of Uncertainties, International Journal of Fuzzy Systems, Iranian Journal of Fuzzy Systems, Fuzzy Information and Engineering, OR Transactions. He is also the Editor-in-Chief of Fuzzy Optimization and Decision Making.


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 find 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 significantly 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 confirm a two-order (102 times) reduction in computational time for randomly generated problems with millions of variables and constraints.