Linear reformulation of Polynomial discrete programming for fast computation

Han-Lin Li, Yao Huei Huang, Shu Cherng Fang

Research output: Contribution to journalArticlepeer-review

8 Scopus citations

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 mixedinteger 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(h3n3) 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 (102-times) reduction in computational time for some randomly generated cubic polynomial discrete programming problems. There is a Video Overview associated with this article, available as supplemental material.

Original languageEnglish
Pages (from-to)108-122
Number of pages15
JournalINFORMS Journal on Computing
Volume29
Issue number1
DOIs
StatePublished - 1 Dec 2017

Keywords

  • Branch and bound
  • Linearization equation
  • Mixed-integer linear program
  • Polynomial discrete program

Fingerprint Dive into the research topics of 'Linear reformulation of Polynomial discrete programming for fast computation'. Together they form a unique fingerprint.

Cite this