A NEW GLOBAL APPROACH FOR 0-1 POLYNOMIAL PROGRAMS

Abstract

Given a 0-1 polynomial expression SIGMA(k=1)N-1 SIGMA(m=k+1)N x(k)x(m), where x(k) and x(m) are 0-1 variables, the famous Glover and Woolsey method required to use N(N - 1)/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 SIGMA(k=1)N x(k)y(k), y(k) = SIGMA(m=k+1)N x(m); then to transform the expression into a linear form where x(k) and y(k) 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.