ReportTitle:
Linear Reformulation of Polynomial Discrete Programming for Fast Computation
Reporter(Institution):
Shu-Cherng Fang (North Carolina State University)
Time:2:00.pm,16th Dec, 2016
Location:B-201, Building of Economics & Management, Jiulonghu Campus
Abstract:
Optimization models involving a polynomial objective function and multiple polynomial constraints with discrete variables are often encountered in engineering, management and systems. Integer linear programming and quadratic integer programming are good examples. 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 effort 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 effective 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 real and randomly generated problems with millions of variables and constraints.
*Joint work with Prof. Hanlin Li and Prof. Yaohui Huang
Reporter:
Professor Shu‐Cherng Fang，
BS (National Tsing Hua University)
MA (Johns Hopkins University)
PhD (Northwestern University)
Shu-Cherng Fang holds the Walter Clark Chair and University Alumni Distinguished Graduate Professorship at North Carolina State University. He has also been Honorary University Chair Professor at Tsinghua University in Beijing, Fudan University in Shanghai, Northeastern University in Shenyang, Shanghai University in Shanghai, National Chiao Tung University in Hsinchu and National Tsing Hua University in Taiwan. 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 two hundred some refereed journal articles and book chapters. He authored the books of Linear Optimization and Extensions: Theory and Algorithms (Prentice Hall 1993, with S. C. Puthenpura), Entropy Optimization and Mathematical Programming (Kluwer Academic 1997, with J.R. Rajasekera and H.-S. Tsao) and Linear Conic Programming: Theory and Application (Science Press 2013, with Wenxun Xing). He currently serves on the editorial boards of twenty four scientific journals, including Optimization, Journal of Global Optimization, Optimization Letters, Pacific Journal of Optimization, Journal of Management and Industrial Optimization, Journal of Operations and Logistics, International Journal of Operations and Quantitative Management, International Journal of Operations Research, Journal of Operations Research Society of China, OR Transactions, American Journal of Operations Research, Journal of Uncertainties, International Journal of Fuzzy Systems, Iranian Journal of Fuzzy Systems, Journal of Chinese Institute of Industrial Engineers. He is also the Founding Editor-in-Chief of Fuzzy Optimization and Decision Making.
Professor Fang has graduated about fifty PhD students. He has won many awards and has been listed in several major biographic references. Professor Fang’s research interests include Linear and Nonlinear Programming, Fuzzy Optimization and Decision Making, Soft Computing, Logistics, and Supply Chain Management.
