完整後設資料紀錄
DC 欄位 | 值 | 語言 |
---|---|---|
dc.contributor.author | Li, Han-Lin | en_US |
dc.contributor.author | Huang, Yao-Huei | en_US |
dc.contributor.author | Fang, Shu-Cherng | en_US |
dc.date.accessioned | 2018-08-21T05:53:21Z | - |
dc.date.available | 2018-08-21T05:53:21Z | - |
dc.date.issued | 2017-12-01 | en_US |
dc.identifier.issn | 1091-9856 | en_US |
dc.identifier.uri | http://dx.doi.org/10.1287/ijoc.2016.0716 | en_US |
dc.identifier.uri | http://hdl.handle.net/11536/144575 | - |
dc.description.abstract | 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. | en_US |
dc.language.iso | en_US | en_US |
dc.subject | polynomial discrete program | en_US |
dc.subject | mixed-integer linear program | en_US |
dc.subject | linearization equation | en_US |
dc.subject | branch and bound | en_US |
dc.title | Linear Reformulation of Polynomial Discrete Programming for Fast Computation | en_US |
dc.type | Article | en_US |
dc.identifier.doi | 10.1287/ijoc.2016.0716 | en_US |
dc.identifier.journal | INFORMS JOURNAL ON COMPUTING | en_US |
dc.citation.volume | 29 | en_US |
dc.citation.spage | 108 | en_US |
dc.citation.epage | 122 | en_US |
dc.contributor.department | 資訊管理與財務金融系 註:原資管所+財金所 | zh_TW |
dc.contributor.department | Department of Information Management and Finance | en_US |
dc.identifier.wosnumber | WOS:000396488400007 | en_US |
顯示於類別: | 期刊論文 |