Linear Reformulation of Polynomial Discrete Programming for Fast Computation

Han-Lin Li (), Yao-Huei Huang () and Shu-Cherng Fang ()
Additional contact information
Han-Lin Li: Department of Information Management and Finance, Institute of Information Management, National Chiao Tung University, Hsinchu, Taiwan
Yao-Huei Huang: School of Economics and Management, Southwest Jiaotong University, China
Shu-Cherng Fang: Department of Industrial and Systems Engineering, North Carolina State University, Raleigh, North Carolina 27695

INFORMS Journal on Computing, 2017, vol. 29, issue 1, 108-122

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.

Keywords: polynomial discrete program; mixed-integer linear program; linearization equation; branch and bound (search for similar items in EconPapers)
Date: 2017
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (3)

Downloads: (external link)
https://doi.org/10.1287/ijoc.2016.0716 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:orijoc:v:29:y:2017:i:1:p:108-122

Access Statistics for this article

More articles in INFORMS Journal on Computing from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().