標題: Linear Reformulation of Polynomial Discrete Programming for Fast Computation
作者: Li, Han-Lin
Huang, Yao-Huei
Fang, Shu-Cherng
資訊管理與財務金融系 註:原資管所+財金所
Department of Information Management and Finance
關鍵字: polynomial discrete program;mixed-integer linear program;linearization equation;branch and bound
公開日期: 1-Dec-2017
摘要: Polynomial discrete programming problems are commonly faced but hard to solve. Treating the nonconvex 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 the 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 study presents a set of equations that linearize the discrete cross-product terms in an extremely effective manner. It is shown that embedding the proposed "equations for linearizing discrete products" into those state-of-the-art methods in the literature not only significantly reduces the required number of linear constraints from O(h(3)n(3)) to O(hn) for a cubic polynomial discrete program with n variables in h possible values but also tighten these methods with much more balanced branch-and-bound trees. Numerical experiments confirm a two-order (10(2)-times) reduction in computational time for some randomly generated cubic polynomial discrete programming problems.
URI: http://dx.doi.org/10.1287/ijoc.2016.0716
http://hdl.handle.net/11536/144575
ISSN: 1091-9856
DOI: 10.1287/ijoc.2016.0716
期刊: INFORMS JOURNAL ON COMPUTING
Volume: 29
起始頁: 108
結束頁: 122
Appears in Collections:Articles