A new global approach for 0-1 polynomial programs

Han-Lin Li*

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

2 Scopus citations

Abstract

Given a 0-1 polynomial expression Σk = 1 N - 1Σm = k + 1 Nxkxm, where xk and xm are 0-1 variables, the famous Glover and Woolsey method required to use N(N - l) 2 additional continuous variables and 2N(N - 1) linear constraints to transform this expression into a linear form. This paper proposes a method which first reformulates the above expression as a new expression Σk = 1 Nxkyk, yk = Σm = k + 1 Nxm; then to transform the expression into a linear form where xk and yk are separated. The proposed transformation method only required to use 2(N - 1) additional continuous variables and 8(N - 1) linear constraints. Based on the new transformation, a 0-1 polynomial program can be more effectively solved to obtain a global optimum.

Original languageEnglish
Pages (from-to)319-327
Number of pages9
JournalComputers and Operations Research
Volume21
Issue number3
DOIs
StatePublished - 1 Jan 1994

Fingerprint Dive into the research topics of 'A new global approach for 0-1 polynomial programs'. Together they form a unique fingerprint.

Cite this